5. Паросочетания в графах

Sergei Fomin
Flashcards by Sergei Fomin, updated more than 1 year ago
Sergei Fomin
Created by Sergei Fomin about 5 years ago
33
0

Description

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

Resource summary

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
Show full summary Hide full summary

Similar

2. Циклы в графах
Sergei Fomin
3. Связность в графах
Sergei Fomin
4. Связность в графах (ч. 2)
Sergei Fomin
7. Раскраска графов
Sergei Fomin
8. Планарные графы
Sergei Fomin
6. Паросочетания в графах (ч. 2)
Sergei Fomin
1. Основные понятия теории графов
Sergei Fomin
Edexcel Additional Science Biology Topic 1
hchen8nrd
Biology -B2
Sian Griffiths
Bayonet Charge flashcards
Angeles Mercado
mi mapa conceptual
Andrea Agudelo