Ориентированные графы

Для заданного множества вершин $v_{1}, \ldots , v_{n}$ найти

Доказать, что в ориентированном графе без циклов есть хотя бы один исток и хотя бы один сток.

Пусть $\mathfrak {G}=(V, E)$ — это ациклический граф. Доказать, что его вершины можно пронумеровать $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ так, что если выполнено $\left(v_{i}, v_{j}\right) \in E$, то $i<j$.

Пусть $\mathfrak {G}=(V, E)$ — граф, $V=\left\{ v_{1}, \ldots , v_{n}\right\} , A$ — матрица смежности, $W \subseteq V$, а вектор-столбец $w$ содержит нули и единицы, причём $w_{i}=1$ означает $v_{i} \in W$. Определить смысл булевых произведений $A w$ и $w^{T} A$.

Доказать, что в турнире из вершины $v$ с наибольшей полустепенью исхода в любую другую ведёт путь длины не более двух.

Индукцией по количеству вершин доказать следующее утверждение: в турнире есть простой путь, который проходит через все вершины.

Чемпионат организован по круговой системе (каждая команда играет по одному матчу с каждой, победитель определяется по количеству выигранных матчей). Доказать, что если победитель чемпионата проиграл команде $A$, то $A$ проиграла некоторой команде $B$, которая, в свою очередь, проиграла победителю.

Определить, что представляет собой граф достижимости для

Вычислить матрицу графа достижимости $A_{\mathfrak {G}}$ * для следующего графа

и построить соответствующий ей граф достижимости. Найти все базы графа $\mathfrak {G}$.

Построить для изображённых на рис. 27 ориентированных графов $\mathfrak {G}_{1}$ и $\mathfrak {G}_{2}$ их матрицы смежности и списки смежности. Вычислить матрицы достижимости и построить соответствующие графы достижимости.

Рис. 27. Графы \mathfrak {G}{1} и \mathfrak {G}{2}.

Доказать лемму 60 на стр. 193.

Лемма 60: Отношение строгой достижимости на компонентах сильной связности является отношением строгого частичного порядка, то есть оно антирефлексивно, антисимметрично и транзитивно.

Пусть граф $\mathfrak {G}=(V, E)$ задан своей матрицей смежности:

Построить граф достижимости $\mathfrak {G}^{*}=\left(V, E^{*}\right)$ для $\mathfrak {G}$ и определить, сколько в нём новых рёбер, то есть чему равна разность $\left|E^{*}\right|-\left|E\right|$.

Доказать, что граф без петель ациклический тогда и только тогда, когда все компоненты сильной связности содержат по одному элементу.

Показать, что для каждого положительного $n$ существует граф без циклов с $n$ вершинами и $\frac{n(n-1)}{2}$ рёбрами. Доказать, что в любом графе, в котором рёбер больше, обязательно есть цикл.

Доказать, что в ориентированном графе без циклов существует единственная база, состоящая из всех истоков.

Для графов $\mathfrak {G}_{1}$ и $\mathfrak {G}_{2}$ на рис. 28 определить компоненты сильной связности и отношение строгой достижимости на них.

Рис. 28. Графы \mathfrak {G}{1} и \mathfrak {G}{2}.