Глава 2. Алгоритмы на графах §1. Основные понятия теории графов.

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

Графы представляют собой распространенные структуры в математике и информатике, и алгоритмы для работы с графами очень важны. Имеются сотни интересных вычислительных задач, сформулированных с использованием графов.

Определение 1. Неориентированным графом называется совокупность непустого множества – множества вершин и множества - множества ребер, т.е. неупорядоченных пар различных элементов множества .

Число вершин графа обозначается .

Число ребер графа обозначается .

Если - вершины , т. е. и – соединяющее их ребро, то есть , тогда вершина и ребро называются инцидентными. Два ребра, инцидентных одной вершине, называются смежными ребрами. Две вершины, инцидентные одному ребру, называются смежными вершинами.

Количество ребер, инцидентных вершине , называется степенью (валентностью) вершины и обозначается .

Определение 2. Ориентированным графом (орграфом) называется совокупность непустого множества – множества узлов и множества E – множества дуг, т.е. упорядоченных пар различных элементов множества .

В орграфе число дуг, исходящих из вершины v называется полустепенью исхода и обозначается . Число дуг, входящих в v – полустепенью захода и обозначается .

Граф наглядно изображают диаграммой: вершины – точками, ребро – отрезком . Для орграфа узлы изображают точками, дуга - стрелкой от к .

Рис 1. а) граф , б) орграф

Определение 3. Псевдографом (псевдоорграфом) называется совокупность непустого множества и множества неупорядоченных (упорядоченных) пар элементов из необязательно различных.

Ребро (дуга )псевдографа (псевдоорграфа) назывется петлей.

Определение 4. Мультиграфом (мультиорграфом) называется совокупность непустого множества и набора неупорядоченных (упорядоченных) пар элементов из , причем одна и та же пара может входить в набор несколько раз. Такое ребро (дугу) называют кратным ребром (дугой).

Рис 2. а) псевдограф, – петля, б) мультиграф, - кратное ребро.

Определение 5. Если задана функция и/или , то множество называется множеством меток, а граф (орграф) называется помеченным или взвешенным, нагруженным.

Рис 3. Помеченный орграф. Функция , ,

Далее, по умолчанию, термин «граф », означает неориентированный непомеченный граф без петель и кратных ребер.

Определение 6. Граф (орграф) называется подграфом графа (орграфа) и обозначается , если и .

Если , то называется остовным подграфом графа .

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

Определение 7. Маршрутом в графе (орграфе) называется последовательность вершин (узлов) , такая, что ; .

Если , маршрут называется замкнутым, в противном случае – открытым. Длиной маршрута называется количество ребер в нем (учитывая повторения).

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

Циклом называется замкнутая цепь. Простым циклом – замкнутая простая цепь. Граф без циклов называется ациклическим.

В орграфе цепь называется путем, а цикл контуром.

В графе (орграфе) расстоянием между вершинами (узлами) и называется наименьшая длина цепи (пути), соединяющей и , а сама такая цепь (путь) называется геодезической.

Пример.

1. – маршрут, но не цепь.

2. – цепь, но не простая цепь.

3. – простая цепь.

4. – цикл, но не простой цикл.

5. - простой цикл.

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

Связный ациклический граф называется свободным деревом (деревом без корня).