Cтраница 1
Сжатие графов на рис. 2.27, г, е, з приводит к графам, показанным соответственно на рис. 2.27, д, ж, и. [1]
Подграфы сжатий графа С являются сжатиями подграфов графа О. [2]
Подграф сжатия графа О называется минором графа С. Таким образом, всякое сжатие графа О является минором этого графа и, с точностью до вершинного изоморфизма, всякий подграф графа С является минором графа О. [3]
Здесь вследствие сжатия графа столбцы ребер заменены столбцами ветвей, а строки вершин - строками узлов. Кроме того, в этой матрице вследствие ориентации ветвей инцидентным коэффициентам приписаны разные знаки: положительный для ветвей, направленных от инцидентного узла, и отрицательный для ветвей, направленных в сторону инцидентного узла. Такой выбор знаков инцидентных коэффициентов соответствует правилу знаков для токов ветвей, оттекающих и притекающих к узлу. [4]
Для посторения пирамиды может также использоваться сжатие графа. [5]
Минор минора графа О есть подграф сжатия некоторого подграфа какого-то сжатия графа О. [6]
Операция, переводящая графе большим количеством вершин, в граф с меньшим количеством вершин за счет удаления из соответствующих элементарных цепей разделяющих их вершин, называется сжатием графа. [7]
Подграф сжатия графа О называется минором графа С. Таким образом, всякое сжатие графа О является минором этого графа и, с точностью до вершинного изоморфизма, всякий подграф графа С является минором графа О. [8]
Минор минора графа О есть подграф сжатия некоторого подграфа какого-то сжатия графа О. О, а потому ( в силу теорем 1.5 и 11.7) вершинно изоморфен подходящему подграфу некоторого сжатия графа О. [9]
Будем говорить, что семейство Т обладает нечетным циклическим свойством, если нет - сжатия графа G, являющегося двудольным графом. Заметим, что из этого свойства следует, в частности, что Т состоит из разных разрезов. Отметим также, что если мы добавим к Т все тривиальные разрезы, то суть свойства не изменится. [10]