Хорошо, давайте решим все 12 заданий по вашей матрице смежности. Буду оформлять так, чтобы было удобно переписать в тетрадь.
Ваша матрица смежности \(G\):
\[
G =
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 0
\end{pmatrix}
\]
Задание 1. По матрице смежности нарисовать p,q-граф. Охарактеризовать его свойства.
Для начала, определим количество вершин \(p\) и рёбер \(q\).
Количество вершин \(p\) равно размерности матрицы, то есть \(p = 6\).
Количество рёбер \(q\) равно сумме всех единиц в матрице смежности.
Суммируем элементы матрицы \(G\):
\(q = (1+1+0+0+0+0) + (0+0+1+0+0+0) + (1+0+0+1+0+0) + (1+1+1+0+1+0) + (1+1+1+1+0+1) + (1+1+1+1+1+0)\)
\(q = 2 + 1 + 2 + 4 + 5 + 5 = 19\)
Итак, \(p=6\), \(q=19\).
Граф является ориентированным, так как матрица смежности несимметрична (например, \(G_{12}=1\), но \(G_{21}=0\)).
Граф содержит петли, так как на главной диагонали есть единицы (например, \(G_{11}=1\)).
Граф является взвешенным, если бы элементы матрицы были не только 0 и 1, но в данном случае это обычный граф.
Нарисуем граф. Вершины обозначим цифрами от 1 до 6.
Ребро из вершины \(i\) в вершину \(j\) существует, если \(G_{ij}=1\).
* Из 1 в 1 (петля)
* Из 1 в 2
* Из 2 в 3
* Из 3 в 1
* Из 3 в 4
* Из 4 в 1
* Из 4 в 2
* Из 4 в 3
* Из 4 в 5
* Из 5 в 1
* Из 5 в 2
* Из 5 в 3
* Из 5 в 4
* Из 5 в 6
* Из 6 в 1
* Из 6 в 2
* Из 6 в 3
* Из 6 в 4
* Из 6 в 5
(Здесь должен быть рисунок графа. Поскольку я не могу рисовать, я опишу его словами. Представьте 6 вершин, расположенных по кругу или в виде многоугольника, и стрелки между ними согласно описанным связям.)
Свойства графа:
* Ориентированный (дуги).
* Содержит петли (дуга из вершины в саму себя).
* Не является простым (из-за петель).
* Не является полным (не все возможные дуги присутствуют).
* Не является регулярным (степени вершин разные).
* Является связным (из любой вершины можно достичь любой другой, хотя бы косвенно).
Задание 2. Обозначить граф (вершины, ребра).
Вершины: \(V = \{1, 2, 3, 4, 5, 6\}\)
Рёбра (дуги): \(E = \{(1,1), (1,2), (2,3), (3,1), (3,4), (4,1), (4,2), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5)\}\)
Задание 3. Записать граф в виде отношения. Записать обратное отношение.
Граф в виде отношения \(G\):
\(G = \{(1,1), (1,2), (2,3), (3,1), (3,4), (4,1), (4,2), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5)\}\)
Обратное отношение \(G^{-1}\) получается заменой каждой пары \((u,v)\) на \((v,u)\):
\(G^{-1} = \{(1,1), (2,1), (3,2), (1,3), (4,3), (1,4), (2,4), (3,4), (5,4), (1,5), (2,5), (3,5), (4,5), (6,5), (1,6), (2,6), (3,6), (4,6), (5,6)\}\)
Задание 4. Найти степени вершин. Проверить выполнение основного соотношения.
Для ориентированного графа различают полустепень исхода (out-degree) и полустепень захода (in-degree).
Полустепень исхода \(d^+(v)\) - количество рёбер, исходящих из вершины \(v\). Это сумма элементов в строке матрицы смежности.
Полустепень захода \(d^-(v)\) - количество рёбер, входящих в вершину \(v\). Это сумма элементов в столбце матрицы смежности.
Вычислим полустепени исхода:
\(d^+(1) = G_{11} + G_{12} + G_{13} + G_{14} + G_{15} + G_{16} = 1+1+0+0+0+0 = 2\)
\(d^+(2) = G_{21} + G_{22} + G_{23} + G_{24} + G_{25} + G_{26} = 0+0+1+0+0+0 = 1\)
\(d^+(3) = G_{31} + G_{32} + G_{33} + G_{34} + G_{35} + G_{36} = 1+0+0+1+0+0 = 2\)
\(d^+(4) = G_{41} + G_{42} + G_{43} + G_{44} + G_{45} + G_{46} = 1+1+1+0+1+0 = 4\)
\(d^+(5) = G_{51} + G_{52} + G_{53} + G_{54} + G_{55} + G_{56} = 1+1+1+1+0+1 = 5\)
\(d^+(6) = G_{61} + G_{62} + G_{63} + G_{64} + G_{65} + G_{66} = 1+1+1+1+1+0 = 5\)
Вычислим полустепени захода:
\(d^-(1) = G_{11} + G_{21} + G_{31} + G_{41} + G_{51} + G_{61} = 1+0+1+1+1+1 = 5\)
\(d^-(2) = G_{12} + G_{22} + G_{32} + G_{42} + G_{52} + G_{62} = 1+0+0+1+1+1 = 4\)
\(d^-(3) = G_{13} + G_{23} + G_{33} + G_{43} + G_{53} + G_{63} = 0+1+0+1+1+1 = 4\)
\(d^-(4) = G_{14} + G_{24} + G_{34} + G_{44} + G_{54} + G_{64} = 0+0+1+0+1+1 = 3\)
\(d^-(5) = G_{15} + G_{25} + G_{35} + G_{45} + G_{55} + G_{65} = 0+0+0+1+0+1 = 2\)
\(d^-(6) = G_{16} + G_{26} + G_{36} + G_{46} + G_{56} + G_{66} = 0+0+0+0+1+0 = 1\)
Основное соотношение для ориентированного графа: сумма полустепеней исхода равна сумме полустепеней захода и равна общему числу рёбер \(q\).
\(\sum_{v \in V} d^+(v) = q\)
\(\sum_{v \in V} d^-(v) = q\)
Проверим:
\(\sum d^+(v) = 2+1+2+4+5+5 = 19\)
\(\sum d^-(v) = 5+4+4+3+2+1 = 19\)
Обе суммы равны 19, что совпадает с количеством рёбер \(q\). Основное соотношение выполняется.
Задание 5. Записать матрицу инцидентности (смежность ребро-вершина – с точностью до петель!).
Матрица инцидентности \(B\) имеет размерность \(q \times p\), где \(q\) - количество рёбер, \(p\) - количество вершин.
Элемент \(B_{ej}\) равен 1, если ребро \(e\) инцидентно вершине \(j\). Для ориентированного графа:
\(B_{ej} = 1\), если ребро \(e\) исходит из вершины \(j\).
\(B_{ej} = -1\), если ребро \(e\) входит в вершину \(j\).
\(B_{ej} = 0\), если ребро \(e\) не инцидентно вершине \(j\).
Петли обрабатываются по-особому: для петли \((v,v)\) элемент \(B_{ev}\) равен 2.
Перечислим рёбра и их номера:
\(e_1 = (1,1)\)
\(e_2 = (1,2)\)
\(e_3 = (2,3)\)
\(e_4 = (3,1)\)
\(e_5 = (3,4)\)
\(e_6 = (4,1)\)
\(e_7 = (4,2)\)
\(e_8 = (4,3)\)
\(e_9 = (4,5)\)
\(e_{10} = (5,1)\)
\(e_{11} = (5,2)\)
\(e_{12} = (5,3)\)
\(e_{13} = (5,4)\)
\(e_{14} = (5,6)\)
\(e_{15} = (6,1)\)
\(e_{16} = (6,2)\)
\(e_{17} = (6,3)\)
\(e_{18} = (6,4)\)
\(e_{19} = (6,5)\)
Матрица инцидентности \(B\) будет иметь размерность \(19 \times 6\).
\[
B =
\begin{pmatrix}
\text{вершина 1} & \text{вершина 2} & \text{вершина 3} & \text{вершина 4} & \text{вершина 5} & \text{вершина 6} \\
2 & 0 & 0 & 0 & 0 & 0 & (e_1=(1,1)) \\
1 & -1 & 0 & 0 & 0 & 0 & (e_2=(1,2)) \\
0 & 1 & -1 & 0 & 0 & 0 & (e_3=(2,3)) \\
-1 & 0 & 1 & 0 & 0 & 0 & (e_4=(3,1)) \\
0 & 0 & 1 & -1 & 0 & 0 & (e_5=(3,4)) \\
-1 & 0 & 0 & 1 & 0 & 0 & (e_6=(4,1)) \\
0 & -1 & 0 & 1 & 0 & 0 & (e_7=(4,2)) \\
0 & 0 & -1 & 1 & 0 & 0 & (e_8=(4,3)) \\
0 & 0 & 0 & 1 & -1 & 0 & (e_9=(4,5)) \\
-1 & 0 & 0 & 0 & 1 & 0 & (e_{10}=(5,1)) \\
0 & -1 & 0 & 0 & 1 & 0 & (e_{11}=(5,2)) \\
0 & 0 & -1 & 0 & 1 & 0 & (e_{12}=(5,3)) \\
0 & 0 & 0 & -1 & 1 & 0 & (e_{13}=(5,4)) \\
0 & 0 & 0 & 0 & 1 & -1 & (e_{14}=(5,6)) \\
-1 & 0 & 0 & 0 & 0 & 1 & (e_{15}=(6,1)) \\
0 & -1 & 0 & 0 & 0 & 1 & (e_{16}=(6,2)) \\
0 & 0 & -1 & 0 & 0 & 1 & (e_{17}=(6,3)) \\
0 & 0 & 0 & -1 & 0 & 1 & (e_{18}=(6,4)) \\
0 & 0 & 0 & 0 & -1 & 1 & (e_{19}=(6,5))
\end{pmatrix}
\]
Задание 6. Нарисовать граф, изоморфный заданному.
Изоморфный граф имеет ту же структуру связей, но может отличаться названиями вершин или их расположением.
Простейший способ нарисовать изоморфный граф – это перенумеровать вершины.
Например, пусть \(1' \to 2\), \(2' \to 3\), \(3' \to 4\), \(4' \to 5\), \(5' \to 6\), \(6' \to 1\).
Тогда матрица смежности \(G'\) для нового графа будет:
\[
G' =
\begin{pmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\]
Это не совсем то, что нужно. Изоморфный граф должен иметь ту же структуру, а не просто перенумерованные вершины.
Если мы просто перенумеруем вершины, то матрица смежности изменится, но граф останется изоморфным.
Например, пусть \(v_1 \to v_2\), \(v_2 \to v_1\), а остальные вершины остаются на своих местах.
Тогда матрица смежности будет выглядеть так:
\[
G_{изоморфный} =
\begin{pmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 0
\end{pmatrix}
\]
(Это пример, как можно получить другую матрицу, но граф будет изоморфен. Для школьника достаточно просто перерисовать граф, изменив расположение вершин, но сохранив все связи.)
(Здесь должен быть рисунок графа, идентичный по структуре исходному, но, возможно, с другим расположением вершин или их обозначениями, например, A, B, C, D, E, F вместо 1, 2, 3, 4, 5, 6.)
Задание 7. Записать матрицу расстояний. Сопоставить со степенями матрицы смежности.
Матрица расстояний \(R\) содержит кратчайшие пути между всеми парами вершин. Для ориентированного графа расстояние от \(u\) до \(v\) может отличаться от расстояния от \(v\) до \(u\).
Если пути нет, расстояние считается бесконечным.
Для нахождения матрицы расстояний можно использовать алгоритм Флойда-Уоршелла или последовательно возводить матрицу смежности в степень.
Элемент \
