Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Практика
Примеры решения типовых задач
Задание 1. Определить степени каждой вершины графа на рис. 1. Построить его дополнение.
Рисунок 1 – Граф
Решение. Степени вершин определяются количеством ребер, ей инцидентных. Поэтому: ; ; ; ; ; .
Дополнение графа строится следующим образом: из полного графа на 6-ти вершинах убираются те ребра, которые принадлежат графу . На рис. 2 ребра графа отмечены пунктиром.
Рисунок 2 – Граф
Рисунок 3 – Дополнение графа
Проверить правильность построения можно так: Сумма степеней одноименных вершин графа и его дополнения равна 5 (степень вершины графа ).
Задание 2. Построить матрицы смежности и инциденций для неориентированного графа на рис.4.
Рисунок 4 – Граф
Решение.
Строим матрицу смежности , строки и столбцы которой обозначаем вершинами графа. Для неориентированного графа она симметричная. Элемент матрицы смежности равен 1, если вершины и смежны, и 0 в противном случае. Так как граф простой (не имеет петель и кратных ребер), на главной диагонали расположены 0, а все элементы матрицы имеют значения 0 или 1. Сумма чисел по строке (и по столбцу) равна степени вершины.
Таблица 1 – Матрица смежности неориентированного графа
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
2 |
1 |
0 |
1 |
0 |
1 |
1 |
|
3 |
0 |
1 |
0 |
0 |
1 |
0 |
|
4 |
0 |
0 |
0 |
0 |
0 |
1 |
|
5 |
0 |
1 |
1 |
0 |
0 |
0 |
|
6 |
1 |
1 |
0 |
1 |
0 |
0 |
Матрица инциденций строится следующим образом: строки ее соответствуют вершинам, столбцы – ребрам графа . Элемент равен 1, если вершина инцидентна ребру, и 0 – в противном случае.
Таблица 2 – Матрица инциденций неориентированного графа
|
a |
b |
c |
d |
e |
f |
g |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
2 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
В каждом столбце должны находиться только 2 единицы. Сумма чисел по строке равна степени вершины.
Задание 3. Построить матрицы смежности и инциденций для ориентированного графа на рис. 5.
Рисунок 5 – Граф
Решение.
Строим матрицу смежности , строки и столбцы которой обозначаем вершинами графа. Для ориентированного графа она несимметричная. Элемент матрицы смежности равен 1, если из вершины в ведет дуга, и 0 в противном случае. Так как граф простой (не имеет петель и кратных ребер), на главной диагонали расположены 0, а все элементы матрицы имеют значения 0 или 1. Сумма чисел по строке равна полустепени исхода вершины, а по столбцу – полустепени захода вершины.
Таблица 3 – Матрица смежности ориентированного графа
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
0 |
1 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
0 |
0 |
0 |
1 |
|
5 |
0 |
1 |
1 |
0 |
0 |
0 |
|
6 |
1 |
0 |
0 |
0 |
0 |
0 |
Матрица инциденций строится следующим образом: строки ее соответствуют вершинам, столбцы – ребрам графа . Элемент равен 1, если вершина является началом дуги, (-1) – если вершина – конец дуги, и 0 – если вершины и дуга не инцидентны.
Таблица 4 – Матрица инциденций ориентированного графа
|
a |
b |
c |
d |
e |
f |
g |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
2 |
-1 |
1 |
0 |
-1 |
1 |
0 |
0 |
|
3 |
0 |
-1 |
-1 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
0 |
-1 |
-1 |
1 |
Сумма чисел по столбцу равна нулю.
Задание 4. По матрице смежности (табл. 5) построить граф и определить, является ли он ориентированным или неориентированным.
Таблица 5 – Матрица смежности графа
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
0 |
1 |
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
|
4 |
1 |
0 |
0 |
0 |
1 |
1 |
|
5 |
0 |
1 |
0 |
0 |
0 |
0 |
|
6 |
1 |
0 |
0 |
0 |
0 |
0 |
Решение.
Матрица смежности несимметричная, поэтому граф ориентированный. Количество вершин – 6. Строим граф. Из вершины 1 ведут дуги в вершины 2 и 3; из вершины 2 – в вершины 3 и 6; из вершины 3 – в вершину 4; из вершины 4 – в вершины 1, 5 и 6; из вершины 5 – в вершину 2; из вершины 6 – в вершину 1. Проверить правильность построения можно, посчитав полустепени исхода (сумма цифр по строке) и полустепени захода (сумма цифр по столбцу) для каждой вершины. Граф, соответствующий матрице смежности (табл. 5), изображен на рис. 5.
Рисунок 6 – Граф
Задание 5. По матрице инциденций (табл. 6) построить граф и определить, является ли он ориентированным или неориентированным.
Таблица 6 – Матрица инциденций графа
|
a |
b |
c |
d |
e |
f |
g |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
2 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
3 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
4 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
6 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
Решение.
В матрице инциденций нет значений (-1), потому можно сделать вывод о том, что граф неориентированный. Количество вершин равно 6, количество ребер – 7. Строим пустой граф на шести вершинах и соединяем их ребрами: ребро а соединяет вершины 1 и 4, ребро b – вершины 2 и 4, и т.д. Граф, соответствующий матрице инциденций (табл. 6), изображен на рис. 7.
Рисунок 7 – Граф
Задание 6. Определить, является ли для графа соответствующий маршрут цепью, простой цепью, циклом, простым циклом, если маршрут: :
Рисунок 8 – Граф
1) ;
2) ;
3) ;
4) ;
5) .
Решение. Согласно определению получим:
1) простой цикл (все вершины и ребра различны);
2) цикл (все ребра различны, а вершины нет);
3) простая цепь;
4) маршрут (есть одинаковые ребра и вершины);
5) простая цепь.
Задание 7. Для графов и на рисунке 9 выполнить операции объединения, пересечения и композиции и .
Рисунок 9 – Графы и
Решение.
В графе присутствуют все вершины и все дуги графов и . Так же, как в объединении множеств, повторяющиеся элементы используем один раз.
В графе присутствуют те вершины и те дуги графов и , которые есть и в графе и в графе . На рисунке 10 изображены результаты объединения и пересечения графов и .
Матрица смежности результирующего графа образуется поэлементным логическим сложением матриц смежности графов и .
Матрица смежности результирующего графа образуется поэлементным логическим умножением матриц смежности графов и .
Рисунок 10 – Объединение и пересечение графов и
Композиция графов строится следующим образом: выписываются все дуги графа и соответствующие им дуги графа , в результирующий граф включаются дуги , исключая повторяющиеся (в данном случае, дуга (1,3)):
|
(1,1) |
(1,3) |
(1,3) |
|
(1,1) |
(1,4) |
(1,4) |
|
(1,2) |
(2,1) |
(1,1) |
|
(2,3) |
(1,3) |
|
|
(2,3) |
– |
|
|
(2,4) |
(4,3) |
(2,3) |
|
(4,3) |
– |
Граф изображен на рис. 11. Матрица смежности графа получается умножением матрицы смежности графа на матрицу смежности графа .
Рисунок 11 – Граф
Композиция графов строится следующим образом: выписываются все дуги графа и соответствующие им дуги графа , в результирующий граф включаются дуги :
|
(1,3) |
– |
|
|
(1,4) |
(4,3) |
(1,3) |
|
(2,1) |
(1,1) |
(2,1) |
|
(1,2) |
(2,2) |
|
|
(4,3) |
– |
Результирующий граф изображен на рис. 12. Матрица смежности графа получается умножением матрицы смежности графа на матрицу смежности графа .
Рисунок 12 – Граф
Операция композиции не является коммутативной, графы и не изоморфны.
Задание 8. Определить число компонент связности в графе , если задан следующим образом:
1)
2)
3)
Решение. 1) Граф имеет три компоненты связности. В первую входят вершины , во вторую – , в третью – , так как вершины первой компоненты нельзя соединить цепью с вершинами компонент два и три, а вершины компонент два и три также нельзя соединить цепью.
2) Граф имеет две компоненты связности, в первую входят вершины , во вторую – .
3) Граф имеет четыре компоненты связности. В первую входят вершины , во вторую – , в третью – , в четвертую – .
Задание 9. Найти в графе все точки сочленения и мосты, если :
Рисунок 13 – Граф
Решение. Последовательно рассматриваем ребра графа, мысленно удаляя их из графа, только удаление ребра приводит к увеличению числа компонент связности, следовательно, является мостом. Аналогично поступаем с вершинами графа, и находим, что вершины 3 и 5 являются точками сочленения, так как удаление их из графа приводит к увеличению компонент связности.
Задание 10. Для графа найти расстояние от точки до всех вершин графа , где :
Рисунок 14 – Граф
Решение. Расстояние от точки будем искать согласно алгоритму.
1. ,
2. ,
3. , просмотрели все вершины графа, отсюда , .
Задание 11. Найти расстояние от заданной точки до заданной точки и найти все геодезические цепи , если граф задан следующим образом:
Рисунок 15 – Граф
Решение. 1. , 2. , 3. , 4. . Следовательно, . Геодезические цепи : ; ; ; .
Задание 12. Найти Эйлерову цепь в неориентированном графе , изображенном на рис. 10.
Решение. Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа − согласно утверждению, для существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе ровно 2 вершины нечетной степени.
Рисунок 16.
В рассматриваемом графе нечетные степени имеют вершины и (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 17, получаем граф :
Рисунок 17.
Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы так, чтобы хотя бы один из них начинался или кончался на вершинах или .
Пусть цикл составят ребра, проходящие через следующие вершины: . Согласно алгоритму, удаляем из все ребра, задействованные в цикле . Теперь граф будет таким, как показано на рис. 18.
Составляем следующий цикл : . Граф после удаления ребер, составляющих цикл , изображен на рис. 19.
|
Рисунок 18 |
Рисунок 19 |
Очевидно, что последний цикл будет состоять из v3 v5 v1|v3, где последнее ребро, соединяющее вершины и – фиктивно. После удаления ребер, составляющих цикл , в графе G не останется ни одного ребра.
Теперь по общим вершинам склеиваем полученные циклы. Поскольку и имеют общую вершину , то, объединяя их, получим следующий цикл: . Теперь склеим получившийся цикл с циклом : . Удаляя фиктивное ребро, получаем искомую Эйлерову цепь: .
Задание 13. Установить изоморфность графов G1 и G2, приведенных на рис.20.
Рисунок 20.
Запишем элементы и с соответствующими им парами и определим частичную подстановку, проведя ребра 1 и 2, показанные на рис. 21. Затем последовательно строим ребра 3-7, используя отображения и и частичные подстановки. В результате получаем подстановку
которая удовлетворяет условию: для каждой вершины из существует вершина из , для которой и и существует подстановка, переводящая граф в граф . Следовательно, графы и изоморфны.
Обобщенный алгоритм распознавания изоморфизма графов пригоден при решении большинства практических задач, за исключением тех случаев, когда рассматриваемые графы имеют одинаковое число вершин и все пары полустепеней исхода и захода каждой вершины одинаковы.
Рисунок 21.
Задание 14. Найти эксцентриситеты каждой вершины графа (рис. 22), радиус графа, его диаметр, центр, окружение и обхват.
Рисунок 22.
Решение. Эксцентриситет – наименьшее расстояние от вершины до наиболее удаленной от нее вершины графа. Диаметр – наибольший из эксцентриситетов, радиус – наименьший. Окружение – длина наименьшего простого цикла графа, обхват – длина наибольшего простого цикла. Центр находится в вершине (вершинах), на которых достигается минимальный эксцентриситет. Таким образом, для графа :
; ; ; центр графа – вершина 4. Окружение, как и обхват равны 3 (в графе всего один цикл).
Задание 15. Используя алгоритм Робертса-Флореса найти в графе гамильтонов цикл.
Решение. Алгоритм начинается с построения матрицы , где элемент есть -я вершина (допустим, ), для которой в графе существует дуга . Вершины можно упорядочить произвольно, образовав элементы -го столбца матрицы . Число строк матрицы будет равно наибольшей полустепени исхода вершины.
Рисунок 23 – Граф
Матрица М:
|
a |
b |
c |
d |
e |
f |
|
|
1 |
b |
c |
a |
c |
c |
a |
|
2 |
– |
e |
d |
f |
d |
b |
|
3 |
– |
– |
– |
– |
– |
c |
Все вершины по очереди записываем во множество .
Поиск всех гамильтоновых циклов производится так (вершина берется в качестве отправной вершины):
|
№ |
Множество |
Комментарии |
|
1 |
Добавляем первую возможную вершину в столбце (вершину ). |
|
|
2 |
Добавляем первую возможную вершину в столбце (вершину ). |
|
|
3 |
Первая возможная вершина в столбце не является возможной (), добавляем следующую вершину в столбце (вершину ). |
|
|
4 |
Добавляем вершину . |
|
|
5 |
В столбце нет возможных вершин. Возвращение. |
|
|
6 |
В столбце нет возможных вершин. Возвращение. |
|
|
7 |
В столбце нет возможных вершин. Возвращение. |
|
|
8 |
Добавляем вершину . |
|
|
9 |
Добавляем вершину . |
|
|
10 |
Добавляем вершину . |
|
|
11 |
Добавляем вершину . |
|
|
12 |
Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение. |
|
|
13 |
Возвращение. |
|
|
14 |
Возвращение. |
|
|
15 |
Добавляем вершину . |
|
|
16 |
Добавляем вершину . |
|
|
17 |
Добавляем вершину . |
|
|
18 |
Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение. |
|
|
19 |
Возвращение. |
|
|
20 |
Возвращение. |
|
|
21 |
Возвращение. |
|
|
22 |
Возвращение. |
|
|
23 |
Возвращение. |
|
|
24 |
Конец поиска. |
В результате получаем два гамильтоновых цикла (рис. 24).
Рисунок 24 – Гамильтоновы циклы в графе
Задание 16. Найти хроматическое число графа (рис. 25).
Рисунок 25.
Решение. 1. Вычисляем степени всех вершин графа .
2. Просматриваем все вершины графа в порядке невозрастания степеней.
3. Окрашиваем в цвет №1 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №1.
Рисунок 26.
4. Окрашиваем в цвет №2 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №2.
Рисунок 27.
5. Окрашиваем в цвет №1 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №1.
Рисунок 28.
Таким образом, получили правильную раскраску графа .
Задание 17. Используя алгоритм Дейкстры, в графе найти кратчайшие расстояния от вершины 1 до всех остальных вершин.
Рисунок 29 – Граф
Решение. Строим таблицу (см. лекции). На первом шаге присваиваем вершине 1 метку 0*, а всем остальным вершинам – . .
|
1 |
0* |
||||||||
|
2 |
|||||||||
|
3 |
|||||||||
|
4 |
|||||||||
|
5 |
|||||||||
|
6 |
|||||||||
|
7 |
|||||||||
|
8 |
|||||||||
|
9 |
На втором шаге выписываем во второй столбец временные метки вершин (соответствующие весу дуги), в которые из 1-й вершины ведет дуга. Если дуги из вершины 1 нет, оставляем метку .
.
;
;
.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 2.
.
|
1 |
|||||||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
|||||||||
|
4 |
7 |
||||||||
|
5 |
7 |
||||||||
|
6 |
|||||||||
|
7 |
|||||||||
|
8 |
|||||||||
|
9 |
Третий шаг: проделываем все операции для вершины 2:
.
;
;
.
Метки для остальных вершин оставляем прежними.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 3.
.
|
1 |
2 |
||||||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
|||||||
|
5 |
7 |
7 |
|||||||
|
6 |
14 |
||||||||
|
7 |
|||||||||
|
8 |
|||||||||
|
9 |
Четвертый шаг: проделываем все операции для вершины 3:
.
;
.
Метки для остальных вершин оставляем прежними. Метка для вершины 6 уменьшилась. Записываем меньшую.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 4.
.
|
1 |
2 |
3 |
|||||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
7* |
||||||
|
5 |
7 |
7 |
7 |
||||||
|
6 |
14 |
11 |
|||||||
|
7 |
|||||||||
|
8 |
|||||||||
|
9 |
Пятый шаг: проделываем все операции для вершины 4:
.
;
.
Для вершины 2 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 5.
.
|
1 |
2 |
3 |
4 |
||||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
7* |
||||||
|
5 |
7 |
7 |
7 |
7* |
|||||
|
6 |
14 |
11 |
11 |
||||||
|
7 |
10 |
||||||||
|
8 |
15 |
||||||||
|
9 |
Шестой шаг: проделываем все операции для вершины 5:
.
;
;
;
;
Для вершины 4 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними. Метки для вершин 6, 7, 8 уменьшились. Записываем меньшие.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 6.
.
|
1 |
2 |
3 |
4 |
5 |
|||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
7* |
||||||
|
5 |
7 |
7 |
7 |
7* |
|||||
|
6 |
14 |
11 |
11 |
9* |
|||||
|
7 |
10 |
9 |
|||||||
|
8 |
15 |
11 |
|||||||
|
9 |
16 |
Седьмой шаг: проделываем все операции для вершины 6:
.
;
Метки для остальных вершин оставляем прежними.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 7.
.
|
1 |
2 |
3 |
4 |
5 |
6 |
||||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
7* |
||||||
|
5 |
7 |
7 |
7 |
7* |
|||||
|
6 |
14 |
11 |
11 |
9* |
|||||
|
7 |
10 |
9 |
9* |
||||||
|
8 |
15 |
11 |
11 |
||||||
|
9 |
16 |
12 |
Восьмой шаг: проделываем все операции для вершины 7:
.
;
Метки для остальных вершин оставляем прежними.
Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 8.
.
Для вершины 9 метка на девятом шаге не меняется, поэтому все результаты записываем в таблицу.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
1 |
0* |
||||||||
|
2 |
6* |
||||||||
|
3 |
7* |
||||||||
|
4 |
7 |
7 |
7* |
||||||
|
5 |
7 |
7 |
7 |
7* |
|||||
|
6 |
14 |
11 |
11 |
9* |
|||||
|
7 |
10 |
9 |
9* |
||||||
|
8 |
15 |
11 |
11 |
11* |
|||||
|
9 |
16 |
12 |
12 |
12* |
Таким образом, минимальные расстояния от вершины 1 ко всем вершинам графа равны:
Задание 18. Найти максимальный поток в транспортной сети, изображенной на рисунке 30.
Рисунок 30 – Транспортная сеть.
Решение. Для нахождения максимального потока воспользуемся алгоритмом Форда-Фалкерсона. Найдем суммарную пропускную способность дуг, выходящих из истока (вершина 1) и суммарную пропускную способность дуг, входящих в сток (вершина 14).
;
.
Значит, максимальный поток в этой сети не может превосходить 31.
Далее разбиваем сеть на простые непересекающиеся цепи (произвольным образом). В данном случае удобно сделать это следующим образом:
1 – (1, 2, 6, 10, 14);
2 – (1, 3, 7, 11, 14);
3 – (1, 4, 8, 12, 14);
4 – (1, 5, 9, 13, 14).
Для каждой из цепей находим максимальный поток, исходя из пропускных способностей дуг: например, в первой цепи – (1, 2, 6, 10, 14) – минимальная пропускная способность у дуги (2,6) – 6, поэтому поток по этой дуге не может превышать 6-ти.
На рис. 31 показана сеть, в которой синим цветом обозначены простые цепи, а рядом с пропускными способностями дуг обозначено значение потока. Дуги, у которых пропускная способность равна потоку, называются насыщенными.
На первой итерации получаем суммарный поток: 6+5+6+4=21.
На следующих итерациях будем пытаться увеличить величину потока.
Рисунок 31 – первая итерация.
Для этого выбираем другие цепи, в которых нет насыщенных дуг.
На рисунках 32 – 34 изображены последующие итерации. (Над дугой рядом с пропускными способностями дуг через «;» обозначаем новое значение потока).
Вторая итерация: выбираем цепь, по которой можно увеличить поток: (1, 2, 3, 6, 10, 14). Поток можно увеличить на 1 (т.к. пропускная способность дуги (6, 10) равна 7).
Рисунок 32– вторая итерация.
На второй итерации поток увеличился на 1, и стал равен 22.
Третья итерация: выбираем цепь (1, 3, 8, 7, 10, 14). По этой дуге мы можем пропустить поток величиной 2 (т.к. пропускная способность дуги (3,8) равна 2). Получаем суммарный поток, равный 22+2=24. На рис. 33 изображена сеть с потоком, равным 24.
Рисунок 33 – третья итерация.
Четвертая итерация: выбираем цепь (1, 4, 9, 13, 14). По этой дуге мы можем пропустить поток величиной 1 (т.к. пропускная способность дуги (9, 13) равна 5). Получаем суммарный поток, равный 24+1=25. На рис. 34 изображена сеть с потоком, равным 25.
Рисунок 34 – четвертая итерация.
Вопросы
Задания
1. Для графа G=(V,E), где V={a,b,c,d,e,f}, E={ad,ae,af,bd,be,cd,ce,cf}:
а) выполнить задания: графически, матрицами смежности и инциденций, списком ребер;
б) взяв V '= {a,c,e,f}, задать подграф G' графа G;
в) взяв Е'= {ad,bd,cd,cf}, задать суграф G" графа G;
г) выяснить, какие графы являются частью графа G и какой:
G1=(V1, E1), V1={a,c,f} E1={af,cf},
G2=(V2, E2), V2={a,e,f} E2={ae,ef},
G3=(V3, E3), V3={a,c,e,f} E3={af,be,af,ef},
G4=(V4, E4), V4={a,b,c,d,e,f} E4={ad,bd,be},
G5=(V5, E5), V5={a,b,c,d,e,f} E5={ad,af,bc};
д) построить для графа G.
2. Задать графы матрицей инциденций, предварительно пронумеровав элементы множеств V и Е. Задать матрицей смежности дополнительные к данным графам графы. Определить степени вершин графа и его дополнения.
3. Построить все графы на пяти, четырех и трех вершинах.
4. Определить количество циклов в графах:
5. Определить точки сочленения (разделяющие множества) и мосты следующих графов:
6. Найдите количество центров деревьев:
7. Найдите эйлеровы графы и укажите не менее двух эйлеровых циклов в них:
8. Найдите хроматическое число и хроматический индекс графов:
9. Постройте 3 планарных и 3 не планарных графа с |V|=6 и |E|=12.
10. Какое наименьшее число вершин нужно удалить, чтобы граф стал планарным:
Какое наименьшее число ребер нужно удалить, чтобы эти графы стали планарными.
11. Построить минимальный остов графа:
12. Найти радиус, диаметр, окружение и обхват графа.
13. Сколько в графе маршрутов длины 3?
14. Найти в графе компоненты сильной связности.
15. Найти кратчайшие расстояния от вершины 1 ко всем вершинам графа.
16. Найти максимальный поток в транспортной сети.