close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Лабораторная работа №4.
Работа с графами.
Задание:
1. Разработать GUI - приложение в среде Qt Creater, Eclipse CDT или MS Visual C++, решающее задачу согласно Вашему варианту.
Варианты задания:
1. Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна.
2. Задана система односторонних дорог. Найти путь, соединяющий города и , и не проходящий через заданное множество городов.
3. В системе двухсторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.
4. Задана система двусторонних дорог. Найти замкнутый путь длиной не более , проходящий через каждую дорогу ровно один раз.
5. По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города нельзя было попасть в город .
6. Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз.
7. Система двухсторонних дорог называется трисвязной, если для любой четверки разных городов существует два различных пути из в , причем один из них проходит через , а другой - через . Определить, является ли трисвязной данная система двусторонних дорог.
8. По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более .
9. В системе двусторонних дорог за проезд каждой дороги взимается - некоторая пошлина. Найти путь из города в город с минимальной величиной , где - сумма длин дорог пути, а - сумма пошлин проезжаемых дорог.
10. Задана система двусторонних дорог. -периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше . Определить -периферию для заданного N.
11. Определить, можно ли в заданной системе односторонних дорог проехать из города в город таким образом, чтобы посетить город и не проезжать никакой дорогой более одного раза.
12. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города в город (который может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.
13. По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого из остальных городов, проезжая не более .
14. В заданном графе указать все его четырехвершинные полные подграфы.
15. Вершины и ребра графа называют его элементами. По графу построить граф , у которого в качестве вершин взяты элементы , а две вершины смежные тогда и только тогда, когда соответствующие элементы в смежные или инцидентны.
16. Для заданного натурального числа вершин построить случайный граф, не содержащий циклов длины 3, в котором степени всех вершин равны 3.
17. Говорят, что вершина графа накрывает ребро, если она инцидента этому ребру. Вершинным покрытием графа называется множество вершин, накрывающих все его ребра. Построить минимальное по числу вершин вершинное покрытие заданного графа.
18. Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины.
Пояснение: в заданиях предполагается, что в системе дорог каждая -я дорога имеет некоторую длину в условных единиц.
Кроме того, во всех вариантах необходимо реализовать следующий набор операций для исследования графа (и/или системы дорог, представляемых графом):
1. Подсчет степени вершины для любой указанной вершины.
2. Нахождение -го яруса для заданной вершины.
3. Подсчет диаметра графа.
4. Подсчет числа компонент связности.
5. Нахождение всех точек сочленения графа.
6. Проверка того, является ли граф деревом.
7. Удаление всех изолированных вершин графа.
Документ
Категория
Рефераты
Просмотров
515
Размер файла
81 Кб
Теги
лабораторная
1/--страниц
Пожаловаться на содержимое документа