4296572
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| Теорема Уитни | Граф является k-связным тогда и только тогда, когда для любой пары вершин x и y найдётся не менее k простых путей из x в y, не имеющих общих внутренних вершин. |
| Отделяющее X от Y множество и его минимальность | Множество вершин, при удалении которых вершины множества X теряют связь с вершинами множества Y. Отделяющее множество минимально, если не существует другого отделяющего X от Y множества меньшего размера. |
| Теорема Гёринга | Размер k минимального отделяющего X от Y множества равен максимальному количеству попарно непересекающихся путей из X в Y. |
| Теорема Менгера | Пусть даны две несмежные вершины x и y. Мощность отделяющего x от y множества равна наибольшему числу попарно непересекающихся во внутренних вершинах путей из x в y. |
| Рёберная теорема Менгера | Количество рёберно-непересекающихся путей из x в y совпадает с размером рёберно-разделяющего x и y множества. |
| Понятие сети | Сеть - ориентированный взвешенный граф, у которого выделены вершины s и t с нулевой входящей и исходящей степенью соответственно. |
| Поток в сети, величина потока | Количество "вещества", протекающего по каждому каналу (ребру), при этом поток не может превышать ёмкости ребра, и входящий поток в любую вершину сети (кроме s и t) равен исходящему. Величина потока - количество вещества, исходящего из s (или входящего в t). |
| Разрез в сети, ёмкость разреза | Пусть в сети задано разделение всех вершин на два блока S и T, причём s ∈ S и t ∈ T. Тогда S-T разрезом называется совокупность рёбер, пересекающих границу множеств S и T. Ёмкость разреза - суммарная ёмкость всех рёбер разреза, выходящих из S и входящих в T. |
| Теорема Форда-Фалкерсона | Величина максимального потока в сети совпадает с пропускной способностью минимального разреза. |
Want to create your own Flashcards for free with GoConqr? Learn more.