Файл: Дискретная математика.pdf

48

Л а б о р а т о р н а я р а б о т а № 4.5

Кратчайшие пути между каждой парой вершин во взвешенном орграфе

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

Задания

1.Изучить алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе.

2.Разработать и реализовать алгоритм решения задачи (см. варианты заданий).

3.Подобрать тестовые данные. Результат представить в виде диаграммы графа.

Варианты заданий

1.Во взвешенном орграфе найти все пары вершин vi и vj, такие, что кратчайшее расстояние от vi до vj равно кратчайшему расстоянию от vj до vi. Вывести кратчайшие пути между найденными парами вершин.

2.Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей минимальной стоимости.

3.Во взвешенном орграфе найти все такие вершины vi, что сумма кратчайших расстояний от всех вершин орграфа до vi равна сумме кратчайших расстояний от vi до всех вершин орграфа.

4.Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней медианой, и внутренним центром. Привести пример орграфа с такой вершиной.

5.Во взвешенном орграфе найти все такие вершины vi, что кратчайшее расстояние от самой “удаленной” вершины орграфа до vi равно кратчайшему расстоянию от vi до самой “удаленной” от нее вершины.

6.Используя алгоритм нахождения кратчайших расстояний между каждой парой вершин в орграфе определить:

а) является ли заданный орграф сильно связным; б) является ли заданный орграф односторонне связным.

49

7.Найти все внешние, внутренние и внешне-внутренние центры взвешенного орграфа. Привести примеры орграфов, которые имеют более одного центра каждого вида.

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

9.Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней, и внутренней медианой. Привести пример орграфа с такой вершиной.

10.Во взвешенном орграфе найти все пары вершин vi и vj, такие, что кратчайшее расстояние от vi до vj меньше кратчайшего расстояния от vj до vi. Вывести кратчайшие пути между найденными парами вершин.

11.Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей максимальной стоимости.

12.Во взвешенном орграфе найти все такие вершины vi, что сумма кратчайших расстояний от всех вершин орграфа до vi меньше суммы кратчайших расстояний от vi до всех вершин орграфа.

13.Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешним центром, и внутренней медианой. Привести пример орграфа с такой вершиной.

14.Во взвешенном орграфе найти все такие вершины vi, что кратчайшее расстояние от самой “удаленной” вершины орграфа до vi меньше кратчайшего расстояния от vi до самой “удаленной” от нее вершины.

15.Найти множество вершин во взвешенном орграфе, внешние и внутренние передаточные числа которых совпадают.

16.Найти все внешние, внутренние и внешне-внутренние медианы взвешенного орграфа. Привести примеры орграфов, которые имеют более одной медианы каждого вида.

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

18.Найти множество вершин во взвешенном орграфе, числа внешнего и внутреннего разделения которых совпадают.

19.Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешним, и внутренним центром. Привести пример орграфа с такой вершиной.

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

50

Контрольные вопросы

1.Дайте определение графа, орграфа, псевдографа, мультиграфа, гиперграфа, взвешенного графа. Что такое степень вершины, полустепень исхода и полустепень захода? Дайте определение понятиям смежности и инцидентности.

2.Что такое матрица смежности и матрица инцидентности? Предложите различные способы хранения взвешенных графов и орграфов в памяти ЭВМ. Разработайте алгоритмы преобразования одного способа хранения графа в другой.

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

4.Дайте определение маршрута, цепи, простой цепи. Опишите алгоритмы получения всех маршрутов, цепей и простых цепей заданной длины. Как можно подсчитать количество маршрутов заданной длины между каждой парой вершин графа?

5.Что называется расстоянием между заданными вершинами, эксцентриситетом вершины, диаметром и радиусом графа? Какая вершина графа называется переферийной, центральной? Что называется центром графа? Какая цепь называется диаметральной?

6.Дайте определение цикла и простого цикла. Опишите алгоритм получения всех простых циклов в графе.

7.Какой цикл называется гамильтоновым? Как определить, является ли граф гамильтоновым? Какой цикл называется эйлеровым? Как определить, является ли граф эйлеровым? Опишите алгоритмы получения всех гамильтоновых и эйлеровых циклов.

8.Какой граф называется связным?

9.Что такое матрица связанности вершин? Как ее вычислить?

10.Что называется мостом, точкой сочленения, разрезом, реберной

ивершинной связностью?

11.Дайте определение дереву и лесу. Какими свойствами обладают дерево и лес?

12.Что такое лист и корень дерева? Сколько корней может иметь дерево? Докажите.

13.Сколько различных деревьев можно построить на n вершинах? Докажите.

14.Дайте определение покрывающему дереву и покрывающему лесу. Сколько ребер нужно удалить из связного графа, чтобы получить покрывающее дерево? Сколько ребер нужно удалить из несвязного графа, чтобы получить покрывающий лес?

51

15.Опишите алгоритм Краскала. Что такое “букет”?

16.Опишите алгоритм формирования всех покрывающих деревьев связного графа.

17.Как определяется стоимость покрывающего дерева взвешенного графа? Опишите алгоритмы построения покрывающего дерева минимальной стоимости.

18.Что называется поиском в орграфе? Опишите алгоритмы поиска

вглубину и в ширину.

19.Какие виды связности существуют в орграфе?

20.Дайте определения отношениям достижимости, контрдостижимости и взаимодостижимости вершин орграфа.

21.Что называется компонентой сильной связности орграфа? Опишите алгоритм нахождения компонент сильной связности орграфа.

22.Что называется конденсацией орграфа? Что называется базой и антибазой орграфа?

23.Что называется кратчайшим путем и кратчайшим расстоянием между двумя вершинами во взвешенном орграфе? Опишите алгоритмы нахождения кратчайших путей между заданной парой вершин во взвешенном орграфе.

24.Что такое дерево кратчайших путей? Как его построить?

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

26.Что называется числом внешнего, внутреннего и внешневнутреннего разделения вершины? Что называется внешним, внутренним и внешне-внутренним центром взвешенного орграфа?

27.Что называется внешним, внутренним и внешне-внутренним передаточным числом вершины во взвешенном орграфе? Что называется внешней, внутренней и внешне-внутренней медианой взвешенного орграфа?

28.Дайте определение клики, максимальной клики и наибольшей клики. Опишите алгоритмы поиска всех максимальных клик и наибольшей клики.

29.Дайте определение независимому множеству вершин, максимальному и наибольшему независимому множеству. Установите связь между кликами и независимыми множествами вершин.

30.Что такое раскраска графа, правильная раскраска, хроматическое число, минимальная раскраска?

31.Опишите алгоритм получения всех раскрасок графа в число цветов, не превышающее заданного.

32.Опишите алгоритм получения минимальной раскраски.