Совершенное паросочетание в двудольном графе

  Рет қаралды 7,259

Kirsanov2011

Kirsanov2011

8 жыл бұрын

Дискретная математика. Теория графов. Для определения числа совершенных паросочетаний вычисляем перманент матрицы смежности двудольного графа. Затем составляем вспомогательную таблицу, в которой отмечаем запрещенные для размещения единиц места. Сначала расставляем единицы произвольно (в каждой строке и столбце по одной единице, не более). Потом начинаем добавлять единицы передвигая мешающие по найденному заранее адресу.

Пікірлер: 5
@ucumberoor3891
@ucumberoor3891 8 жыл бұрын
Спасибо, классный видос)
@nRADRUS
@nRADRUS 8 жыл бұрын
ловко
@wildbine
@wildbine 2 жыл бұрын
Я впервые узнал, что перманент матрицы будет количеством совершенных паросочетаний. В целом, логично. Но это работает для любого графа с любой матрицей смежности? (не только для двудольного с равным количеством вершин в обеих долях)
@kirkandreev4519
@kirkandreev4519 8 жыл бұрын
добрый день) я очень плохой студеном в этом семестре, очень много пропустил, но строй мех знаю в идеале но вот возникли проблемы с расчетом плиты(плоского дела) методом конечных элементов из за недостатка информации очень прошу вас облегчить мою жизнь, и пока
@Kirsanov2011
@Kirsanov2011 8 жыл бұрын
+Kirk Andreev Метод конечных элементов пока не планирую. Извините...
Таблица инверсии
9:58
Kirsanov2011
Рет қаралды 5 М.
Венгерский алгоритм
34:33
Kirsanov2011
Рет қаралды 18 М.
Why You Should Always Help Others ❤️
00:40
Alan Chikin Chow
Рет қаралды 137 МЛН
Just try to use a cool gadget 😍
00:33
123 GO! SHORTS
Рет қаралды 85 МЛН
small vs big hoop #tiktok
00:12
Анастасия Тарасова
Рет қаралды 19 МЛН
Матрицы графа и их связь
23:52
Kirsanov2011
Рет қаралды 5 М.
Паросочетания  двудольного графа
18:55
ЦЕНТР ТЯЖЕСТИ
2:54
Александр Соловушкин
Рет қаралды 687
Поиск компонент сильной связности в графе. Алгоритм Косараджу
18:57
Олимпиадное программирование в УлГТУ
Рет қаралды 7 М.
Паросочетание в двудольном графе
16:00
Парадокс двух конвертов // Vital Math
13:06
Vital Math
Рет қаралды 288 М.
Планарные графы
10:44
Данил Лебедев
Рет қаралды 9 М.
Why You Should Always Help Others ❤️
00:40
Alan Chikin Chow
Рет қаралды 137 МЛН