ДМ Практикум
.pdf
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 0 0 0 0 0 0 |
|||||||
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
||||||||
A(G)= |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
. |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
|
||||||||
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
А) Контрольные вопросы
7.1Приведите примеры графов:
а) с пятью вершинами и пятью ребрами; б) с пятью вершинами и тремя ребрами; в) с тремя вершинами и пятью ребрами.
7.2Вычислите, сколько существует простых графов с четырьмя вершинами.
7.3Докажите, что сумма степеней вершин графа равна удвоенному числу его ребер.
7.4Для полного графа K4 выполните операции: а) удаление ребра (v1,v2 ) ;
б) удаление вершины v1 ;
в) добавление вершины v5 и добавление ребра (v1,v5 ) ;
г) отождествление вершин v1,v2 ;
д) стягивание ребра (v1,v2 ) ;
е) размножение вершины v1 ;
к) расщепление вершины v1 ;
и) разбиение ребра (v1,v2 ) .
7.5Приведите пример н-графа с пятью вершинами, имеющего а) одну компоненту связности; б) две компонент связности; в) пять компонент связности.
7.6Приведите пример орграфа, имеющего четыре вершины и являющегося а) сильно связным; б) односторонне связным; в) слабо связным.
7.7Докажите, что следующие утверждения эквивалентны: а) граф является деревом;
б) граф связный и число его ребер на единицу меньше числа вершин; в) любые две вершины графа соединяет единственная простая цепь.
7.8Изобразите на рисунке все неизоморфные остовные деревья полного гра- фа K4 .
61
7.9Докажите, что цикломатическое число γ (G) графа можно вычислить по формуле: γ (G) = m − n + k , где m - число ребер, n - число вершин, k - число компонент связности графа G .
Б) Задачи и упражнения
7.10Для графов G1 , G2 , заданных на рисунке 7.4, найдите: а) матрицу смежности ;
б) матрицу инцидентности;
в) степени (полустепени) вершин;
Рисунок 7.4
7.11Графы G1 , G2 заданы матрицами смежности. а) нарисуйте графы;
б) найдите их матрицы инцидентности;
в) найдите степени (полустепени) вершин графов.
|
|
0 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
||
|
|
1 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
||
|
|
0 |
1 |
0 |
1 |
1 |
0 |
|
|
|
1 |
0 |
0 |
0 |
1 |
0 |
|
A(G ) = |
0 |
1 |
1 |
2 |
0 |
0 |
; |
A(G2 ) = |
0 |
0 |
0 |
1 |
0 |
1 |
. |
||
1 |
|
|
|
|
|
||||||||||||
|
|
1 |
0 |
1 |
0 |
2 |
0 |
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 0 0 0 1 0 |
||||||||
7.12 Для графа G , заданного на рисунке 7.5,
найдите: |
|
|
а) |
матрицу смежности; |
|
б) |
матрицу инцидентности; |
|
в) |
степени вершин; |
|
г) |
число компонент связности; |
|
д) |
цикломатическое число. |
Рисунок 7.5 |
62
7.13В заданном матрицей смежности орграфе найдите компоненты сильной связности:
а)
в)
д)
|
|
1 |
1 |
|
0 |
0 |
0 |
1 |
|
|
|
|
|
1 |
1 1 |
0 |
0 |
0 |
|
|
|||
|
|
0 |
0 |
|
1 |
1 |
1 |
0 |
|
|
|
A(G) = |
0 |
0 |
|
1 |
1 |
0 |
0 |
; |
|
||
|
|
|
|
|
|||||||
|
|
0 |
0 |
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
0 |
0 |
0 |
1 |
|
|||
|
|
0 |
1 |
|
0 |
0 |
0 |
0 |
|
||
|
|
1 |
0 1 |
0 |
0 |
0 |
|
||||
|
|
0 |
0 |
|
0 |
1 |
0 |
0 |
|
|
|
A(G) = |
0 |
1 |
|
1 |
1 |
0 |
0 |
; |
|
||
|
|
|
|
|
|||||||
|
|
1 |
0 |
|
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
0 |
0 |
0 |
0 |
|
|||
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
A(G) = |
1 0 0 1 1 0 0 0 ; |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
|
0 1 1 0 0 0 0 1 |
||||||||||
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
б)
г)
е)
|
|
0 |
1 |
0 |
0 |
0 |
0 |
||
|
|
0 0 0 |
1 |
0 |
0 |
||||
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
|
A(G) = |
0 |
0 |
0 |
0 |
0 |
1 |
; |
||
|
|
|
|||||||
|
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|||
|
|
0 |
0 |
1 |
0 |
0 |
1 |
||
|
|
0 0 1 |
1 |
0 |
0 |
||||
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
|
A(G) = |
0 |
0 |
0 |
0 |
0 |
1 |
; |
||
|
|
|
|||||||
|
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
0 |
|||
|
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
|
0 0 1 |
1 |
0 |
0 |
0 |
|||
A(G) = 0 0 0 0 0 0 0 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
||||||||
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0
0
0
00 .
1
1
1
7.14Сеть радиовещания состоит из 5 передающих станций, ее структура пока- зана на рисунке 7.6 а (масштаб: 1 клетка=1 км). Координационное рас- стояние равно 4 км, рабочие частоты всех станций одинаковы. Постройте граф сети и задайте его матрицей смежности.
7.15Для радиопокрытия города N установлено 8 базовых станций (рисунок 7.6 б, масштаб: 1 клетка=1,5 км). Координационное расстояние равно 9
км, рабочие частоты станций следующие: f1 = f4 = f7 , f2 = f3 = f6 , f5 = f8 . Постройте граф сети и задайте его матрицей смежности.
7.16Структура сети радиовещания показана на рисунке 7.7 а. Радиус зоны об- служивания равен 38 км, координационное расстояние – 114 км. Опреде- лите, будут ли указанные станции оказывать взаимные влияния друг на друга, постройте граф сети и найдите его матрицу смежности.
63
а) |
б) |
Рисунок 7.6
7.17В городе N установлены 15 базовых станций (рисунок 7.7 б). Радиус зон покрытия базовых станций равен 3,5 км, координационное расстояние – 18,2 км. Определите, будут ли станции оказывать взаимные влияния друг на друга, постройте граф сети и матрицу смежности.
а)
б)
Рисунок 7.7
64
7.18 Выясните, какие из графов на рисунке 7.8 являются изоморфными:
|
|
|
|
|
|
|
Рисунок 7.8 |
|
В) Тестовые задания (укажите единственный верный ответ) |
||||||||
7.19 Матрица |
смежности |
A(G) н-графа, изображенного на рис. 7.9, имеет |
||||||
вид… |
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
1 |
|
|
|
|
а) |
1 |
0 |
1 |
0 |
|
; |
Рисунок 7.9 |
|
|
1 |
0 |
1 |
|
|
|||
|
2 |
|
|
|
|
|||
|
1 |
0 |
1 |
2 |
|
|
|
|
|
0 |
1 |
1 |
1 |
|
|
|
|
б) |
1 |
0 |
1 |
0 |
|
; |
|
|
|
1 |
0 |
1 |
|
|
|
||
|
1 |
|
|
|
|
|||
|
1 |
0 |
1 |
1 |
|
|
|
|
|
0 1 2 1 |
|
0 1 1 1 |
|||||
в) |
1 0 1 0 |
; |
1 0 1 0 |
|
||||
|
|
|
|
|
г) |
. |
||
|
2 1 0 1 |
|
1 1 0 1 |
|||||
|
1 0 1 1 |
|
1 0 1 2 |
|||||
65
7.20 Матрица смежности A(G) орграфа, изображенного на рис.7.10, име-
ет |
вид… |
|
|
|
|
|
0 |
1 |
1 |
0 |
|
|
а) 0 0 1 |
0 |
; |
||
|
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
|
0 |
1 |
2 |
1 |
|
|
1 |
0 |
1 |
0 |
|
; |
б) |
1 |
0 |
1 |
|
|
2 |
|
|
|||
1 |
0 |
1 |
2 |
|
|
0 |
1 |
2 |
0 |
|
0 1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
; |
0 |
0 |
1 |
0 |
в) |
|
0 |
|
г) |
0 |
0 |
. |
|
2 0 |
1 |
|
1 |
1 |
||||
1 |
0 |
0 |
2 |
|
1 |
0 |
0 |
2 |
7.21 Дана матрица смежности н-графа
Степень вершины v4 равна…
а) 2;
б) 4;
в) 6;
г) 3.
7.22 Дана матрица смежности орграфа
Полустепень захода вершины v3 равна…
а) 1;
б) 0;
в) 2;
г) 3.
Рисунок 7.10
0 |
1 |
2 1 |
|
|
|
|
|
|
|
G : A(G) = 1 |
0 |
1 |
0 |
. |
2 1 |
0 |
1 |
|
|
1 |
0 |
1 |
2 |
|
|
1 |
1 |
0 |
0 |
|
|
|
|
|
|
|
G : A(G) = 0 1 |
0 2 . |
||||
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
1 |
|
66
7.23 |
|
|
|
|
|
|
|
|
вид: |
Матрица |
|
достижимости |
орграфа |
G |
имеет |
||||
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
1 |
|
|
|
|
|
||||
R(G) = 0 0 1 |
0 0 . |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
Число компонент сильной связности орграфа G равно…
а) 2;
б) 3;
в) 4;
г) 5.
7.24 Несвязный граф без циклов называется
а) деревом;
б) лесом;
в) орграфом;
г) простым графом.
7.25 Граф G имеет 15 ребер, 10 вершин и 3 компоненты связности.
Число ребер, которые необходимо удалить для того, чтобы граф стал лесом, равно…
а) 2;
б) 5;
в) 7;
г) 8.
67
Глава VIII. Некоторые задачи на графах
Обходы графов
Обходом графа называется некоторое систематическое перечисление его вершин или ребер. Вершинными обходами являются, например, «поиск в глу- бину» и «поиск в ширину», а реберным – нахождение эйлерова цикла.
Поиск в глубину. Пусть дан связный н-граф.
1)Выходя из начальной вершины, строим простую цепь, пройденным верши- нам приписываем метки.
2)Цепь строим до тех пор, пока не встретим уже помеченную вершину или не окажемся в висячей вершине. В этом случае возвращаемся на шаг назад и выбираем ребро, ведущее к непомеченной вершине.
3)Процесс продолжаем до тех пор, пока всем вершинам не будут присвоены метки.
Поиск в ширину. Пусть дан связный н-граф.
1)Выходя из начальной вершины, помечаем все вершины из ее окрестности как вершины первого «уровня».
2)У каждой из вершин первого уровня помечаем еще не помеченные вершины ее окрестности как вершины второго уровня и т. д.
3)Процесс продолжаем до тех пор, пока все вершины не получат метки.
Если граф несвязный, то обходим вершины, достижимые из начальной. В орграфе учитываем направление дуг.
Эйлеров цикл (цепь) – это цикл (маршрут), проходящий через все ребра графа ровно один раз. Н-граф содержит эйлеров цикл тогда и только тогда, ко- гда он связен и степени всех его вершин четны. Если в связном н-графе ровно две вершины нечетной степени, то граф содержит эйлерову цепь. Орграф со- держит эйлеров цикл тогда и только тогда, когда он сильно связен, и для каж- дой его вершины полустепень исхода равна полустепени захода.
Пусть дан н-граф, удовлетворяющий условиям существования эйлерова цикла.
Алгоритм выделения эйлерова цикла:
1)выбираем произвольно некоторую вершину v ;
2)выбираем произвольно ребро u , инцидентное вершине v , присваиваем ему номер 1;
3)каждое пройденное ребро вычеркиваем и присваиваем ему номер на едини- цу больший номера предыдущего вычеркнутого ребра;
68
4)ребро, ведущее в начальную вершину v , выбираем только в том случае, ес- ли нет другого выбора;
5)ребро, являющееся мостом, выбираем только в том случае, если нет другого выбора;
6)после того, как будут пройдены все ребра, в графе образуется эйлеров цикл, причем нумерация ребер соответствует порядку их обхода.
Если в графе возможно построить только эйлерову цепь, то обход начи- наем с вершины, имеющей нечетную степень.
Пример 8.1 Провести поиск в ширину и поиск в глубину из вершины v1 в н-графе, заданном матрицей смежности. Проверить, существует ли в данном графе эйлеров цикл.
|
0 |
2 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
2 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
|
||||||||
A(G) = |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
. |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
|
||||||||
1 0 0 0 1 |
1 0 1 |
||||||||
1 1 1 1 1 |
0 1 |
0 |
|||||||
Последовательность обхода находится не однозначно, для большей опре- деленности будем обходить вершины в порядке возрастания их номеров. Метки вершин указаны в скобках.
Поиск в ширину:
Поиск в глубину:
Проверим условия существования эйлерова цикла:
1)из получившихся обходов видно, что все вершины графа связаны между собой, т.е. граф связен;
2)найдем степени вершин графа:
69
deg(v1 ) = 4; |
deg(v2 ) = 4 ; |
|
|
deg(v3 ) = 2 ; |
deg(v4 ) = 2 ; |
|
||
deg(v5 ) = 3 ; |
deg(v6 ) =1; |
|
|
deg(v7 ) = 4 ; |
deg(v8 ) = 6 . |
|
||
Две вершины v5 и v6 |
имеют нечетную степень, значит, в графе существу- |
|||||||
ет эйлерова цепь: v5 - v4 - v8 - v3 - v2 - v1 - v2 - v8 - v1 - v7 - v8 - v5 - v7 - v6 . |
|
|||||||
Граф (орграф) называется нагруженным (взвешенным), если на множест- |
||||||||
ве его ребер (дуг) задана весовая функция w : E(G) → . |
|
|
||||||
|
|
|
Кратчайшие остовы |
|
|
|||
Пусть G(V , E) |
- нагруженный н-граф с n вершинами, заданный матрицей |
|||||||
весов W (G) : |
|
|
|
|
|
|
|
|
|
|
w(vi ,v j ), (vi ,v j ) E, |
|
|
||||
|
w |
= |
∞, |
(v ,v |
) E, , i, j =1,..., n . |
|
||
|
ij |
|
|
i |
j |
|
|
|
|
|
|
∞, |
i = j |
|
|
||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Вес остова равен сумме весов всех ребер, входящих в остов. Остов явля- ется кратчайшим, если он имеет минимальный вес.
Алгоритм выделения кратчайшего остова:
1)строим граф T1 , состоящий из множества вершин V и единственного ребра u1 , имеющего минимальный вес;
2)если граф Ti уже построен и i < n − k , где n - число вершин, k - число ком- понент связности графа G , то строим граф Ti+1 , добавляя к множеству ребер графа Ti ребро ui+1 , имеющее минимальный вес среди ребер, не входящих в
Ti и не образующих циклов с ребрами из Ti .
Данный алгоритм позволяет находить остов в ненагруженном графе, считая веса всех его ребер равными 1.
Пример 8.2. Найти кратчайший остов в н-графе, заданном матрицей ве-
сов:
|
∞ 5 |
∞ |
∞ |
2 |
1 |
∞ |
∞ |
|
|
5 |
∞ 7 |
∞ 10 2 |
3 |
∞ |
|||
|
∞ 7 |
∞ |
1 |
∞ |
7 |
1 |
3 |
|
|
∞ ∞ 1 |
∞ ∞ ∞ 1 |
3 |
|||||
W (G) = |
2 |
10 ∞ |
∞ ∞ 10 ∞ |
∞ . |
||||
|
|
2 |
7 |
∞ 10 |
∞ 10 |
|
||
1 |
∞ |
|||||||
∞ 3 |
1 |
1 |
∞ 10 ∞ 1 |
|||||
∞ ∞ 3 3 |
∞ ∞ 1 |
∞ |
||||||
70