Тест по предмету «Информатика» на тему «графы»

1. Назовите два основных элемента графа и кратко укажите, что они обозначают.

2. В неориентированном графе рёбра имеют вид \(AB\), \(AC\), \(BC\), \(CD\). Какова степень вершины \(C\)?

3. В неориентированном графе три вершины \(A\), \(B\), \(C\) соединены рёбрами \(AB\) и \(BC\). Сколько единиц содержит его матрица смежности?

4. В ориентированном графе заданы дуги \(A \to B\), \(A \to C\), \(C \to B\), \(B \to D\). Чему равна исходящая степень вершины \(A\)?

5. В графе существуют рёбра \(AB\), \(BC\), \(CD\), \(DA\), а вершины \(A\), \(B\), \(C\), \(D\) различны. Как называется последовательность вершин \(A-B-C-D-A\)?

6. Взвешенный граф имеет рёбра \(AB=4\), \(AC=1\), \(CB=2\), \(BD=1\), \(CD=5\). Найдите кратчайший путь из \(A\) в \(D\) и его длину.

7. Как называется связный граф без циклов, содержащий 6 вершин и 5 рёбер?

8. Как называется маршрут в графе, проходящий по каждому ребру ровно один раз, при этом вершины могут повторяться?

9. В графе вершины \(1,2,3,4\) соединены рёбрами \(1-3\), \(1-4\), \(2-3\), \(2-4\). Можно ли разделить вершины на две доли так, чтобы каждое ребро соединяло вершины из разных долей? Укажите такое разбиение.

10. Составьте список смежности неориентированного графа с вершинами \(A,B,C,D,E\) и рёбрами \(AB\), \(AC\), \(BD\), \(CE\).

Ответы

1. Вершины — объекты графа; рёбра — связи между вершинами.
5. Цикл.
6. \(A-C-B-D\), длина \(1+2+1=4\).
7. Дерево.
8. Эйлеров путь (эйлерова цепь).
9. Да: \(\{1,2\}\) и \(\{3,4\}\).
10. \(A: B,C;\ B: A,D;\ C: A,E;\ D: B;\ E: C\).