Пути и циклы в графе. Ориентированные графы. Взвешенные графы.

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

При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.

Циклом называется путь, в котором совпадают начало с концом.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией. На рисунке приведены примеры Эйлеровых линий.

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

Ориентированный граф — граф, рёбрам которого присвоено направление. На практике часто ориентированные графы используют для наглядного представления процесса и результата спортивных соревнований.

Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).

Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3,..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа. Доказательство Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, то и требовалось доказать. Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство. Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды. ч.т.д.

Закономерность 3. Число нечетных вершин любого графа четно.

Взвешенные графы.

Взвешенный граф – это граф, некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Числа-пометки носят названия вес, длина, стоимость. Длина пути во взвешенном графе – это сумма весов ребер (дуг), из которых состоит путь.

Дерево как частный случай представления графов.

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий.

Свойство 2. Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Теорема. Дерево с n вершинами имеет n — 1 ребро.

Доказательство: Для дерева — изолированной вершины n=1 и ребер 0, что соответствует теореме (n—1 = 1—1 = 0). Если из графа «дерева», не являющегося изолированной вершиной, удалить одно ребро, то получается два дерева с теми же вершинами. Для получения трех деревьев нужно удалить два ребра; для получения четырех деревьев — три ребра и т. д. Наибольшее количество деревьев из графа с n вершинами можно получить n (n изолированных вершин), чего можно достичь, удалив n—1 ребро. ч.т.д.