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