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

Пусть даны неориентированный граф G = (V, E) и целое число к > 2. Пара вершин hu; vi называется k-реберно-связной, если при удалении любых (k — 1) ребер графа G вершины u и v остаются связанными. Нетрудно заметить, что в данном случае имеет место отношение эквивалентности: вершины графа G этим отношением разбиваются на классы эквивалентности, называемые k-реберно-связными компонентами. Граф G называется k-реберно-связным, если при удалении любых (k — 1) ребер G сохраняет связность. Согласно этим определениям, граф G является k-реберно-связным в том и только том случае, если любые две вершины G являются k-реберно-связными. Множество ребер E0 С E является реберным разрезом для вершин x и y, если удаление всех ребер, входящих в E0, разбивает G на два графа, один из которых содержит x, а другой – y. Множество ребер E0 С E является реберным разрезом для G, если удаление всех ребер, входящих в E0, разбивает G на два графа. Реберный разрез E0 графа G (для x и y, соответственно) является минимальным, если удаление любого ребра из E0 восстанавливает связность G (x и y, соответственно). Мощность реберного разреза E0, обозначаемая jE0j, задается числом ребер в E0. Реберный разрез E0 графа G (вершин x и y, соответственно) называется реберным разрезом минимальной мощности или, вкратце, реберным разрезом связности, если не существует другого реберного разреза E00 графа G (x и y, соответственно), такого, что \E"\ < jE0j. Реберные разрезы связности, разумеется, являются минимальными реберными разрезами. Заметим, что G является k-реберно-связным в том и только том случае, если реберный разрез связности для G содержит не менее k ребер, а вершины x и y являются k-реберно-связными в том и только том случае, если реберный разрез связности для x и y содержит не менее k ребер. Реберный разрез связности, мощность которого равна 1, называется мостом.

Следующая теорема, которую предложили Форд и Фулкерсон, а также Элиас, Файнштайн и Шеннон [ ], дает еще одну характеристику k-реберной-связности.