4402018
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| Двудольный граф. Критерий двудольности графа | Это граф, множество вершин которого можно разбить на два блока так, что вершины первого блока имеют рёбра только с вершинами второго блока, и наоборот. Критерий двудольности: не должно быть циклов нечётной длины. |
| Х-насыщенное паросочетание в двудольном графе. Критерий Холла для существования Х-насыщенного паросочетания в двудольном графе. | Это такое паросочетание, которое покрывает все вершины блока Х. Критери Холла: если для любого подмножества U вершин Х множество смежных с U вершин по мощности не менее мощности U, то существует Х-насыщенное паросочетание. |
| Минимальное вершинное покрытие в двудольном графе | Количество вершин в минимальном вершинном покрытии в двудольном графе совпадает с количеством рёбер в максимальном паросочетании. |
| Частично упорядоченное множество | Это множество с введённым на нём отношением частичного порядка, обладающим рефлексивностью, транзитивностью и антисимметричностью. |
| Наибольший и наименьший по включению элемент ЧУМ | Это элемент, больше/меньше которого в ЧУМе никого нет. |
| Цепь и антицепь в ЧУМе | Цепь - подмножество ЧУМ, такое, что все элементы сравнимы. Антицепь - такое подмножество ЧУМ, все элементы которого не сравнимы. |
| Теорема Дилоурса | Минимальное количество цепей, покрывающих ЧУМ, равно количеству элементов в максимальной антицепи. |
| Теорема Мирского | Если М - длина наибольшей цепи, то ЧУМ разбивается ровно на М антицепей, объединение которых даёт нам весь ЧУМ. |
Want to create your own Flashcards for free with GoConqr? Learn more.