Алгоритмы на графах

Что такое вершина в графе?

• Линия, соединяющая две вершины

• Точка, представляющая объект в графе

• Цикл в графе

• Вес ребра

Что такое ребро в графе?

• Точка, представляющая объект в графе

• Линия, соединяющая две вершины

• Цикл в графе

• Вес вершины

Чем отличается ориентированный граф от неориентированного?

• Ориентированный граф имеет циклы, а неориентированный нет

• В ориентированном графе ребра имеют направление, а в неориентированном нет

• Ориентированный граф имеет больше вершин, чем неориентированный

• Ориентированный граф используется только для решения математических задач

Что такое матрица смежности графа?

• Таблица, в которой строки и столбцы соответствуют вершинам, а элементы указывают количество ребер между вершинами

• Таблица, в которой строки и столбцы соответствуют ребрам, а элементы указывают, инцидентны ли ребра вершинам

• Таблица, в которой строки и столбцы соответствуют вершинам, а элементы указывают расстояние между вершинами

• Таблица, в которой строки и столбцы соответствуют ребрам, а элементы указывают вес ребер

Как называется алгоритм поиска кратчайшего пути

• Алгоритм Крускала

• Алгоритм Флойда-Уоршелла

• Алгоритм Флойда-Уоршелла

• Алгоритм Дейкстры

Изображена схема дорог, связывающих города A, B, C, D, E и F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город F?

• 6

• 5

• 4

• 7

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К?

• 13

• 11

• 12

• 10

Граф называется ориентированным, если:

• у рёбер графа указано направление

• у рёбер графа указано числовое значение

• если возможно только однократное прохождение вершин и рёбер графа

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите таблицу, соответствующую схеме.

• 
• 
• 

В виде иерархической структуры графа ("дерева") можно представить:

• файловую систему компьютера

• образование трехразрядных двоичных чисел

• процесс передвижения из начального пункта в конечный через конкретную область