Flashcards
5. Паросочетания в графах
Cards in this deck (9)
- 1Паросочетание. Соверешнное паросочетание. Максимальное паросочетание.Паросочетание - любой набор рёбер в графе, не имеющих общих концевых вершин.
Паросочетание называется совершенным, если оно покрывает все вершины в графе.
Паросочетание максимально, если не существует в графе паросочетания, покрывающего большее количество вершин. - 2Критерий максимальности паросочетания (Теорема Бержа)Паросочетание максимально, если в графе нет М-дополняющих путей. Это такие пути, которые начинаются и заканчиваются в непокрытой данным паросочетанием вершине и состоят из рёбер, которые поочерёдно то входят в данное паросочетание, то не входят.
- 3Вершинно-независимое множество и вершинное покрытие графаВершинно-независимое множество - множество вершин, которые не соединены друг с другом рёбрами.
Вершинное покрытие графа - множество вершин, которому смежны все рёбра графа. - 4Связь вершинно-независимого множества и вершинного покрытияЕсли S - какое-то вершинно-независимое множество, тогда V(G)/S будет каким-то вершинным покрытием графа, и наоборот.
- 5Рёберно-независимое множество и рёберное покрытие графаРёберно-независимое множество - то же самое, что паросочетение - набор рёбер графа, не имебщих общих концевых вершин.
Рёберное покрытие графа - подмножество рёбер графа, покрывающее все его вершины. - 6Связь рёберно-независимого и рёберно-покрывающего множествПусть a - количество вершин в рёберно-независимом множестве, b - количество рёбер в рёберном покрытии графа. Тогда:
a + b = V(G) - 7Критерий Татта существования совершенного паросочетания в графеВ графе существует совершенное паросочетание тогда и только тогда, когда для любого подмножества S вершин графа выполняется условие:
c0(G-S) <= |S|
где c0 - количество нечётных компонент связности - 8Дефицит графаЭто число вершин, не покрытых максимальным паросочетанием
- 9Формула Татта-Бержаdef(G) = max[c0(G-S) - |S|] по всем S
Information
- Description
- Карточки к пятой лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 77
- Tags
- Rating