Теория графов и их применение
| Вид материала | Курсовая |
- 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
- «Теория графов», 114.81kb.
- Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
- «Применение информационный технологий в теории графов», 272.84kb.
- Билеты по Дискретной математике «Теория Графов», 12.79kb.
- Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
- Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов., 13.97kb.
- Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.
- Знать содержание программы курса; иметь навыки структурного моделирования типовых объектов;, 56.2kb.
- Теория конечных графов и её приложения прак зан, 29.91kb.
ДеревьяДеревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом. Из теоремы 2 ссылка скрыта следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами, или листьями. В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь  - пример дерева, в котором точно два листа.В следующих двух теоремах устанавливаются некоторые свойства деревьев. Теорема 1. Граф с  вершинами и  ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:
Доказательство. Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего. (1) и (2)  (3). Индукция по числу вершин. При  утверждение очевидно. При  в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве  вершин и, по предположению индукции,  ребра. Следовательно, в исходном дереве было ребро.(2) и (3) (1). Пусть в графе, не имеющем циклов, ребро, а его компонентами связности являются  , причем  состоит из  вершин,  . Каждая компонента является деревом, поэтому, как доказано выше, число ребер в равно  , а всего ребер в графе  . Значит,  и граф связен.(1) и (3) (2). Рассмотрим связный граф с ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем , а это противоречит доказанному выше.Теорема 2. Если  - дерево, то
Доказательство. Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины  и  . Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине ). Пусть  - последняя вершина этого совпадающего начала, а после в одном пути следует вершина  , а в другом - вершина  . Рассмотрим ребро  . Если его удалить из графа, то в оставшемся подграфе вершины и будут соединимыми - соединяющий их маршрут можно построить так: взять отрезок первого пути от до и к нему присоединить отрезок второго от до , взятый в обратном порядке. Но это означает, что ребро не является перешейком. Однако из теоремы 4 ссылка скрыта следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).Отметим, что единственный путь, соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл). |
.