3. Разрезы

Понятие разреза очень тесно связано с понятием цикла и определяется так.

Определение. Бели вершины неориентированного графа разбиты на два множества является дополнением относительно X), то множество ребер графа одни концевые вершины которых лежат в а другие называется разрезом графа

Множество ребер разреза может быть представлено множеством вершин пары Таким образом, остовный подграф полученный из удалением ребер, принадлежащих разреву, является несвязным Грефом, состоящим но крайней мере из двух компонент. В графе на рис. 9.4

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

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

Рис. 9.4. разрез

Это множество можно также представить парой хотя теперь остовный подграф, полученный удалением правильного разреза из разбивает точно на две связные компоненты, одна из которых имеет своими вершинами множество а другая — множество В общем случае каждый разрез является объединением некоторого числа правильных разрезов. В графе на рис. 9.4, например, разрез, показанный пунктиром, является объединением трех правильных резрезов:

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

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

Разрез был определен выше для неориентированного графа. Если граф ориентированный, то разрез графа определяется как множество дуг, соответствующих ребрам неориентированного дубликата графа Некоторые из дуг разреза графа будут ориентированы из 10 в 10. и множество этих дуг будет записываться как в то время как множество дуг, ориентированных из вершин множества в вершины множества будет записываться как Поэтому разрез состоящий из дуг ориентированного графа, определяется как объединение

Например для графа на рис. 9.5 множество дуг является разрезом, разделяющим множества вершин

Рис. 9.5. Ориентированные разрезы.

Это разрез образован дугами подмножеств

Множество фундаментальных циклов неориентированного графа было определено в предыдущем разделе как множество циклов, каждый из которых получается путем добавления какого-нибудь ребра, не принадлежащего остову к ребрам этого остова. Аналогичным образом, имея в виду отмеченную выше двойственность меясду разрезами и остовами, фундаментальные разрезы относительно остова определяются как разрезов, каждый из которых содержит одно, и только одно ребро, принадлежащее дереву

Следующая теорема устанавливает связь между фундаментальными разрезами и фундаментальными циклами и дает способ аостроения фундаментальных разрезов.

Теорема 1. Если остов неориентированного ерафа то фундаментальный разрез, определяемый ребром из образован и теми ребрами из не принадлежащими которые после добавления к дают фундаментальные циклы, содержащие

Доказательство. Если из остова удалить ребро то распадается на два поддерева (см. рис. 9.6). Любое ребро, одна концевая вершина которого лежит в а другая в должно принадлежать фундаментальному раарезу, так как добавление любого такого ребра к ребрам из приводит к образованию другого остова графа следовательно, любое множество, не содержащее таких ребер, не будет разрезом. Множество <аких ребер вместе с ребром является разрезом, так как их

Рис. 9.6. Фундаментальные циклы, содержащие ребро

удаление разбивает граф на два подграфа, один из которых имеет множеством своих вершин а другой Значит, этот разрез является фундаментальным разрезом. Более того, так как ребро является единственным ребром, через которое проходят цепи остова начинающиеся в вершинах из и оканчивающиеся в вершинах из то единственными ребрами, замыкающими фундаментальные циклы, содержащие ребро будут те, одна концевая вершина которых лежит в а другая в Т (таковы, например, ребра в графе на рис. 9.6). Это доказывает теорему.