Дискретная математика: графы и автоматы. Альпин Ю.А - 14 стр.

14                                       Глава 1. Неориентированные графы


Но это неравенство возможно лишь при k = 0. ¤

         § 3. Деревья. Минимальные остовы графов

   1. Основные свойства деревьев. Перейдём к изучению гра-
фов, в некотором смысле противоположных эйлеровым и гамильто-
новым графам.
   Деревом называется связный граф без циклов. Граф без циклов
называют лесом.
   На рис. 6 изображены примеры деревьев с 4-мя вершинами.




                                Рис. 6

Рассматриваемые вместе, эти деревья определяют лес.
    Прежде, чем доказать теорему о свойствах деревьев, введём новое
понятие и установим два полезных факта.
    Ребро связного графа называется мостом, если удаление его при-
водит к несвязному графу (очевидно, с двумя компонентами). Вооб-
ще, ребро графа называется мостом, если оно является мостом ком-
поненты, которой оно принадлежит.
    Предложение 1. Ребро является мостом тогда и только то-
гда, когда оно не принадлежит ни одному циклу.
     Доказательство достаточно провести для связного графа. Ес-
ли ребро {u, v} принадлежит циклу, то вершины u и v связаны марш-
рутом, не содержащим этого ребра. Этим маршрутом можно заменить
все вхождения ребра {u, v} в маршруты. Следовательно, удаление
ребра {u, v} не нарушает связанности вершин.
     Обратно, если после удаления ребра {u, v} получается связный
граф, то в нём существуют (u, v)-маршрут и, следовательно, простая
(u, v)-цепь, не содержащие ребра {u, v}. Но это значит, что в исходном
графе это ребро принадлежит простому циклу. ¤
   Предложение 2. Связный граф с n вершинами имеет не мень-
ше, чем n − 1 ребер.
   Д о к а з а т е л ь с т в о. Для графов с малым числом вершин
утверждение очевидно. Пусть оно верно для графов с числом вер-
шин, строго меньшим n. Докажем его для графов с n вершинами.
Будем последовательно удалять из графа рёбра до тех пор, пока не