Пройти тест: ЕГЭ по информатике: Графы и кратчайшие пути | Zestly

Question 1

Дан ориентированный граф, заданный списком ребер: (A,B,2), (A,C,5), (B,C,1), (B,D,7), (C,D,3), (D,E,2). Какова длина кратчайшего пути из вершины A в вершину E?

Accepted Answer

8

Question 2

В неориентированном графе 8 вершин. Какое максимальное количество ребер может содержать этот граф, чтобы он оставался деревом?

Accepted Answer

7

Question 3

Дан граф с вершинами {1, 2, 3, 4, 5}. Матрица смежности (где 0 — отсутствие ребра, число — вес): 
Строка 1: [0, 3, 0, 0, 0]
Строка 2: [3, 0, 2, 4, 0]
Строка 3: [0, 2, 0, 1, 5]
Строка 4: [0, 4, 1, 0, 2]
Строка 5: [0, 0, 5, 2, 0]
Выберите все верные утверждения о путях из вершины 1 в вершину 5.

Accepted Answer

Кратчайший путь имеет длину 8

Question 4

В ориентированном графе вершины A, B, C, D. Ребра: A->B (весом 2), B->C (весом 3), A->C (весом 6), C->D (весом 1), B->D (весом 5). Сколько существует различных путей из A в D?

Answer

2

Answer

3

Answer

4

Answer

5

Question 5

Выберите верные свойства для любого связного неориентированного графа без циклов (дерева):

Answer

Удаление любого ребра делает граф несвязным

Answer

Количество ребер всегда равно количеству вершин

Answer

Добавление любого ребра создает цикл

Answer

Степень каждой вершины равна 2