Начальные понятия теории графов (стр. 5 )

Установим некоторые простые свойства маршрутов.

Теорема 1. В любом маршруте, соединяющем две различные вершины, содержится простой путь, соединяющий те же вершины. В любом цикле, проходящем через некоторое ребро, содержится простой цикл, проходящий через это ребро. Доказательство. Пусть - маршрут. Если все его вершины различны, то это уже простой путь. В противном случае, пусть , . Тогда последовательность , полученная из этого маршрута удалением отрезка последовательности от до , тоже является маршрутом. Новый маршрут соединяет те же вершины и имеет меньшую длину. Продолжая действовать таким образом, после конечного числа "спрямлений" получим простой путь, соединяющий и . Второе утверждение теоремы доказывается аналогично.

Отметим, что в формулировке теоремы 1 нельзя заменить слово "цикл" словами "замкнутый маршрут". Действительно, если - ребро графа, то последовательность - замкнутый маршрут, проходящий через это ребро, но никакого цикла в нем нет.

Теорема 2. Если в графе степень каждой вершины не меньше , то в нем есть цикл. Доказательство. Найдем в графе простой путь наибольшей длины. Пусть это . Вершина смежна с , а так как ее степень не меньше двух, то она смежна еще хотя бы с одной вершиной, скажем, с . Если бы была отлична от всех вершин пути, то последовательность была бы простым путем большей длины. Следовательно, - это одна из вершин пути, , причем . Но тогда - цикл.

Связность и компоненты

Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины. Заметим, что ввиду теоремы 1 можно в этом определении заменить слово "маршрут" словами "простой путь".

Для произвольного графа определим на множестве вершин отношение соединимости: вершина соединима с вершиной , если существует соединяющий их маршрут. Легко видеть, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются областями связности, а порождаемые ими подграфы - компонентами связности графа. В связном графе имеется только одна компонента связности - весь граф. Компоненты связности можно определить также как максимальные по включению связные подграфы данного графа.

У графа на рис. 2.2 имеется четыре области связности - , , , .

Рис. 2.2.

Вершина называется шарниром (или точкой сочленения), если при ее удалении число компонент связности увеличивается. У графа на рис. 2.2 имеется четыре шарнира - это вершины , , , .

Ребро, при удалении которого увеличивается число компонент связности, называется перешейком. Перешейками графа, изображенного на рис. 2.2, являются ребра , , , , .

Легко доказываются следующие свойства шарниров и перешейков:

Теорема 3.Вершина является шарниром тогда и только тогда, когда в графе имеются такие отличные от вершины и , что любой путь, соединяющий и , проходит через .

Теорема 4. Ребро является перешейком в том и только том случае, если в графе нет простого цикла, содержащего это ребро.

Метрические характеристики графов

Расстоянием между двумя вершинами графа называется наименьшая длина пути, соединяющего эти вершины. Расстояние между вершинами и обозначается через . Если в графе нет пути, соединяющего и , то есть эти вершины принадлежат разным компонентам связности, то расстояние между ними считается бесконечным.

Функция обладает следующими свойствами:

, причем тогда и только тогда, когда ; ; (неравенство треугольника).

В математике функцию двух переменных, определенную на некотором множестве и удовлетворяющую условиям 1 - 3, называют метрикой, а множество, на котором задана метрика, - метрическим пространством. Таким образом, множество вершин любого графа можно рассматривать как метрическое пространство.

Расстояние от данной вершины до наиболее удаленной от нее вершины называется эксцентриситетом вершины и обозначается через . Таким образом,