Файл: 1 Кодирование текстовых и символьных данных.doc

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

Маршрут называется циклическим, если . Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Число ребер в маршруте — длина маршрута. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа. Длина всякого цикла не менее трех в графе без петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.

Важным понятием теории графов является связность. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.

Р
ис. 1.14. Граф

В подавляющем большинстве случаев граф задается матрицей. Для расчетов на ЭВМ это единственный способ. Наиболее часто граф задают с помощью матриц смежности и инциденций.

Рассмотрим изображенный на рис. 1.14 граф. Как для орграфов, так и для неориентированных графов можно определить матрицу смежности вершин. Это квадратная матрица



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

---

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

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

.

Строки матрицы инциденций называют векторами инциденций графа . Матрица инциденций



также однозначно определяет структуру графа.

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

Рассмотрим связный граф

---

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

(1.13.6)

называется эксцентриситетом вершины . Максимальный из всех эксцентриситетов вершин называется диаметром графа и обозначается , т. е.

. (1.13.7)

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через :

. (1.13.8)

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

Рис. 1.15. Центр графа

В
ершина центральная, если . Множество всех центральных вершин графа называется его

---

центром. Центром может быть единственная вершина графа или несколько вершин. На рис. 1.15 , , . Таким образом, . Периферийные вершины и , диаметральные цепи и , центральная вершина .

---