2.5. Разрезающие множества

К разрезающему множеству S связного графа G относится такое минимальное множество ребер графа G, что удаление их из графа G разделяет последний, т. е. граф становится несвязным.

Рис. 2.5. Иллюстрация определения разрезающего множества, а — граф

В качестве примера рассмотрим подмножество ребер графа G (рис. 2.5, а). После удаления - S, из G получаем (рис. 2.5, б). Граф — несвязный. Кроме того, удаление любого собственного подмножества не может превратить

граф G в несвязный. Таким образом, разрезающее множество графа

Рассмотрим теперь множество . Граф (рис. 2.5, в) — несвязный. Однако множество являющееся собственным подмножеством также превращает граф G в несвязный. Граф -показан на рис. 2.5, г. Следовательно, не будет разрезающим множеством графа.

Заметим, что по определению разрезающего множества, данного выше, если является разрезающим множеством графа G, то ранги G и отличаются по крайней мере на единицу, т. е. . В работе [2.1] приводится следующее определение разрезающего множества:

Разрезающим множеством S связного графа G является такое минимальное множество ребер G, что удаление S разбивает граф G на две компоненты, т. е. Возникает вопрос: эквивалентны ли эти два определения? Ответ — положителен, а доказательство оставлено в качестве упражнения 2.15.