Примеры решения задач
Задача 1. Для графа G перечислить все вершины и ребра, указать степени всех вершин. Какие из них являются висячими, а какие изолированными?
v3
x3 x2
v6 v4 v2 x4
x1
v1 x6 x5
v5
Решение. v1, v2, v3, v4, v5, v6, v7 – вершины графа G; ребра графа G – х1, х2, х3, х4, х5. Вершина v1 имеет степень 1, так как ей инцидентно только одно ребро х1. Вершина v2 имеет степень 4, так как ей инцидентны ребра х1, х2, х4, х5. Вершина v3 имеет степень 2, так как ей инцидентны два ребра х2 и х3 и т.д. Вершина v7 имеет степень 0, так как нет ребер ей инцидентных. Таким образом, вершины v1 и v6 являются висячими, так как их степень равна 1. Вершина v7 является изолированной, так как она имеет степень 0.
Задача 2. Для графа G построить матрицу смежности А(G).
v2 x6
x3 x1
v5 v3
v1 x2
x5 x4
v4
Решение. Так как у графа 5 вершин, то размер матрицы А(G) будет 5х5. Так как вершины v1и v2 связаны ребром х1, то а12=1, так как вершины v1 и v3 связаны ребром х2, то а13=1, и т.д. В результате получаем матрицу смежности А(G):
Заметим, что матрица смежности А(G) обладает свойством симметрии.
Задача 3. Пусть дан орграф D. Записать для графа D матрицу смежности А(D) и матрицу инцидентности В(D).
v2
x6 v5 x5 x1
v6 v3
x7 v1 x2
x3 x4
v4
Решение. Орграф D содержит 6 вершин и 7 дуг, поэтому размер матрицы А(D) будет 6х6, а матрица В(D) – 6х7. Так как орграф D не содержит дуги из v1 в v1 (петли), то а11=0. Так как орграф D не содержит дуги из v1 в v2, то а12=0. Так как из вершины v1 в вершину v3 существует дуга х2, то а13=1 и т.д.
В результате получаем матрицу инцидентности А(D):
Матрица смежности А(D) орграфа D не обладает свойством симметрии.
Составим матрицу инцидентности В(D) орграфа D. Элемент b11=-1, так как в вершине v1 заканчивается дуга х1;
элемент b12=1, так как в вершине v1 заканчивается дуга х2 и т.д. В результате получаем матрицу инцидентности В(D):
Задача 4. Пусть дан граф G. Определить количество путей длины 3 из вершины v2 в вершину v5.
x6 v5 v3
x78 v4 x4 x1
x7 x5 x3
v1
v2 x2
Решение. Составим матрицу смежности графа G. Так как вершин у графа G равно 5, то матрица смежности имеет размерность 5х5.
Так как необходимо определить пути длины 3, то матрицу смежности возведем в 3-ю степень.
Так как элемент а25=1, то из вершины v2 в вершину v5 существует один путь длины 3, а именно х2 х4 х6.
Задачи для самостоятельного решения
Задача 1. Для графа G перечислить все вершины, все ребра, указать степени каждой из вершин. Какие из них являются висячими, а какие изолированными?
v2 v3 x2
x78 v4 x3 x1
x5 x4
v1
v6 v5
Задача 2. Для графа G записать матрицу смежности А(G).
v2 v3 x1
x88
x3 x4
v6 x2
x78 v4 x5
v5 v1
x68
Задача 3. Дана матрица смежности А(G) графа G. Восстановить по ней граф.
Задача 4. Для орграфа Д записать матрицу смежности A(G) и матрицу инцидентности В(Д)
v2 v4 x4
x8 x7 x5 x3 x1
v5
x6 v3 v1 x2
Задача 4. По матрице инцидентности В(Д) восстановить орграф.
Задача 5. Дана матрица смежности орграфа Д. Восстановить по ней орграф и найти число путей длины 4 из 1 вершины в 3. Указать эти пути.
Задача 6. Дана матрица смежности графа G. Восстановить по ней граф и найти число путей длины 3 из 2 вершины в 4. Указать эти пути.
