ВУЗ:
Составители:
Рубрика:
. Практикум по курсу «Алгоритмизация и программирование». Часть 2
8. Дан граф. Написать функцию, которая находит путь максимальной
длины, исходящий из заданной вершины.
9. Дан граф. Написать функцию поиска пути максимальной длины в гра-
фе.
10. Дан граф. Написать функцию поиска медианы графа, т.е. такой его
вершины, что сумма расстояний от нее до остальных вершин минимальна.
11. Дан граф. Написать функцию, определяющую является ли он
связным. Связным называется граф, из каждой вершины которого можно по-
строить путь в любую другую его вершину.
12. Дан граф. Написать функцию, определеющую является ли он деревом.
Деревом называется связный граф без циклов.
13. Построить каркас заданного графа алгоритмом Краскала (1956). Реа-
лизовать решение в виде функции. Алгоритм заключается в следующем. По-
следовательно в каркас включаются ребра с наименьшей длиной так, чтобы
получившаяся часть каркаса не содержала циклов. Для проверки наличия
цикла можно использовать алгоритм Дейкстры: если рассматривается ребро
<a, b>, то ищем путь в построенной части каркаса из узла a в узел b. Если
путь будет найден, добавление ребра приведет к образованию цикла, т.е. это
ребро в каркас не включаем. Если же цикла не будет, то ребро включается в
каркас.
133
. Практикум по курсу «Алгоритмизация и программирование». Часть 2
8. Дан граф. Написать функцию, которая находит путь максимальной
длины, исходящий из заданной вершины.
9. Дан граф. Написать функцию поиска пути максимальной длины в гра-
фе.
10. Дан граф. Написать функцию поиска медианы графа, т.е. такой его
вершины, что сумма расстояний от нее до остальных вершин минимальна.
11. Дан граф. Написать функцию, определяющую является ли он
связным. Связным называется граф, из каждой вершины которого можно по-
строить путь в любую другую его вершину.
12. Дан граф. Написать функцию, определеющую является ли он деревом.
Деревом называется связный граф без циклов.
13. Построить каркас заданного графа алгоритмом Краскала (1956). Реа-
лизовать решение в виде функции. Алгоритм заключается в следующем. По-
следовательно в каркас включаются ребра с наименьшей длиной так, чтобы
получившаяся часть каркаса не содержала циклов. Для проверки наличия
цикла можно использовать алгоритм Дейкстры: если рассматривается ребро
, то ищем путь в построенной части каркаса из узла a в узел b. Если
путь будет найден, добавление ребра приведет к образованию цикла, т.е. это
ребро в каркас не включаем. Если же цикла не будет, то ребро включается в
каркас.
133
