Углеродные нанотрубки (стр. 2 из 4)
* * *
Докажем, что любой связный граф можно вычертить «одним росчерком», если разрешить проходить каждое ребро точно два раза.
Если проходить граф описанным выше способом, то его можно сопоставить с графом, у которого приходится по два ребра на каждое ребро исходного графа, т.е. индекс каждой вершины в два раза больше, чем у исходного. Полученный граф имеет вершины с четными индексами, а значит этот граф является уникурсальным (его можно «нарисовать одним росчерком»).
* * *
Граф G` содержит n ребер и тоже не содержит контуров, т.е. является деревом. По предположению индукции для дерева G` соотношение (2) справедливо, и потому в G` имеется n+1 вершина. Заметим теперь, что только один конец добавляемого ребра r является вершиной графа G` (в противном случае, взяв в G` простую цепочку, соединяющую a и b, и добавив к этой цепочке ребро r, мы получили бы контур в графе G). Следовательно, при добавлении ребра r в графе G появляется одно новое ребро и одна новая вершина. Иначе говоря, граф G имеет n+2 вершины и n+1 ребро, и потому соотношение (2) для него справедливо. Проведенная индукция доказывает равенство (2) для любого дерева.
Теперь можно приступить к доказательству теоремы Эйлера. Для ее доказательства выделим из графа G максимальное его дерево G*, обозначим за k - число «перемычек» (т.е. ребер графа G, не содержащихся в G*). Т.к. граф G* является деревом, то он не содержит ни одного контура, а, следовательно, он определяет на сфере лишь одну область (грань), и потому для него соотношение (1) справедливо. Далее, добавляя одну «перемычку», число ребер увеличивается на единицу, число вершин остается прежним, т.к. G* - максимальное дерево, т.е. оно содержит все вершины графа G; число граней увеличится на единицу за счет разбиения одной грани на две. Отсюда видно, что добавление одной «перемычки» не меняет соотношения (1). Значит и добавление k перемычек его не изменит. Т.е. граф G удовлетворяет соотношению (1).
Из теоремы Эйлера можно получить несколько интересных следствий.
Обозначим через n3 число треугольных граней выпуклого многогранника, через n4 - число его четырехугольных граней и т.д. Тогда соотношение один можно переписать так:
В=2+Р-(n3+n4+n5+...). (3)
Т.к. каждое из ребер «принадлежит» ровно двум граням, то можно записать следующую формулу:
Р=
(4)В каждой вершине же сходится минимум три грани, т.е. каждой грани «принадлежит» максимум
вершин, отсюда вытекает неравенство: 
(5)Объединяя (3), (4) и (5), получим
Умножая полученное на 6 и приводя подобные, получим: 
причем равенство возможно только в том случае, когда в вершине сходятся три грани. В нашем случае, для идеальных фулеренов и для нанотрубок, запаянных с обоих концов это выполнено. Отсюда видно, что в состав них может входить ровно 12 пятиугольников.
Вторым следствием теоремы Эйлера является так называемая эйлерова характеристика поверхности.
Пусть Q — поверхность, которая допускает разбиение на многоугольники; это означает, что на поверхности можно «нарисовать» граф, разбивающий ее на конечное число кусков, гомеоморфных кругу. Обозначим число вершин и ребер графа через В и Р, а число многоугольников, на которые Q разбивается этим графом,— через Г. Число
X (Q) = В - Р + Г (6)
называется эйлеровой характеристикой поверхности Q. Строго говоря, число (6) определяется не самой поверхностью Q, а выбором ее разбиения на многоугольники. Однако теорема Эйлера показывает, что для поверхности Q, гомеоморфной сфере, эйлерова характеристика не зависит от выбора разбиения на многоугольники: Х(Q)=2. Докажем, что и для любой поверхности Q ее эйлерова характеристика Х(Q) не зависит от выбора разбиения на многоугольники, а определяется самой поверхностью.
В самом деле, пусть на, поверхности Q «нарисованы» два графа G1, G2, каждый из которых задает разбиение на многоугольники. Числа вершин, ребер и граней разбиения, определяемого графом G1, обозначим через B1, Р1, Г1, а соответствующие числа для разбиения, определяемого графом G2,— через В2, Р2, Г2. Вообще говоря, графы G1 и G2 могут пересекаться в бесконечном числе точек. Однако, «пошевелив» граф G1, мы сможем добиться того, чтобы G1 и G2 пересекались лишь в конечном числе точек.
Далее, если граф G1
G2 несвязен, то, «пошевелив» графы G1, G2, можно добиться того, чтобы они имели общие точки и, следовательно, их объединение было связным. Итак, мы можем предполагать, что графы G1 и G2 пересекаются лишь в конечном числе точек и имеют связное объединение G1 G2. Считая новыми вершинами все точки пересечения графов G1 и G2, а также все вершины этих графов, мы найдем, что G1 G2 является конечным связным графом (его ребрами являются куски ребер графов G1 и G2, на которые они разбиваются вершинами графа G1 G2).Обозначим через В и Р число вершин и ребер графа G1
G2, a через Г — число граней, на которые он разбивает поверхность Q. Идея состоит в том, чтобы доказать равенства 
(7)из которых и будет следовать, что B1-P1+Г1=B2-P2+Г2. Оба равенства (7) доказываются одинаково; докажем первое.
Пусть М - некоторый многоугольник («грань»), определяемый графом G1. Обозначим число вершин и ребер графа G1
G2, расположенных внутри М (не на контуре), через В' и Р', а число вершин (а значит, и ребер) этого графа, расположенных на контуре многоугольника М, через q. Далее, число граней, определяемых графом G1 G2 и содержащихся в М, обозначим через Г'. На рис. 4 имеем В'=4, Р'=12, Г'=9, q=15.Вырежем теперь многоугольник М (вместе с имеющейся на нем частью графа G1
G2) из поверхности Q. Так как М гомеоморфен кругу и, значит, полусфере, то его можно второй («нижней») полусферой дополнить до поверхности, гомеоморфной сфере (рис. 5). На этой сфере расположен связный граф, имеющий В'+q вершин, Р'+q ребер и определяющий Г'+1 граней (Г' граней содержится в М и еще одной гранью является нижняя полусфера). Следовательно, согласно (1), (В'+q)- (Р'+q)+(Г'+1)=2, т. е.В'-Р'+Г=1. (8)
Если теперь (возвращаясь к поверхности Q, на которой начерчен граф G1
G2) мы выбросим из графа G1 G его часть, расположенную внутри М, то получится новый граф, для которого, однако, число В-Р+Г останется таким же, как и для графа G1 G2. В самом деле, вместо В' вершин, Р' ребер и Г' граней, имевшихся внутри М, мы теперь будем иметь 0 вершин, 0 ребер и одну грань (сам многоугольник М), т. е. число В'-Р'+Г' заменится на 0-0+1, а это, согласно (8), ничего не меняет. 
Рис. 4. Рис. 5.
Теперь ясно, что если мы из графа G1
G2 выбросим его части, расположенные внутри всех многоугольников, определяемых графом G1, то получим новый граф G*, для которого число В-Р+Г будет таким же, как и для графа G1 G2 Иначе говоря,В*-Р*+Г*=В-Р+Г (9)
где В* и Р* — число вершин и ребер графа G*, а Г* — число определяемых им граней.
Заметим, наконец, что граф G* получается из G1 добавлением нескольких новых вершин на ребрах. Добавление каждой новой вершины увеличивает число ребер на 1 (поскольку добавленная вершина разбивает одно из ребер на два). Следовательно, если переход от графа G1 к G* осуществляется добавлением k новых вершин, то В*=B1 + k1*P*=P1+k. Кроме того, Г*=Г1 (так как граф G* определяет те же грани, что и граф G1). Таким образом,
В*-Р*+Г*=(B1+k)-(P1+k)+Г1=В1-Р1+Г1,
а это, согласно (9), и дает первое из соотношений (7).
Итак эйлерова характеристика поверхности не зависит от ее разбиения на многоугольники, а определяется самой поверхностью. Кроме того, если поверхности Q1и Q2 гомеоморфны, то X(Q1)=Х(Q2).