4344345
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| Паросочетание. Соверешнное паросочетание. Максимальное паросочетание. | Паросочетание - любой набор рёбер в графе, не имеющих общих концевых вершин. Паросочетание называется совершенным, если оно покрывает все вершины в графе. Паросочетание максимально, если не существует в графе паросочетания, покрывающего большее количество вершин. |
| Критерий максимальности паросочетания (Теорема Бержа) | Паросочетание максимально, если в графе нет М-дополняющих путей. Это такие пути, которые начинаются и заканчиваются в непокрытой данным паросочетанием вершине и состоят из рёбер, которые поочерёдно то входят в данное паросочетание, то не входят. |
| Вершинно-независимое множество и вершинное покрытие графа | Вершинно-независимое множество - множество вершин, которые не соединены друг с другом рёбрами. Вершинное покрытие графа - множество вершин, которому смежны все рёбра графа. |
| Связь вершинно-независимого множества и вершинного покрытия | Если S - какое-то вершинно-независимое множество, тогда V(G)/S будет каким-то вершинным покрытием графа, и наоборот. |
| Рёберно-независимое множество и рёберное покрытие графа | Рёберно-независимое множество - то же самое, что паросочетение - набор рёбер графа, не имебщих общих концевых вершин. Рёберное покрытие графа - подмножество рёбер графа, покрывающее все его вершины. |
| Связь рёберно-независимого и рёберно-покрывающего множеств | Пусть a - количество вершин в рёберно-независимом множестве, b - количество рёбер в рёберном покрытии графа. Тогда: a + b = V(G) |
| Критерий Татта существования совершенного паросочетания в графе | В графе существует совершенное паросочетание тогда и только тогда, когда для любого подмножества S вершин графа выполняется условие: c0(G-S) <= |S| где c0 - количество нечётных компонент связности |
| Дефицит графа | Это число вершин, не покрытых максимальным паросочетанием |
| Формула Татта-Бержа | def(G) = max[c0(G-S) - |S|] по всем S |
Want to create your own Flashcards for free with GoConqr? Learn more.