Лабораторная работа 13

Тема. Граф. Операции над графом.

Цель.

· Получение практических навыков по созданию и управлению структурой данных – граф

ЗАДАНИЕ

Общие для всех вариантов.

1. Разработать структуру представления графа согласно варианту.
2. Разработать процедуру заполнения графа из 10 узлов.

Для каждого варианта

1. Выполнить задание варианта, разместив, определение его подпрограмм и представления графа, в отдельном модуле (Можно представить на классе).
2. Создать приложение, демонстрирующее выполнение заданий варианта и общих операций.
3. При составлении тестов рассмотрите все указанные варианты:

· Полный граф (все узлы связаны между собой)

· Несвязанный граф – представлен несколькими несвязанными между собой подграфами

· Граф не имеет несвязанных компонент и не является полным

ВАРИАНТЫ

	Задание	Характеристики графа и его представление
	Выделено некоторое множество узлов. Построение всех возможных путей от заданного исходного узла к заданному конечному узлу, проходящих через выделенное множество узлов	Неориентированный Невзвешенный Матрица смежности
	Нахождение фундаментального множества циклов, не проходящих через заданное множество узлов. Исходный узел произвольный.	Ориентированый Невзвешенный Список смежных вершин
	Выявление мостов в графе. Определение кратчайшего пути от узла ХО к узлу УО: ХО и УО принадлежат: Одному подграфу Различным подграфам Различным подграфам, образующим последовательность ХО---------------- ---------------- ∙ ∙ ∙ ∙ УО	Неориентированный Невзвешенный Список смежных вершин
	Выявление точек сочленения. Удаление узлов – точек сочленения. Поиск кратчайшего пути между узлами, принадлежащими различным подграфам.	Ориентированный Невзвешенный Список смежных вершин
	Определить диаметр графа. Эксцентрисистет узла j – расстояние (вес пути) от j – ого узла к наиболее удаленному. Диаметр – наибольший из эксцентриситетов.	Ориентированный Взвешенный Матрица смежности
	Определить кратчайшие пути от заданного узла ХО ко всем прочим узлам. Кратчайший путь определяется суммой весов ребер.	Неориентированный Взвешенный Матрица смежности
	Нахождение кратчайших путей во взвешенном графе между заданными вершинами.	Неориентированный Взвешенный Матрица смежности
	Для произвольных узлов найти кратчайший путь с минимальной стоимостью и проходящий (включающий) через некоторое заданное множество узлов. (1,в; 2.а;3.в)	Неориентированный Взвешенный Список смежных вершин
	Определить, какие из ребер можно удалить при соблюдении условия: длины кратчайших цепей от произвольного узла к произвольному узлу остаются прежними. Длина цепи – сумма всех входящих в нее ребер	Неориентированный Взвешенный Список смежных вершин
	Все ребра определенного цвета. Определить, есть ли цепь в графе от истока до стока, окрашенная в один цвет	Ориентированный Взвешенный Матрица смежности
	Все ребра определенного цвета. Задаются два произвольных узла Х и У. Определить все цепи от Х до У, такие, что все ребра, их составляющие окрашены в разные цвета	НеОриентированный Взвешенный Матрица смежности
	Определить, кратчайшие пути от истока до стока	Ориентированный Взвешенный Список смежных вершин
	Нахождение всех циклов в графе, не включающих заданное множество ребер. Граф ориентированный, взвешенный. Все ребра определенного цвета. Определить, есть ли цепь в графе от истока до стока, окрашенная в один цвет	Ориентированный НеВзвешенный Список смежных вершин
	Найти кратчайшие пути от истока графа к заданному узлу. Определить все множество узлов, кратчайшие пути к которым равны найденному	Ориентированный НеВзвешенный Список смежных вершин
	Выявление циклов в графе, включающих заданное множество ребер.	НеОриентированный НеВзвешенный Матрица смежности
	Нахождение цикла в графе с минимальной стоимостью. Стоимость цикла – сумма весов ребер. Исходный узел произвольный.	Ориентированный Взвешенный Матрица смежности
	Определить мосты в графе. Запаралелить мосты таким образом, чтобы при удалении моста не увеличивалось число компонент связности графа. При этом должно сохраниться направление перемещения по графу	Ориентированный НеВзвешенный Матрица смежности
	Граф неориентированный. Медиана - узел, сумма расстояний от которого до остальных узлов минимальна. Центр графа – узел, кратчайшее расстояние от которого до наиболее удаленного от него узла является минимальным. Определить медиану. Определить множество центральных узлов	НеОриентированный НеВзвешенный Матрица смежности
	Поиск истока в ориентированном графе. Исток - узел, от которого достижимы все узлы графа. Найти все истоки графа.	Ориентированный НеВзвешенный Список смежных вершин