Основные понятия теории графов. Гладких О.Б - 82 стр.

      Для доказательства к исходному графу при-            Пусть M – множество таких цепей (скажем
соединяем ребро (А, В); после этого все вершины     μij) в G между концевыми вершинами xi и xj ∈ X –,
графа станут четными. Этот новый граф удовле-       что никакие две цепи не имеют одинаковых ко-
творяет всем условиям теоремы 2.6, и поэтому в      нечных вершин, т.е. цепи соединяют различные
нем можно проложить эйлеров цикл Ψ. И если те-      пары вершин из X.– и покрывают все вершины
перь в этом цикле удалить ребро (А, В), то оста-    множества X –. Число цепей μij в M равно 1/2 | X –| и
нется искомая цепь АВ.                              всегда цело, если конечно оно определено. Пред-
      На этом приеме основано доказательство        положим теперь, что все ребра, образующие цепь
следующей теоремы, которую следует считать          μij, теперь удвоены (добавлены искусственные
обобщением теоремы 2.7.                             ребра). Так поступаем с каждой цепью μij∈ M и по-
Теорема 2.8. Если данный граф является связным      лученный граф обозначим через G – (M). Так как
и имеет 2k вершин нечетной степени, то в нем        некоторые ребра из G могут входить более чем в
можно провести k различных цепей, содержащих        одну цепь μij, то некоторые ребра из G – (M) могут
все его ребра в совокупности ровно по одному        быть (после того как добавлены все «новые» цепи
разу.                                               μij) утроены, учетверены и т.д.
Теорема 2.9. Различных деревьев с n перенумеро-     Теорема 3.3. Для любого цикла, проходящего по
ванными вершинами можно построить n n – 2.          G, можно выбрать множество M, для которого
      Эта теорема известна, в основном, как вывод   граф G – (M) имеет эйлеров цикл, соответствующий
английского математика А..Кэли (1821-1895).         первоначально взятому циклу в графе G. Это соот-
Графы-деревья издавна привлекали внимание уче-      ветствие таково, что если цикл проходит по ребру
ных. Сегодня двоичные деревья используются не       (xi, xj) из G l раз, то в G – (M) существует l ребер
только математиками, а и биологами, химиками,       (одно реальное и l – 1 искусственных) между xi и
физиками и инженерами.                              xj, каждое из которых проходится ровно один раз
Теорема 2.10. Полный граф с пятью вершинами не      эйлеровым циклом из G – (M). Справедливо и об-
является плоским.                                   ратное утверждение.
                Доказательство.                                        Доказательство.
      Воспользуемся формулой Эйлера:


                          82                                                    95