Задачи № 2
Реализовать поиск в глубину в неориентированном графе. Вывести все вершины в порядке обхода.
Реализовать поиск в глубину в ориентированном графе. Вывести все вершины в порядке обхода.
Реализовать алгоритм топологической сортировки в ориентированном графе.
Реализовать поиск в ширину в неориентированном графе. Вывести все вершины в порядке обхода.
Реализовать поиск в ширину в ориентированном графе. Вывести все вершины в порядке обхода.
С помощью поиска в глубину проверить связность графа.
С помощью поиска в глубину найти компоненты связности графа.
С помощью поиска в ширину найти компоненты связности графа.
С помощью поиска в глубину определить число компонент связности графа.
С помощью поиска в ширину определить число компонент связности графа.
В ориентированном графе найти компоненты сильной связности.
Написать программу, определяющую по двум вершинам принадлежность их к одной компоненте связности.
Написать программу, находящую наибольшую по числу вершин компоненту связности графа.
Написать программу, находящую наибольшую по числу рёбер компоненту связности графа.
Написать программу, определяющую, содержит ли неориентированный граф циклы с помощью поиска в глубину (в ширину). Если содержит, восстановить любой цикл.
Написать программу, определяющую, является ли неориентированный граф деревом с помощью поиска в ширину.
Написать программу, строящую остов связного графа с помощью поиска в глубину. Остовом (неориентированного) связного графа G=(V,E) называется его частичный граф S=(V,T), являющийся деревом. Частичный граф --- это подграф, содержащий все вершины исходного графа и подмножество его рёбер.
Написать программу, строящую коостов связного графа (частичный граф, порождаемый ребрами, не входящими в заданный каркас (остов)).
Проверить, является ли граф деревом с помощью построения его остова с помощью поиска в ширину.
Написать программу, проверяющую Эйлеровость связного графа, т. е. наличие в нем эйлерова цикла, содержащего все рёбра графа по одному разу (вершины могут повторяться).
Замечание: согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Проверить достижимость вершины графа их указанного множества вершин.
Построить дерево кратчайших путей из указанной вершины в графе.
Построить дерево кратчайших путей из указанной вершины в ориентированном графе.
С помощью поиска в глубину проверить является ли заданное ребро графа мостом. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности).
С помощью поиска в ширину проверить является ли заданное ребро графа мостом.
Найти мосты в связном неориентированном графе.
Проверить неориентированный граф на двудольность, т.е.можно ли разделить его вершины на две доли так, чтобы не было рёбер, соединяющих две вершины одной доли.
Указание. Произведём серию поисков в ширину. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли
Найти точки сочленения в связном неориентированном графе. Точкой сочленения называется такая вершина, удаление которой делает граф несвязным.
С помощью поиска в глубину проверить является ли заданная вершина графа точкой сочленения.
С помощью поиска в глубину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.
С помощью поиска в ширину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.
Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик рекурсии WG).
Для графа дерева найти длину кратчайшего пути от вершины U до V (использовать поиск в ширину и счётчик слоёв).
Для графа дерева найти кратчайший пути от вершины U до V (использовать поиск в ширину или волновой алогритм).
Во взвешенном неориентированном графе найти кратчайший путь между двумя вершинами.
Реализовать алгоритм поиска в ширину и определить вершину, наиболее удалённую от начальной вершины r.
С помощью поиска в глубину проверить, что в ориентированном графе данное множество вершин W является порождающим, т.е если из вершин W можно достичь любую вершину графа.
С помощью поиска в ширину проверить, что в ориентированном графе данное множество вершин является порождающим.
Найти наибольшее паросочетание в неориентированном связном графе.