Углеродные нанотрубки
Контуром в графе называется замкнутая цепочка ребер, объединение которых представляет собой линию, гомеоморфную окружности.
Деревом называется связный граф, не содержащий ни одного контура.
Индекс точки называется число дуг, сходящихся в данной точке.
Также следует доказать следующую теорему:
Для любого дерева, имеющего В вершин и Р ребер, справедливо соотношение
В-Р=1. (2)
Для доказательства проведем индукцию по числу ребер Р. При Р=1 (дерево имеет одно ребро и две вершины) соотношение (2) справедливо. Предположим, что для любого дерева, имеющего n ребер, соотношение (2) уже доказано, и пусть G — дерево, имеющее n+1 ребро. Так как граф G связен, то его можно получить из некоторого связного графа G` добавлением одного ребра r.
Действительно, любой связный граф может быть получен следующим образом: мы берем одно ребро, затем присоединяем к нему еще одно ребро так, чтобы снова получился связный граф, затем присоединяем еще одно ребро (так, чтобы снова получился связный граф)
* * *
Докажем, что любой связный граф можно вычертить «одним росчерком», если разрешить проходить каждое ребро точно два раза.