Часть 1. Задачи на графах

 

1. Дан ориентированный граф с N вершинами (N<50). Вер­шины и дуги окрашены в цвета с номерами от 1 до М (М<6). Указаны две вершины, в которых находятся фишки игрока и конечная вершина. Правило перемещения фишек: игрок мо­жет передвигать фишку по дуге, если ее цвет совпадает с цве­том вершины, в которой находится другая фишка; ходы можно делать только в направлении дуг графа; поочередность ходов необязательна. Игра заканчивается, если одна из фишек дости­гает конечной вершины. Написать программу поиска кратчайшего пути до конечной вершины, если он существует.

2. Задан неориентированный граф. При прохождении по не­которым ребрам отдельные (определенные заранее) ребра могут исчезать или появляться. Написать программу поиска кратчайшего пути из вершины с номером q в вершину с номером w.

3. Заданы два числа N и М (20<M<N<150), где N — количе­ство точек на плоскости. Написать программу построения дере­ва из М точек так, чтобы оно было оптимальным.

Примечание. Дерево называется оптимальным, если сумма всех его ребер минимальна. Все ребра — это расстояния между вершинами, заданными координатами точек на плоскости.

4. Даны два числа N и М. Написать программу построения графа из N вершин и М ребер. Каждой вершине ставится в соответствие число ребер, входящих в нее. Граф должен быть таким, чтобы сумма квадратов этих чисел была минимальна.

5. Задан ориентированный граф с N вершинами, каждому ребру которого приписан неотрицательный вес. Написать про­грамму поиска простого цикла, для которого среднее геометри­ческое весов его ребер было бы минимально.

Примечание. Цикл называется простым, если через каждую вершину он прохо­дит не более одного раза, петли в графе отсутствуют.

6. Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами верхнего правого угла (100, 100) поместили N (1<N<30) квадратиков. Написать программу поиска крат­чайшего пути из точки (0,0) в точку (100,100), который бы не пересекал ни одного из этих квадратиков. Ограничения:

· длина стороны каждого квадратика равна 5;

· стороны квадратиков параллельны осям координат;

· координаты всех углов квадратиков — целочисленные;

· квадратики не имеют общих точек.

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

7. Задан неориентированный граф с N вершинами, пронуме­рованными целыми числами от 1 до N. Написать программу, которая последовательно решает следующие задачи:

· выясняет количество компонент связности графа;

· находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;

· определяет, можно ли ориентировать все ребра графа та­ким образом, чтобы получившийся граф оказался сильно связным;

· ориентирует максимальное количество ребер, чтобы полу­чившийся граф оказался сильно связным;

· определяет минимальное количество ребер, которые сле­дует добавить в граф, чтобы ответ на третий пункт был утвердительным.

 

8. Задан ориентированный граф с N (1<N<30) вершинами, пронумерованными целыми числами от 1 до N. Разработать про­грамму, которая подсчитывает количество различных путей между всеми парами вершин графа.

9. Задан ориентированный граф с N вершинами, пронумеро­ванными целыми числами от 1 до N. Разработать программу, кото­рая подсчитывает количество различных путей между всеми па­рами вершин графа.

Входные данные. Входной файл input.txt содержит количе­ство вершин графа N (1<N<30) и список дуг графа, заданных номерами начальной и конечной вершин.

Выходные данные. В выходной файл output.txt вывести матрицу N×N, элемент (i,j) которой равен числу различных путей, ведущих из вершины i в вершину j или -1, если существует бесконечно много таких путей.

10. Дан ориентированный граф. Вершинам приписаны веса. Начальная и конечная вершины заданы. Требуется найти путь между этими вершинами с максимально возможным суммарным весом. Путь должен удовлетворять следующим условиям:

· по каждой дуге разрешается пройти один раз;

· если в вершину попадаем по входящей дуге, то к суммар­ному весу вес этой вершины прибавляется;

· если в вершину попадаем по выходящей дуге, то из сум­марного веса вес этой вершины вычитается.

Входные данные. Входной файл input.txt со­держит данные в следующей последовательно­сти:

· N x ₁ х₂... x_N — количество вершин графа и их веса (1≤ N ≤30, 1< х_i <30000);

· b,e  — номера начальной и конечной вер­шин;

· М — количество дуг;

· i1, j1 — номера вершин, соединяемых пер­вой дугой;

· i₂, j₂ — номера вершин, соединяемых вто­рой дугой;

· i_M, j_M — номера вершин, соединяемых ду­гой с номером М.

Выходные данные. В выходной файл output.txt требуется вывести максимальный вес пути и путь, на ко­тором он достигается. В случае, если решение не существует, выходной файл должен содержать единственную строку «решения нет».

11. Дан взвешенный (ребрам приписаны веса) связный граф G=(V,E).

Обозначим через D{v,u} минимальное расстояние между вершинами v,u € V. Величина D(G) = Max(D(v,u)) называется диаметром графа. Величина R(v) = Max(D(v,u)) максимальным удалением в графе от вершины v. Величину R(G) = Min(R(v)) называют радиусом графа. Любая вершина t€V, такая, что R(t)=R(G), называется центром графа.

Разработать программу поиска диаметра, радиуса и центров графа.

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

12. Согласно теореме Д. Кенига (1936 г.) для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины. Определить, является ли заданный граф двудольным.

Примечание. При поиске в ширину вершины графа помечаются метками 0, 1, 2 и т. д. Первой вершине, с которой начинается просмотр, приписывается метка 0, вершинам, связанным с ней, — метка 1 и т. д. Разобьем граф после просмотра на два подграфа: подграф X включает вершины с четными метками, подграф Y — с нечетными. Если оба подграфа пусты — исходный граф является двудольным.

13. Задача Штейнера на графах. В связном взвешенном гра­фе G с выделенным подмножеством вершин U (U € V) требуется найти связный подграф Т, удовлетворяющий двум условиям:

· множество вершин подграфа Т содержит заданное под­множество U;

· граф Т имеет минимальный вес среди всех подграфов, удовлетворяющих первому условию.

Примечание. Очевидно, что искомый подграф является дере­вом, оно называется деревом Штейнера. Задача сводится к нахождению дерева минимального веса в подграфах графа G, множество вершин которых содержит U. Эффективных алгоритмов решения задачи неизвестно, поэтому наиболее простой состоит в переборе вариантов при небольших значениях числа вершин.

14. Задача о пяти ферзях. На шахматной доске 8x8 расставить наименьшее число ферзей так, чтобы каждая клетка доски была под боем.

Примечание. Построить граф для данной доски с учетом пра­вил перемещения ферзя. Всякой искомой расстановке соответ­ствует наименьшее доминирующее множество в графе.

15. Для заданного ориентированного графа с N вершинами разработать :

· структуру представления графа;

· процедуру заполнения графа из N узлов;

· процедуру поиска всех путей от заданной вершины ко всем остальным методом в глубину;

· процедуру поиска кратчайших путей от заданной вершины ко всем остальным методом в ширину;

· процедуру построения остового дерева графа.