Определение 1. Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах, и несвязными в противном случае.
Определение 2. Граф называется связным, если любые две его вершины связны, и несвязным в противном случае.
Пример 1. Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими? Вариантов таких компаний может быть два.
В первом случае мы имеем связный граф, во втором - несвязный.
Теорема 1. Связный граф G(X,T) представляет собой простой цикл тогда, и только тогда, когда каждая его вершина имеет степень 2.
Доказательство.
Необходимость. Пусть граф G(X,T) представляет собой простой цикл. Он является замкнутым простым путем. Из любой его вершины можно попасть в любую другую, не проходя ни через какую вершину два раза. Очевидно, что степень любой вершины такого графа равна 2.
Достаточность. Пусть граф G(X,T) связный и степень каждой его вершины равна 2. Любые две его вершины соединены путем. Возьмем произвольную вершину. Пойдем по одному из двух ребер, к которым принадлежит эта вершина. Мы попадем в следующую вершину, из которой выходит два ребра. По одному мы пришли. Двигаемся далее по второму ребру. Таким образом, все вершины графа будут пройдены и мы вернемся в исходную вершину. Путь замкнется. Следовательно, этот граф является циклом.
|
|
Определение 3. Ребро (xi, xj) называется мостом, если в графе G(X,T), полученном после удаления ребра (xi, xj), вершины xi и xj несвязны.
Пример 2.
В исходном графе ребро (x 3, x 5) является мостом.
Существует несколько признаков мостов:
1) Ребро (xi, xj) является мостом тогда, и только тогда, когда (xi, xj) является единственным путем, соединяющим вершины xi и xj.
2) Ребро (xi, xj) является мостом тогда, и только тогда, когда найдутся две вершины xk и xm, такие, что любой путь, соединяющий их, содержит вершины xi и xj.
3) Ребро (xi, xj) является мостом тогда, и только тогда, когда оно не принадлежит ни одному циклу.
Определение 4. Связный граф без циклов называется деревом.
Определение 5. Вершина дерева, имеющая степень 1, называется висячей.
По аналогии с генеалогическими деревьями вводятся родовые понятия для вершин.
Пример 3.
Вершина x 1 называется корневой, пути от нее называются ветвями. Вершина x 2 называется родительской по отношению к вершинам x 4, x 5, x 6 и прародительской по отношению к вершинам x 8, x 9. Вершины x 2 и x 3 называются дочерними к вершине x 1.
Пример 4. Кубок по настольному теннису разыгрывают 16 команд по олимпийской системе. Схему турнира можно изобразить деревом.
Любое ребро в дереве является мостом. Для каждой пары вершин дерева существует единственный соединяющий их путь.
|
|
Теорема 2. Дерево с n вершинами имеет n -1 ребро.