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

Дерево . На рис. 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