Математическая культура. Мациевский С.В. - 42 стр.

                            п. 3. Дерево
   1. Цикл. Цепь называется циклом, если она замкнутая и простая (т.е. в
цепи все вершины различны, кроме, быть может, первой и последней).
   Цикл длины три называется треугольником.                   v
   Пример. На рисунке имеются следующие цепи:
   1) цепь v → w → x → y → z → x;                              w
   2) простая цепь v → w → x → y → z;
   3) замкнутая цепь v → w → x → y → z → x → v;
                                                          y           x
   4) цикл v → w → x → y → v;
   5) треугольник v → w → x → v.                              z
   2. Дерево. Лесом называется граф, не содержащий циклов. Связный лес
называется деревом.
   Граф является деревом тогда и только тогда, когда любые две его вер-
шины соединены ровно одной простой цепью.
   Очевидно, что дерево не содержит циклов, но, добавляя к нему 1 ребро,
получаем ровно 1 цикл.
   Дерево порядка n имеет n – 1 ребро.
   Примеры.
   1. Существуют только два дерева
порядка 4, и только три — порядка 5.
   Упр. 7. Нарисуйте все 6 деревьев порядка 6.
   2. Задача о соединении городов. Соединить города железными дорога-
ми так, чтобы были соединены любые два города при минимальной длине
железных дорог. Решением этой задачи является дерево. Имеется алгоритм
для его построения.
   3. Задача о коммивояжере. Коммивояжер желает посетить несколько
городов, заехав в каждый хотя бы один раз и проделав путь наименьшей
длины. Общий алгоритм решения этой задачи неизвестен.
   3. Планарный граф. Изображенный на плоскости граф так, что ника-
кие два его ребра не пересекаются, называется плоским. Граф, изоморф-
ный плоскому графу, называется планарным.
   Граф полный, если в нем любые две вершины смежны. Полный граф
порядка n обозначается Kn. Граф K5 не планарен, поскольку его нельзя на-
рисовать на плоскости без пересечений ребер.
   Пример. Изоморфные полные планарные графы
порядка 4. Первый из этих графов не плоский.
   Упр. 8. Нарисуйте на плоскости полный граф K5.
   Каждый подграф планарного графа планарен.
   Граф, имеющий непланарный подграф, непланарен.


                                   41