П. 8. Сетевые графы или графики

Решение.

Пример.

Найти число максимальных путей графа с матрицей смежности А порядка 4: .

Граф состоит из 4-х вершин и 3-х дуг: (х₁, х₂), (х₂, х₃), (х₃, х₄). Путь х₁ u₁ х₂ u₂ х₃ u₃ x₄, длина которого равна 3, является максимальной, следовательно, число максимальных путей равно 1.

Определение 47. Полный путь –это путь от начальной вершины х₁ до конечной х_n.

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

Теорема 9.Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.

Иногда встречаются графы, часть ребер которых ориентирована, а другая – нет. Такие графы называют смешанными. Смешанный граф можно превратить в ориентированный мультграф, если каждое его неориентированное ребро заменить двумя ориентированными и противоположно направленными: (а,b) и (b,а). Примером смешанного графа является сеть городских улиц, если на некоторых улицах установлено одностороннее движение, а на других – двустороннее.

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

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

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

Определение 50. Всякий намеченный комплекс работ, необходимых для достижения цели, называют проектом.

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

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

Определение 51. Изображение сети называется сетевым графиком.

Основные правила построения сетевого графика.

1. Каждую стрелку на ребре рисуют так, чтобы ее конец находился правее начала, по возможности горизонтально.

2. Строят без лишних пересечений.

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

4. Из всех вершин, кроме завершающей, должны выходить стрелки.

5. Не должно образовываться циклов.

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

Примеры правильного и неправильного построения сетевых графиков.

Определение 52. Путь в сети от исходного события до завершающего называют полным путем (L).

Определение 53. Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. (t(L)).

Пример.

Найти продолжительности путей L₁, L₂, L₃ в сетевом графике.