Полностью динамическая связность высоких степеней: различия между версиями

Теорема 1 (Форд и Фулкерсон; Элиас, Файнштайн и Шеннон). Пусть даны граф G и две вершины x и y, принадлежащие G. x и y являются k-реберно-связными в том и только том случае, если между x и y имеется не менее k путей с непересекающимися ребрами.

Подобным же образом, множество вершин V0 С V — {x, yg называется вершинным разрезом для вершин x и y, если удаление всех вершин V0 разрывает связь между x и y. V0 С V является вершинным разрезом для вершин графа G, если удаление всех вершин V0 разбивает G.

Мощность вершинного разреза V0, обозначаемая jV0j, задается числом дуг в V0. Вершинный разрез V0 для x и y называется вершинным разрезом минимальной мощности или, вкратце, вершинным разрезом связности, если не существует другого вершинного разреза V00 для x и y, такого, что \V"\ < jV0j. Тогда x и y являются k-вершинно-связными в том и только том случае, если вершинный разрез связности для x и y содержит не менее k вершин. Граф G называется k-вершинно-связным, если все его пары вершин являются k-вершинно-связными. Вершинный разрез связности, мощность которого равна 1, называется точкой сочленения; вершинный разрез связности мощности 2 называется парой разделителей. Заметим, что для связности по вершинам уже неверно утверждение о том, что вершинный разрез связности разбивает граф G на два множества вершин.

Теорема 2 (Менгер). Пусть даны граф G и две вершины x и y, принадлежащие G. x и y являются k-вершинно-связными в том и только том случае, если между x и y имеется не менее k вершинно-непересекающихся путей.