Теория графов

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

. Считая граф сетевым, определить его показатели:

критический путь;

ранние и поздние сроки свершения событий;

ранние и поздние сроки начала и окончание работ;

резервы свершения событий и выполнения работ.

Решение:

Рисунок 4.2 - Граф задания

. Анализ структуры графа

Граф, представленный на рисунке 4.2 не является эйлеровым, т.к. в нём не существует эйлерова цикла, т.е. данный граф нельзя нарисовать, не отрывая руки от бумаги и не повторяя линий. В этом графе не существует эйлерова цикла, в который бы входили все ребра графа без повторений.

Граф называется связным, если две любые его вершины связаны хотя бы одной цепью. Данный в задании граф - связный. Его необходимо разбить на два несвязных графа произвольным образом. Разобьем граф, изображенный на рис. 4.2, на два несвязных графа путём удаления наиболее загруженных вершин и инцидентных им дуг.

Рисунок 4.3 - Несвязные графы, полученные из графа задания.

Мы разбили граф на два несвязных путём удаления вершин 4, 6 и 7 и инцидентных им дуг.

Далее путём удаления наименее загруженных дуг избавимся от циклов и построим дерево графа.

Цикл - цепь, вершины начала и конца которой совпадают.

Цепь - маршрут, в котором все дуги попарно различны (нет двух узлов, соединённых различными дугами).

В заданном графе присутствует очень много циклов. Избавимся от них путём удаления наименее загруженных дуг.

Рисунок 4.4 - Граф, не имеющий циклов, полученный из графа задания.

Дерево - связный неориентированный граф, не содержащий циклов.

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

Точка сочленения - вершина графа, удаление которой повышает число компонентов связности. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей дуг. Компонент связности графа - это его связный подграф.

Построим этот граф, опираясь на граф, изображенный на рис. 4.4.

Рисунок 4.5 - Дерево графа

Удаление вершины 5 из графа, представленного на рис. 4.5, превращает связный граф в два его компонента связности.

. Матрицы смежности и инциденций

Матрицей смежности вершин неориентированного графа, состоящего из n вершин, называется матрица А размера nхn, элементы которой определяются следующим образом:

Матрица смежности для неориентированного графа задания.

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

Матрицей инцидентности ориентированного графа с вершинами и дугами (ребрами) называется прямоугольная матрица размера , элементы которой определяются следующим образом: