Тест по предмету «Информатика» на тему «Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе»
- Для ориентированного графа задана весовая матрица, где \(m_{ij}\) — вес дуги из вершины \(i\) в вершину \(j\), а \(\infty\) означает отсутствие дуги:
| A | B | C | |
|---|---|---|---|
| A | 0 | 5 | ∞ |
| B | ∞ | 0 | 2 |
| C | 1 | ∞ | 0 |
Выберите все верные утверждения.
A. Существует дуга \(A \to B\) весом 5.
B. Существует дуга \(A \to C\) весом \(\infty\).
C. Длина пути \(A \to B \to C\) равна 7.
D. Существует дуга \(C \to A\) весом 1.
- В ориентированном взвешенном графе имеются дуги: \(A \to B\) весом 4, \(B \to C\) весом 3, \(A \to D\) весом 2, \(D \to C\) весом 6, \(B \to D\) весом 1. Длина пути равна сумме весов входящих в него дуг. Выберите все верные утверждения.
A. Длина пути \(A \to B \to C\) равна 7.
B. Длина пути \(A \to D \to C\) равна 8.
C. Длина пути \(A \to B \to D \to C\) равна 11.
D. Путь \(A \to D \to C\) является кратчайшим путём из \(A\) в \(C\).
- Дан направленный ациклический граф с дугами \(s \to a\), \(s \to b\), \(a \to b\), \(a \to t\), \(b \to t\). Выберите все верные утверждения.
A. Из \(s\) в \(t\) существует ровно 3 направленных пути.
B. Последовательность \(s \to a \to b \to t\) является направленным путём.
C. Последовательность \(s \to b \to a \to t\) является направленным путём.
D. Каждый путь из \(s\) в \(t\) проходит через вершину \(a\).
- Дан направленный ациклический граф с дугами \(1 \to 2\), \(1 \to 3\), \(2 \to 3\), \(2 \to 4\), \(3 \to 4\), \(3 \to 5\), \(4 \to 5\). Выберите все верные утверждения.
A. Из вершины 1 в вершину 5 существует ровно 5 направленных путей.
B. Из вершины 1 в вершину 3 существует ровно 2 направленных пути.
C. Из вершины 2 в вершину 5 существует ровно 3 направленных пути.
D. Последовательность \(1 \to 4 \to 5\) является направленным путём.
- Для ориентированного графа задана весовая матрица, где строки соответствуют начальным вершинам, столбцы — конечным, а \(\infty\) означает отсутствие дуги:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 2 | 5 | ∞ |
| B | ∞ | 0 | 1 | 4 |
| C | ∞ | ∞ | 0 | 2 |
| D | ∞ | ∞ | ∞ | 0 |
Выберите все верные утверждения.
A. Длина пути \(A \to B \to C \to D\) равна 5.
B. Существует дуга \(A \to D\) весом \(\infty\).
C. Кратчайший путь из \(A\) в \(D\) имеет длину 5.
D. Из \(A\) в \(D\) существует ровно 3 направленных пути.
Ответы
1 — A, C, D
2 — A, B, C
3 — A, B
4 — A, B, C
5 — A, C, D
