Cтраница 1
Добавление любого ребра ( х х) из О, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из x в х, и только что добавленного ребра. Так как в графе О имеется т ребер, п - 1 из которых лежат в Т, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа С. [1]
Добавление любого ребра ( xi: xs) из G, не принадлежащего Т, к ребрам дерева Т приводит к образованию точно одного ( простого) цикла, состоящего из ребер остова Т, лежащих на ( единственной) цепи из X ] в Х, и только что добавленного ребра. Так как в графе G имеется т ребер, п - 1 из которых лежат в Г, то число всех циклов, построенных таким способом, равно т - п 1, что совпадает с цикломатическим числом графа G. [2]
Легко видеть, что добавление любого ребра в граф, обладающий указанными в теореме свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к G произвольного ребра приводит к га-мильтонову графу, любые две несмежные вершины соединимы простой остовной цепью. [3]
Предположим, что Т несвязен; тогда добавление любого ребра, соединяющего вершину одной компоненты с вершиной другой компоненты, не приводит к образованию цикла. [4]
Максимальным планарным графом называется граф, который при добавлении любого ребра перестает быть планарным. Уитни ( см. [4]) доказал, что каждый максимальный планарный граф, имеющий ps4 вершин, трехсвязен. [5]
Максимальным планарным графом называется граф, который при добавлении любого ребра перестает быть планарным. [6]
Он будет максимальным тогда и только тогда, когда добавление любого ребра Е0 к Е дает запрещенные части в графе ( G. [7]
Очевидно, остающийся граф Т связен и не имеет циклон; кроме того, добавление любого ребра к Т дает некоторый цикл. [8]
Под гранью здесь понимается часть плоскости, ограниченная ребрами графа, внутри которой нет ни вершин, ни ребер. Добавление любого ребра в такой граф влечет за собой появление пересечений в графе. [9]
Мы докажем, что G двойствен по Уитни к G, показав, что определяющее двойственность по Уитни равенство остается неизменным при добавлении любого ребра из G к подграфу Я. Так как это, очевидно, верно для Я, вообще не содержащего ребер, то можно провести индукцию по числу ребер в Я. [10]