| ← Май 2011 → | ||||||
|
2
|
3
|
4
|
5
|
6
|
8
|
|
|---|---|---|---|---|---|---|
|
10
|
11
|
13
|
14
|
15
|
||
|
16
|
17
|
18
|
20
|
21
|
||
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
|
31
|
||||||
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://rusfaq.ru/issues/8/19/525
Открыта:
17-04-2009
Статистика
0 за неделю
RFpro.ru: Консультации по дискретной математике
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты данной рассылки
/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная
Вопрос № 183013: Здравствуйте! Прошу помощи в следующем вопросе: 1. Все перестановки 7 чисел (1;2;3;4;5;6;7) упорядочены в лексикографическом порядке. Какой по счету идет перестановка 6153742 ? 4. Постройте наибольшее паросочетание для двудольного графа... Вопрос № 183013:
Здравствуйте! Прошу помощи в следующем вопросе:
Отправлен: 02.05.2011, 14:41 Отвечает Гордиенко Андрей Владимирович (Модератор) : Здравствуйте, Посетитель - 351942! Рассмотрим первую задачу. При упорядочении перестановок в лексикографическом порядке первой является перестановка 1234567, последней - перестановка 7654321. 1) Перед перестановкой 6153742 находятся перестановки, начинающиеся с цифр 1, 2, 3, 4, 5. Их количество равно 5 · 6! = 3600. Номер рассматриваемой нами перестановки не меньше числа 3600 + 1 = 3601. 2) Рассмотрим перестановку 153742. Цифра 1 является первой из возможных, поэтому номер перестановки не меняется. 3) Рассмотрим перестановку 53742. Перед ней находятся перестановки, начинающиеся с цифр 2, 3, 4 (цифра 1 уже использована). Их количество равно 3 · 4! = 72. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3601 + 72 = 3673. 4) Рассмотрим перестановку 3742. Перед ней находятся перестановки, начинающиеся с цифры 2 (цифра 1 уже использована). Их количество равно 1 · 3! = 6. С учётом рассмотренных выше перестано вок, номер заданной перестановки не меньше числа 3673 + 6 = 3679. 5) Рассмотрим перестановку 742. Перед ней находятся перестановки, начинающиеся с цифр 2, 4 (цифры 1, 3, 5, 6 уже использованы). Их количество равно 2 · 2! = 8. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3679 + 8 = 3687. 6) Рассмотрим перестановку 42. Перед ней находятся перестановки, начинающиеся с цифры 2. Их количество равно 1 · 1! = 1. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3687 + 1 = 3688. Последний элемент перестановки роли не играет. Следовательно, искомый номер перестановки равен 3688. Ответ: 3688. С уважением. ----- Facta loquantur (Пусть говорят дела).
Ответ отправил: Гордиенко Андрей Владимирович (Модератор)
Отвечает Асмик Александровна (Академик) : Здравствуйте, Посетитель - 351942! Паросочетание -- произвольное подмножество попарно несмежных ребер графа. Максимальное паросочетание (maximal matching) -- паросочетание, которое не содержится в паросочетании с большим числом ребер. Наибольшее паросочетание (maximum matching) -- паросочетание, в котором число рёбер наибольшее среди всех паросочетаний графа. Двудольный (bipartite) граф -- такой граф, вершины которого (V) можно разделить на два множества (V+ и V-), так чтобы вершины каждого из множеств были попарно несмежны. Определение Пусть есть паросочетание в графе (V, E), обозначим его M (множество рёбер). M-чередующийся путь -- это путь в графе, содержащий поочерёдно рёбра из M и из (E\M). Теорема Паросочетание M является наибольшим тогда и только тогда, когда нет невырожденного M-чередующегося пути, начинающегося и заканчивающегося в вершинах, не инцидентных ни одному ребру из М. Лемма Если такой путь есть (обозначим ег о рёбра как P), то можно получить разбиение большее, чем M, следующим образом: M' = M⊕ P (симметрическая разность, или XOR). Для решения задачи о паросочетании остается научиться находить увеличивающие пути или убеждаться, что таких путей нет. Алгоритм прост -- начать с пустого паросочетания M={} и постепенно увеличивать его, находя M-чередующийся путь из теоремы и выполняя операции, указанные в лемме. Когда путь найти будет нельзя, это будет означать, что M -- наибольшее паросочетание. Вначале все вершины ненасыщенные. Для построения начального паросочетания применим «жадный» алгоритм; будем просматривать по очереди вершины из первой доли, если из нее ведут ребра в ненасыщенные вершины из K будем жадно хватать и вводить в паросочетание первое попавшееся ребро, не думая о последствиях. добавляем ребро M={(a,ε?),(b,σ?)(c,ο)(d,α?)(f,γ)} Далее, преобразуем двудольный граф G в ориентированный граф G’, введя ориентацию сл едующим образом: все ребра, вошедшие в M, ориентируем снизу вверх, т.е. из второй доли в первую, а остальные ребра сверху вниз. Очевидно, что увеличивающая относительно паросочетания M цепь существует в графе G тогда и только тогда, когда в графе B’ существует путь из s в t, где s -ненасыщенная вершина из 1 доли, t из второй. Вершины g и e - ненасыщенные в верхней доле, β? и δ во второй. Если среди достижимых вершин из g и e окажется вершина ? и ?, есть увеличивающая относительно M цепь в графе G. В эти вершины путь ведет лишь из d, а туда лишь из α?. В α? не ведет ни одного пути. Значит, постороенное паросочетание наибольшее. 
Ответ отправил: Асмик Александровна (Академик)
Оценить выпуск »
Задать вопрос экспертам этой рассылки »Скажите "спасибо" эксперту, который помог Вам!Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТАна короткий номер 1151 (Россия) Номер ответа и конкретный текст СМС указан внизу каждого ответа.
* Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи.
(полный список тарифов) © 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Компания "Московский хостер" Версия системы: 2011.6.31 от 03.04.2011 |
| В избранное | ||
