 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Такая последовательность ребер, по которой можно проложить маршрут между этими вершинами
|
|
При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
рис.9а;б
Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.10)
рис.10 (кружком обведены висячие вершины)
Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
Этим свойством пользуются при нахождении всех предков в генеалогическом дереве, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.
Свойство 2. Всякое ребро в дереве является мостом.
Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.
Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.
Доказательство:
Очевидно, что данный граф связен. Предположим, что в нем есть цикл. Тогда любые две вершины этого цикла соединено, по крайней мере, двумя простыми путями. Получили противоречие, а значит, наше предположение неверно.
*Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.
ЛЕММА (о висячей вершине) В каждом дереве есть висячая вершина.
Доказательство:
Рассмотрим произвольную вершину дерева и пойдём по любому выходящему из неё ребру в другую вершину. Если из новой вершины больше рёбер не выходит, то мы остаёмся в ней, а противном случае, идём по любому другому ребру дальше. Понятно, что в этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие обязательно должно закончится. Но закончиться оно может только в висячей вершине. Лемма доказана.
ТЕОРЕМА. В дереве число вершин на одну больше числа ребер.
Доказательство:
Из условия теоремы граф – дерево. У него есть висячая вершина. Удалим её и выходящее из нее ребро. Оставшийся граф также дерево. У него есть висячая вершина, которую также удалим. Проделав эту операцию n-1 раз, получим граф, состоящий из одной вершины. Т. к. удалялось по одному ребру, то вначале их было n-1.
Дата публикования: 2015-11-01; Прочитано: 755 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
