4. Связность в графах (ч. 2)

Description

Карточки по четвёртой лекции курса "Основы теории графов" на stepic.org
Sergei Fomin
Flashcards by Sergei Fomin, updated more than 1 year ago
Sergei Fomin
Created by Sergei Fomin about 8 years ago
7
0

Resource summary

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.
Теорема Форда-Фалкерсона Величина максимального потока в сети совпадает с пропускной способностью минимального разреза.
Show full summary Hide full summary

Similar

2. Циклы в графах
Sergei Fomin
3. Связность в графах
Sergei Fomin
7. Раскраска графов
Sergei Fomin
8. Планарные графы
Sergei Fomin
5. Паросочетания в графах
Sergei Fomin
6. Паросочетания в графах (ч. 2)
Sergei Fomin
1. Основные понятия теории графов
Sergei Fomin
Деление двузначного числа на двузначное
Эльвира Шемякина
Доли и дроби
Татьяна Иващенко
Тест 1- събиране и изваждане на числата до 6
Светла Събева
Събиране и изваждане до 6
Светла Събева