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

43. Задан граф G(V,E):

Смежными рёбрами являются…

 

Е1,е5; е2,е5; е3,е5; е4,е5.

Е1, е2; е2,е3; е3,е4; е4,е1.

44. Совокупность ребер (i,j), начальные вершины которых принадлежит подмножеству А, а конечные подмножеству В транспортной сети, и обозначается R (A/B) называется …

Разрезом сети.

45. Каким обязательно должно быть выровненное дерево?

Связным.

46. Как называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0?

Ориентированное дерево.

47. Какое дерево называют сбалансированным?

Если для любого узла высота левого и правого поддеревьев отличается не более чем на единицу.

48. Сбалансированное по высоте дерево называется также...

АВЛ-деревом.

Подровненным.

49. Для сбалансированного по высоте бинарного дерева:

H < 2 log2 p.

50. Какие основные структуры данных используются для представления ассоциативной памяти?

Дерево сортировки.

Упорядоченный массив.

Неупорядоченный массив.

таблица расстановки.

 

51. Какое дерево оказывается во многих случаях наилучшим вариантом представления дерева сортировки?

Сбалансированное дерево.

52. Как еще называется таблица расстановки?

хэш-таблица.

53. По какой формуле рассчитывается сумма степеней вершин графа?

.

 

 

54. Задан граф G(V,E):

Несмежными рёбрами являются…

Е1,е3; е2,е4.

55. По какой формуле рассчитывается сумма полу степеней вершин орграфа?

56. Какой цикл называется гамильтоновым циклом?

Содержащий все вершины графа (по одному разу).

57. Какой цикл называется эйлеровым циклом?

Цикл, содержащий все рёбра графа по одному разу.

58. Название «гамильтонов цикл» произошло от задачи…

Кругосветное путешествие».

59. Области применения алгоритма построения минимального остовного дерева:

Производство печатных плат: соединить n контактов проводами с минимальной суммарной стоимостью.

Разработка сетей: задача о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений.

Минимальное остовное дерево может использоваться для визуализации многоаспектных, многомерных данных.

Наука, и в частности биология, используют многомерные данные для группировки объектов, растений, животных. Минимальное остовное дерево позволяет разбивать их на взаимосвязанные классы, четко отслеживая близкие по строению и характеристикам группы.

 

 

60. Суммарный вес минимального остовного дерева

равен...

3

61. Разрез транспортной сети графа проходит через...

Ребра.

62. Может ли Эйлеров цикл проходить через одну и ту же вершину несколько раз?

Да.

63. Эквивалентны ли понятия "минимальное остовное дерево" и "остовное дерево с минимальным весом"?

Да.

64. При построении минимального остовного дерева возможно ли появление изолированных вершин?

Нет.