Flashcards
4. Связность в графах (ч. 2)
Cards in this deck (9)
- 1Теорема УитниГраф является k-связным тогда и только тогда, когда для любой пары вершин x и y найдётся не менее k простых путей из x в y, не имеющих общих внутренних вершин.
- 2Отделяющее X от Y множество и его минимальностьМножество вершин, при удалении которых вершины множества X теряют связь с вершинами множества Y.
Отделяющее множество минимально, если не существует другого отделяющего X от Y множества меньшего размера. - 3Теорема ГёрингаРазмер k минимального отделяющего X от Y множества равен максимальному количеству попарно непересекающихся путей из X в Y.
- 4Теорема МенгераПусть даны две несмежные вершины x и y. Мощность отделяющего x от y множества равна наибольшему числу попарно непересекающихся во внутренних вершинах путей из x в y.
- 5Рёберная теорема МенгераКоличество рёберно-непересекающихся путей из x в y совпадает с размером рёберно-разделяющего x и y множества.
- 6Понятие сетиСеть - ориентированный взвешенный граф, у которого выделены вершины s и t с нулевой входящей и исходящей степенью соответственно.
- 7Поток в сети, величина потокаКоличество "вещества", протекающего по каждому каналу (ребру), при этом поток не может превышать ёмкости ребра, и входящий поток в любую вершину сети (кроме s и t) равен исходящему.
Величина потока - количество вещества, исходящего из s (или входящего в t). - 8Разрез в сети, ёмкость разрезаПусть в сети задано разделение всех вершин на два блока S и T, причём s ∈ S и t ∈ T. Тогда S-T разрезом называется совокупность рёбер, пересекающих границу множеств S и T.
Ёмкость разреза - суммарная ёмкость всех рёбер разреза, выходящих из S и входящих в T. - 9Теорема Форда-ФалкерсонаВеличина максимального потока в сети совпадает с пропускной способностью минимального разреза.
Information
- Description
- Карточки по четвёртой лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 38
- Tags
- Rating