Графы и матрицы

Путь длины $k$ в орграфе — это последовательность из $k$ дуг, соединяющих две вершины. Маршрут — это путь, в котором все дуги (но не обязательно все вершины) различны. Простой путь — это путь, в котором все дуги и все вершины различны. Покажите, что число путей длины $k$ из вершины $i$ в вершину $j$ в орграфе $D$ с $n$ вершинами задаётся $ij$-м элементом матрицы $A^{k}$, где $A$ — матрица смежности орграфа.

Рассмотрим орграф. Полустепень исхода вершины $v$ — это число дуг, исходящих из $v$, а полустепень захода вершины $V$ — это число дуг, входящих в $v$. Петли считаются как одна дуга каждого вида.

Определите полустепень захода и полустепень исхода каждой вершины орграфа, заданного матрицей смежности

и, следовательно, определите, является ли он эйлеровым графом. Изобразите орграф и найдите эйлеров маршрут.

Орграф называется сильно связным, если между каждой парой вершин существует путь. Покажите, что если $A$ — матрица смежности орграфа $D$ с $n$ вершинами, а $B$ — матрица

то $D$ сильно связен тогда и только тогда, когда каждый недиагональный элемент матрицы $B$ больше 0.

Запишите матрицу смежности $A$ для изображённого орграфа. Вычислите матрицы $A^{2}$, $A^{3}$ и $A^{4}$. Следовательно, найдите число маршрутов длины 1, 2, 3 и 4 из $w$ в $u$. Существует ли маршрут длины 1, 2, 3 или 4 из $u$ в $w$? Найдите матрицу $B=A+A^{2}+A^{3}+A^{4}$ для орграфа и, следовательно, сделайте вывод о том, является ли он сильно связным. Это означает выяснение того, все ли внедиагональные элементы отличны от нуля.

Орграф к задаче 21.1.4.

Граф $G(V,E)$ — это множество узлов $V$ (точек, вершин), соединённых множеством связей $E$ (рёбер, линий). Будем считать, что имеется $n$ узлов. Матрица смежности ($n \times n$) $A=A(G)$ имеет вид с 1 в строке $i$, столбце $j$, если $i$ соединена с $j$, и 0 в противном случае. Таким образом, $A$ — симметричная матрица. С $A$ связано распределение степеней — диагональная матрица с суммами строк $A$ на диагонали и нулями во всех остальных местах. Предположим, что $d_{ii}>0$ для всех $i=1,2,\ldots ,n$. Определим лапласиан как $L := D-A$. Пусть

Граф $G(V,E)$ — это множество узлов $V$ (точек, вершин), соединённых множеством связей $E$ (рёбер, линий). Будем считать, что число узлов равно $n$. Матрица смежности ($n \times n$) $A=A(G)$ имеет вид: 1 в строке $i$, столбце $j$, если $i$ соединён с $j$, и 0 в противном случае. Таким образом, $A$ — симметричная матрица. С матрицей $A$ связано распределение степеней $D$ — диагональная матрица, на диагонали которой стоят суммы по строкам матрицы $A$, а остальные элементы равны 0. Матрица $D$ описывает, сколько связей имеет каждый узел. Определим лапласиан как $L := D-A$. Пусть $A = (a_{ij})$, то есть $a_{ij}$ — элементы матрицы смежности. Найдите минимум взвешенной суммы

при условии $\overrightarrow {x}^{T} \overrightarrow {x}=1$, где $\overrightarrow {x}^{T} = (x_{1}, x_{2}, \ldots , x_{n})$. Используйте метод множителей Лагранжа. Сумма берётся по всем парам квадратов расстояний между узлами, которые соединены между собой, поэтому решение должно приводить к тому, что узлы с большим числом взаимных связей будут сгруппированы вместе.

Найдите собственные значения трёх матриц смежности

задающих три простых графа. Найдите «энергию» $E(G)$ каждого графа, определяемую как

Рассмотрим два ориентированных графа с матрицами смежности

Рассмотрим ориентированный граф $G$

Ориентированный граф G из задачи 21.1.9.

Пусть $G$ — граф с вершинами $V$ и рёбрами $E$. Граф $G$ называется транзитивным, если из $(v_{1},v_{2}), (v_{2},v_{3}) \in E$ следует $(v_{1},v_{3}) \in E$. Транзитивным замыканием $\widetilde{G}$ графа $G$ называется наименьший транзитивный граф $\widetilde{G}$, содержащий $G$ в качестве подграфа. Пусть $H$ — матрица смежности графа $G$, а $\widetilde{H}$ — матрица смежности графа $\widetilde{G}$. Если $(H)_{ij}=1$ и $(H)_{jk}=1$, то $(\widetilde{H})_{ij} = (\widetilde{H})_{jk} = (\widetilde{H})_{ik} = 1$. Напишите программу на C++, находящую $\widetilde{H}$ для любой заданной матрицы смежности $H$. Найдите матрицу смежности транзитивного замыкания графа, заданного матрицей смежности

Сравните две матрицы смежности

Допускают ли они эйлеров путь?

Рассмотрим матрицу смежности

Существует ли гамильтонов цикл?

Пусть $G$ — граф с вершинами $V_{G} = \left\{ 1,\ldots ,n_{G}\right\}$ и рёбрами $E_{G} \subseteq V_{G} \times V_{G}$. Матрица смежности $A_{G}$ размера $n_{G} \times n_{G}$ задаётся как $(A_{G})_{ij} = \chi_{E_{G}}(i,j) \in \left\{ 0,1\right\}$, где $i,j \in V$. В следующих произведениях графов $G_{1}$ и $G_{2}$ используются матрицы смежности размера $n_{G_{1}} n_{G_{2}} \times n_{G_{2}} n_{G_{2}}$. Строки и столбцы индексируются множеством $V_{G_{1}} \times V_{G_{2}}$, причём используется упорядочение $(i,j) \leq (k,l)$, если $i<k$, либо $i=k$ и $j \leq l$.

Декартово произведение $G_{1} \times G_{2}$ двух графов $G_{1}$ и $G_{2}$ — это граф с вершинами

и рёбрами

Отсюда следует, что

где $\boxplus$ — обычное сложение с соглашением $1 \boxplus 1 = 1$. Таким образом,

Лексикографическое произведение $G_{1} \bullet G_{2}$ двух графов $G_{1}$ и $G_{2}$ — это граф с вершинами

и рёбрами

Таким образом $E_{G_{1} \times G_{2}} \subseteq E_{G_{1} \bullet G_{2}}$. Отсюда следует, что

Следовательно,

Здесь $\overrightarrow {1}_{n_{G_{1}}}$ — это матрица размера $n_{G_{2}} \times n_{G_{2}}$, все элементы которой равны 1.

Тензорное произведение $G_{1} \otimes G_{2}$ двух графов $G_{1}$ и $G_{2}$ — это граф с вершинами

и рёбрами

Отсюда следует, что

Таким образом $A_{G_{1} \otimes G_{2}} = A_{G_{1}} \otimes A_{G_{2}}$, где $\otimes$ — произведение Кронекера матриц.

Нормальное произведение $G_{1} \star G_{2}$ двух графов $G_{1}$ и $G_{2}$ — это граф с вершинами

и рёбрами

Таким образом,