Тема 4. Элементы теории графов

⇐ ПредыдущаяСтр 5 из 27Следующая ⇒

Графы являются выразительным способом моделирования систем. Теория графов описывает важные для приложений методы анализа и синтеза систем.

Определение и примеры графов

Определение 4.1. Графом называется Г = á X , R ñ , где X — произвольное множество элементов, называемых вершинами, R ⊆ X × X = X 2— бинарное отношение между элементами множества X , т. е. R — некоторое множество пар вида ( xi, xj), где xi, xj∈ X .

Пары из R называются дугами графа, причем считается, что дуга ( xi, xj) имеет направление от xiк xj, т. е. от первого элемента в упорядоченной паре ко второму. При этом говорят, что дуга ( xi, xj) инцидентна вершинам xi, xj. Дуга вида ( xi, xj) называется петлей.

Граф Г1, составленный из части вершин и части дуг другого графа Г2, таких, что называется подграфом второго, и пишут: Г1⊆ Г2.

Последовательность дуг ( xi, xj); ( xj, xl); ...; (хт, хп), таких, что конец любой дуги кроме последней совпадает с началом следующей дуги, называется путем в графе. При этом будем предполагать, что все вершины дуг пути, кроме, возможно, первой и последней, различны. Число дуг пути называется его длиной. Путь обозначается L ( xi, xn), где вершины xi, xnназываются началом и концом пути, а остальные вершины — промежуточными.

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

Итак, граф — это вершины и дуги. Геометрически они изображаются следующим образом. Рассмотрим произвольное множество Q точек плоскости, мощность которого равна мощности множества X . Сопоставим любым образом взаимно-однозначно множества X и Q . Для каждой дуги ( xi, xj) графа найдется пара точек qiи qjиз Q . Соединим эти точки произвольной непрерывной кривой (дугой), направленной от qiк qj.

На плоскости появится рисунок, который является геометрическим изображением графа.

Если две вершины qi, qjсоединены дугами в оба направления, т. е. имеются обе дуги ( qi, qj) и ( qj, qi), то часто такие вершины соединяют одной линией (ребром) без направления. Ребро заменяет две дуги противоположного направления.

Рис . 4. 1. Циклический граф

Рис . 4. 2. Симметричный граф K 3, 3

Рис . 4. 3. Полный граф K 5

Определение 4.2. Граф Г = á X , R ñ , у которого бинарное отношение R — симметричное, называется симметричным (неориентированным). Все остальные графы называются несимметричными (ориентированными).

Пример 4. 1. Граф, изображенный на рис. 4.1, называется циклическим.

Пример 4. 2. Симметричный граф на рис. 4.2 обозначается K 3, 3изображен с использованием ребер без направлений.

Пример 4. 3. Симметричный граф называется полным, если любые две его вершины соединены между собой ребром. На рис. 4.3 изображен полный граф, обозначаемый K 5.

Часто возникает ситуация, когда две вершины требуется соединить произвольным числом дуг. Тогда используют более общее понятие, чем граф, мультиграф. Мулътиграфом называются два множества á X , U ñ и матрица В. Здесь X — множество т вершин, U — множество п дуг и матрица В размером т × п, называемая матрицей инцидентности. Матрица инцидентности показывает, какая дуга имеет какую вершину начальной, а какую конечной. В матрице инцидентности номера строк соответствуют номерам вершин, а номера столбцов — номерам дуг. Элемент bijматрицы инцидентности задается по формуле

Отметим, что любой граф можно задать как мультиграф с единичной кратностью дуг.

Примеры графов из прикладных областей.

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

Рис . 4. 4. Дерево

Рис . 4. 5. Транспортная сеть

