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

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

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

Пусть $\mathfrak {G}=(V, E)$ — это ориентированный граф без циклов и $\left|E\right|>0$. Какие из следующих утверждений верны?

Пусть $\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$.

Граф называется однородным, если полустепени захода и исхода всех его вершин равны одному и тому же числу $r$. Доказать, что для каждого $n>r$ существует однородный граф с $n$ вершинами и полустепенью $r$.

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

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

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

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

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

Построить представления в виде матрицы смежности и списков смежности для ориентированного графа

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

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

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

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

Пусть граф $\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}=(V, E)$, где $V=\left\{ a, b, c, d, e, f, g, h\right\} , E=\left\{ (a, d),(a, f),(a, h),(b, e),(c, b),(c, e),(d, g),(e, b), (e, d),(e, h),(f, a),(f, b),(f, c),(f, d),(f, e),(f, g),(f, h),(g, h), (h, d),(h, g)\right\}$. Построить матрицы смежности, достижимости, взаимной достижимости. Найти компоненты сильной связности.

Дан ориентированный граф $\mathfrak {G}=(V, E)$, где $V=\left{ a, b, c, d, e, f, g, h\right} , E=\left{ (a, c),(a, d),(a, e),(a, f),(b, c),(b, g),(b, h),(c, b), (c, h),(d, a),(d, b),(d, g),(e, c),(e, f),(e, g),(e, h),(f, c),(f, e),

(f, g),(g, b),(g, h),(h, g)\right}$. Построить матрицы смежности, достижимости, взаимной достижимости. Найти компоненты сильной связности.

Дан ориентированный граф $\mathfrak {G}=(V, E)$, где $V=\left\{ a, b, c, d, e, f, g, h\right\} , E=\left\{ (a, c),(a, d),(a, f),(a, g),(b, e),(b, h),(c, a),(c, b), (c, h),(d, b),(d, c),(d, e),(d, g),(d, h),(e, h),(f, h),(g, a),(g, c), (g, f),(h, e)\right\}$. Построить матрицы смежности, достижимости, взаимной достижимости. Найти компоненты сильной связности.

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

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

Определить для каждого из графов $\mathfrak {G}_{i}, i=1,2,3$, изображённых на рис. 10 на следующей странице, компоненты сильной связности, отношение строгой достижимости на них и все базы.

Рис. 10: Графы \mathfrak {G}{1}, \mathfrak {G}{2} и \mathfrak {G}_{3}.

Доказать, что граф является сильно связным тогда и только тогда, когда в нём есть цикл, содержащий все вершины.