Flashcards
6. Паросочетания в графах (ч. 2)
Cards in this deck (8)
- 1Двудольный граф. Критерий двудольности графаЭто граф, множество вершин которого можно разбить на два блока так, что вершины первого блока имеют рёбра только с вершинами второго блока, и наоборот.
Критерий двудольности: не должно быть циклов нечётной длины. - 2Х-насыщенное паросочетание в двудольном графе. Критерий Холла для существования Х-насыщенного паросочетания в двудольном графе.Это такое паросочетание, которое покрывает все вершины блока Х.
Критери Холла: если для любого подмножества U вершин Х множество смежных с U вершин по мощности не менее мощности U, то существует Х-насыщенное паросочетание. - 3Минимальное вершинное покрытие в двудольном графеКоличество вершин в минимальном вершинном покрытии в двудольном графе совпадает с количеством рёбер в максимальном паросочетании.
- 4Частично упорядоченное множествоЭто множество с введённым на нём отношением частичного порядка, обладающим рефлексивностью, транзитивностью и антисимметричностью.
- 5Наибольший и наименьший по включению элемент ЧУМЭто элемент, больше/меньше которого в ЧУМе никого нет.
- 6Цепь и антицепь в ЧУМеЦепь - подмножество ЧУМ, такое, что все элементы сравнимы.
Антицепь - такое подмножество ЧУМ, все элементы которого не сравнимы. - 7Теорема ДилоурсаМинимальное количество цепей, покрывающих ЧУМ, равно количеству элементов в максимальной антицепи.
- 8Теорема МирскогоЕсли М - длина наибольшей цепи, то ЧУМ разбивается ровно на М антицепей, объединение которых даёт нам весь ЧУМ.
Information
- Description
- Карточки по шестой лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 68
- Tags
- Rating