6. Паросочетания в графах (ч. 2)

Sergei Fomin
Flashcards by , created over 3 years ago

Карточки по шестой лекции курса "Основы теории графов" на stepic.org

12
0
0
Sergei Fomin
Created by Sergei Fomin over 3 years ago
Собирање и одземање до 1000 без премин
Vanco Petrusevski
2. Циклы в графах
Sergei Fomin
8. Планарные графы
Sergei Fomin
10 Study Techniques
PatrickNoonan
Biology- Genes and Variation
Laura Perry
7. Раскраска графов
Sergei Fomin
Доли и дроби
Татьяна Иващенко
Събиране и изваждане до 6
Светла Събева
Tablica za umnovenie s 3
marsies marsies
Математически задачи с числата до 5
Светла Събева
Question Answer
Двудольный граф. Критерий двудольности графа Это граф, множество вершин которого можно разбить на два блока так, что вершины первого блока имеют рёбра только с вершинами второго блока, и наоборот. Критерий двудольности: не должно быть циклов нечётной длины.
Х-насыщенное паросочетание в двудольном графе. Критерий Холла для существования Х-насыщенного паросочетания в двудольном графе. Это такое паросочетание, которое покрывает все вершины блока Х. Критери Холла: если для любого подмножества U вершин Х множество смежных с U вершин по мощности не менее мощности U, то существует Х-насыщенное паросочетание.
Минимальное вершинное покрытие в двудольном графе Количество вершин в минимальном вершинном покрытии в двудольном графе совпадает с количеством рёбер в максимальном паросочетании.
Частично упорядоченное множество Это множество с введённым на нём отношением частичного порядка, обладающим рефлексивностью, транзитивностью и антисимметричностью.
Наибольший и наименьший по включению элемент ЧУМ Это элемент, больше/меньше которого в ЧУМе никого нет.
Цепь и антицепь в ЧУМе Цепь - подмножество ЧУМ, такое, что все элементы сравнимы. Антицепь - такое подмножество ЧУМ, все элементы которого не сравнимы.
Теорема Дилоурса Минимальное количество цепей, покрывающих ЧУМ, равно количеству элементов в максимальной антицепи.
Теорема Мирского Если М - длина наибольшей цепи, то ЧУМ разбивается ровно на М антицепей, объединение которых даёт нам весь ЧУМ.