Транспортная сеть. Это, например, сеть дорог, трубопроводная, железнодорожная, информационная и т. д. (рис.4.5). Вершины графа — города, аэропорты, железнодорожные станции, телефонные станции и т. д. Дуги графа — односторонние дороги, трубы, кабели, стекловолокно и т. д. на дугах задают нагрузки (скалярные или векторные), предварительно вводя направления в обе стороны для симметричных дуг. Нагрузками могут быть: пропускная способность дороги, стоимость проезда, протяженность, количество перевозимого груза (грузооборот) и т. д.

Граф смены состояний системы массового обслуживания (СМО ). Такой граф (рис.4.6) описывает процесс смены состояний системы. Это так называемый марковский процесс. Пусть, например, имеется парикмахерская, в которой три мастера и три кресла. Возможны следующие состояния этой системы:

q 0— в парикмахерской нет посетителей, все кресла свободны;

q 1— в парикмахерской один клиент, занято одно (любое) кресло;

q 2— в парикмахерской два клиента, занято два любых кресла;

q 3— в парикмахерской три клиента, все кресла заняты.

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

Рассмотрим процесс смены состояний данной СМО за время ∆ t (минута, час, смена).

Из q 1, например, есть три возможных перехода системы в другое состояние за время ∆ t :

Рис . 4. 6. Граф смены состояний СМО

1) переход в состояние q 0;

2) переход в состояние q 2;

3) переход в состояние q 1(система осталась в состоянии q 1).

Рассмотрим эти переходы. Переход в состояние q 0означает, что за время ∆ t единственного клиента обслужили, а другой не пришел.

Переход в состояние q 2свидетельствует о том, что за время ∆ t появился один новый клиент, а первый еще остался.

И наконец, система осталась в состоянии q 1— в парикмахерской лишь один клиент.

Сетевой график. Граф, описывающий некоторый технологический процесс (проект создания какой-либо системы), называется сетевым (рис. 4.7). Вершины графа — главные события процесса.

Рис . 4. 7. Сетевой график

Здесь событие q 0— начало выполнения проекта. Из вершины q 0дуги только выходят. Вершина графа q 6— событие завершения проекта. В вершину q 6дуги только входят.

Каждая дуга ( qiqj) соответствует некоторой операции (работе). Нагрузка на дуге означает длительность по времени данной операции. Жирной стрелкой выделен критический путь в сетевом графике от q 0до q 6.Среди всех путей из q 0 в q 6самый длительный по времени. Его длительность называется критическим временем. Это есть время выполнения всего проекта, т. е. минимальное время, за которое можно выполнить весь проект.

Связность графа

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

Каждой строке и каждому столбцу сопоставим номер вершины графа. Элементы матрицы а ijположим равными 1, если в графе имеется дуга ( qiqj), и 0, если такой дуги нет. Вернемся к примерам графов, приведенных в предыдущем параграфе.

В примере 4.1 матрица смежности будет иметь вид

В каждой строке и каждом столбце матрицы ровно по одной единице.

В примере 4.2 матрица будет симметричной:

В примере 4.3 имеем:

В данном графе нет «петель», все а ij= 0.

Ребро графа, инцидентное вершинам qi, qjв матрице смежности, удовлетворяет условию а ij= а ji= 1.

Структурный способ задания графа. Матрица смежности, соответствующая данному графу, может содержать много нулей. Хранить в памяти эти нули не имеет смысла. Поэтому граф можно задавать с помощью набора строчных записей (рис. 4.8).

Это означает, что в графе имеются следующие дуги из вершины qi: ( qiqj1), ( qiqj2), …, ( qiqjk).

Аналогичная строчная запись рассматривается для всех остальных вершин.

В примере 4.1 будем иметь пять строчных записей (рис. 4.9).

В примере 4.3 тоже пять строчных записей (рис. 4.10).

Рассмотрим важную характеристику графа, его связность.

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

По определению считаем, что все dij= 1.

Рис . 4. 8. Строчная запись

Рис . 4. 9. Строчная запись графа из примера 4.1

Рис . 4. 10. Строчная запись графа из примера 4.3

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