Course_manual

Mark [u] = 2;	// вершина u помечается как обработанная
вершина	//прохождение графа, пока есть необнаруженные
while (flag)
{	//вершины компоненты связности вершины u
for (i = 0; i < Vt [u ] . kol; i++)		//просмотр списка смежности
вершины u		//выбор из списка смежности u
{ v = Vt [u ] . adj[i];
вершины		//если вершина v уже была
if (Mark [v] = = 1)
обнаружена,	//то считать ее обработанной
Mark [v] = 2;
else if (! Mark [v] )	Mark [v] = 1; //если вершина v обнаружена сейчас,
}	//то считать ее обнаруженной
for (i = 0; i < n && Mark [i] != 1; i++) ;		//просмотр списка меток и поиск
вершин	//обнаруженных на предыдущем шаге
if (i ==n) flag = 0;
else { u = i; Mark [u] = 2; }		//если такая вершина есть, то
продолжаем	//обход, начиная с этой вершины
}

}

void main ( void )

{

int i, s, flag;

//ввод исходных данных vvod_graf ( );

Mark = (int*) calloc ( n, SI ); //выделение памяти под массив меток

for ( i = 0; i < n; i++) Mark [i] = 0;

printf (“\n Задайте исходную вершину”);

scanf ( “%d”, &s );		//ввод метки исходной вершины
s --;
proverka ( s );		//проход графа, начиная с заданной
вершины
// вывод результатов
f = fopen( “spisok.out”, “w” );
printf (f, “%d “, s +1 );
printf (f, “\n“ );
for ( i = 0; i < n; i++ )
if (i != s && ! Mark [i] )	//все необнаруженные после прохода графа
вершины		//выводятся как не достижимые из
printf (f, “%d “, Vt [ i ] . mv);

заданной s

printf (f, “\n”); fclose ( f );

}

Рассмотрим работу программы на примере неориентированного графа, представленного на рис. 1.7. В графе 9 вершин, вершины помечены целыми числами, начиная с 1.

Рис. 1.7.

Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в формате аналогичном задаче 1 (см. 1.3.3.).

Исходный файл для графа на рис. 1.7.:

9
1	3	2	3	4
2	2	1	3
3	3	1	2	4
4	2	1	3
5	1	6
6	1	5
7	2	8	9
8	1	7
9	1	7

В программе эта структура реализована в массиве динамической памяти Vt, элементы которого представлены структурой, содержащей номер вершины, число смежных с ней вершин, указатель на список смежности. Списки смежности также хранятся в массивах динамической памяти. Метки вершин одной компоненты связности – в массиве Mark. Значения элементов структуры смежности заданного графа приведены на рис. 1.8.

Рис. 1.8.

	mv	kol	adj
1	1	3
							1	2	3
2	2	2
							1	2
3	3	3
							1	2	3
4	4	2
							0	2
5	5	1
							5
6	6	1
							4
7	7	2
							7	8
8	8	1
							6
9	9	1
							6

Пусть задана вершина (для которой находим все недостижимые от нее вершины) s = 2. Вначале все вершины помечаются нулем (в массиве Mark) как не обнаруженные (белые). Заданную вершину сразу помечаем как обработанную (меткой 2). И пока есть не обработанные вершины (flag = = 1) просматриваем списки смежности, начиная со списка смежности заданной вершины. Затем списки смежности вершин смежных с заданной и т. д. При этом помечая обнаруженные смежные с текущей вершиной вершины единицей. Текущая вершина перед просмотром ее списка смежности помечается как обработанная (меткой 2). Обход графа в ширину осуществляется в соответствии с порядком нумерации вершин графа и обеспечивается тем, что поиск еще не обработанных вершин начинается всегда с первой вершины. Проход графа в ширину заканчивается, когда среди меток вершин в массиве Mark не будет найдена метка со значением 1 (т.е. будут просмотрены все вершины одной компоненты связности). Вершины, метки которых остались равны 0 являются не достижимыми от заданной вершины. Состояния массива Mark после просмотра списка смежности очередной вершины отражены в таблице (для заданной вершины s = 2).

				0	1	2	3	4	5	6	7	8
Mark
Начальное значение				0	0	0	0	0	0	0	0	0
После		просмотра		1	2	1	0	0	0	0	0	0
списка		смежности
вершины 2
После	просмотра		списка	2	2	2	1	0	0	0	0	0
смежности вершины 1
После	просмотра		списка	2	2	2	2	0	0	0	0	0
смежности вершины 3

Результаты работы программы выводятся в файл spisok.out в следующем формате:

•в первой строке файла метка (номер) заданной вершины графа;

•во второй строке файла метки (номера) не достижимых вершин графа, если все вершины достижимы вторая строка будет пустой.

Выходной файл для графа на рис.1.7. :

2

5 6 7 8 9

2.4.Кратчайшие пути в графе

2.4.1.Кратчайшие пути в графе от одной вершины

Алгоритм поиска в ширину можно рассматривать как решение задачи о кратчайшем пути в частном случае, когда вес каждого ребра равен единице (т.е.,

граф не взвешенный). В полной задаче о кратчайшем пути нам дан ориентированный взвешенный граф G = (V, E) с весовой функцией w: E→ R.

Весом пути p = (v0 ,	v1 , . . . , vn ) называется сумма весов ребер, входящих в
этот путь:
	k
	w( p) = ∑ w(v			,v ).
	i=1		i−1	i
Вес кратчайшего пути из u в v равен
	p		если существует путьиз u в v,
δ (u,v) = min{w( p) : u →v},
∞,			иначе.
Кратчайший путь из	u в v – это любой путь p из u в v, для которого					w
(p) = δ (u, v). Если p = (v1 , v2 , . . . , vk ) –			кратчайший путь из		v1 в vk и	1 ≤ i
≤ j ≤ k, то pi j = (vi , vi+1	, . . . , vj ) есть кратчайший путь из vi				в vj .
Весами ребер могут быть расстояния,		времена, стоимости, штрафы, убытки, –

то есть любая величина, которую мы хотим минимизировать, и которая обладает свойством аддитивности.

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

На рис. 1.9. (а) приведен взвешенный ориентированный граф, в вершинах указаны веса кратчайших путей из вершины s. На следующих рисунках показаны (серыми ребрами) два его дерева кратчайших путей (б) и (в) с корнем s.

Рис. 1.9.

Кратчайшие пути и релаксация

Релаксация является общим приемом в алгоритмах поиска кратчайших путей. Он состоит в постепенном уточнении верхней оценки на вес кратчайшего пути в данную вершину – пока неравенство не превратится в равенство. Для каждого ребра v V храним некоторое число d [v], являющееся верхней оценкой веса кратчайшего пути

из начальной вершины s в вершину v (для краткости будем называть его просто оценкой кратчайшего пути). Начальное значение оценки кратчайшего пути для

вершины s равно 0, для всех остальных вершин равно ∞	(d [s] = 0, d [v] = ∞
для остальных вершин).

Релаксация ребра (u, v) E состоит в следующем: значение d [v] уменьшается до d [u] + w (u, v), если второе значение меньше первого; при этом d [v] остается верхней оценкой пути из s в v, так как для всякого ребра (u, v) E справедливо

δ (s, v) ≤ δ (s, u) + w(u, v).

2.4.2. Алгоритм Дейкстры

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G(V, E) с исходной вершиной s, в котором веса всех ребер неотрицательны (w (u, v) ≥ 0 для всех (u, v) E).

Алгоритм Дейкстры использует представление графа списком смежных вершин Adj [v]. В процессе работы алгоритма формируется множество S V, состоящее из вершин v, для которых δ (s, v) уже найдено (то есть d [v] = δ (s, v)). Роль множества S аналогична роли черных вершин при поиске в ширину. Осуществляя проход графа в ширину, начиная с начальной вершины s, алгоритм выбирает очередную вершину u V \ S с наименьшим d [u] , добавляет u к множеству S и производит релаксацию всех ребер, выходящих из u, после чего процесс повторяется. Вершины, для которых δ (s, v) еще не найдено (т.е. не пройденные вершины), хранятся в очереди Q с приоритетами, определяемыми значениями оценок кратчайшего пути – d. Так как кроме весов кратчайших путей, как правило, требуется найти и сам путь, как и при поиске в ширину, для каждой вершины v V запоминается ее предшественник

Pr [v] (предшественник вершины – это либо вершина, либо nil, если предшественника нет).

DIJKSTRA (G, w, s)

1 { for ( каждая вершина v V)

2{ d [v] ← ∞;

3 Pr [v]← nil; }

4 d [s] ← 0;

5S← 0;

6Q ← V [G];

7while ( Q ≠ )

8{ u← Extract-Min (Q);

9S←S {u};

10	for ( каждая вершина v Adj [u] )
11	if ( d[v] > d [u] + w (u, v) )
12	{d [v]← d [u] + w (u, v); Pr [v]← u;}

13}

14}

Алгоритм начинается с инициализации (строки с 1– 4) оценок кратчайшего пути d и предшественников вершин Pr. Для всех вершин, кроме s оценки имеют

бесконечные значения, для s оценка равна нулю. Предшественники вершин равны nil. Множество S инициализируется как пустое (строка 5). В очередь Q помещаются все вершины (строка 6). При каждом исполнении цикла (строки 7– 13), пока очередь Q не пуста, из нее удаляется вершина u с наименьшим значением d [u] (строка 8 – вызов процедуры Extract-Min – удаление из очереди с приоритетом). Эта вершина добавляется к множеству S (строка 9) (первый раз это будет вершина u = s, так как при инициализации только d [s] имеет наименьшее значение, оно равно 0).

Затем просматриваются все вершины смежные с вершиной u (строки 10–12). Каждое ребро (u, v), выходящее из u, подвергается релаксации (строки 11–12). При этом для пути из s в вершину v могут измениться оценка кратчайшего пути d [v] и предшественник Pr [v], если d [v] > d [u] + w (u, v).

После завершения алгоритма для всех вершин u V будут выполняться равенства d [u] = δ (s, u). По завершении поиска кратчайших путей цепочка предшественников в Pr, начинающаяся с произвольной вершины v, будет представлять собой кратчайший путь (точнее один из кратчайших путей) из s в v (в обратном порядке). Выполняя действия подобно процедуре Print_Path, приведенной выше, можно, используя Pr, легко найти эти пути.

Рис. 1.10.

На рис. 1.10. для ориентированного взвешенного графа (а) последовательно показано выполнение алгоритма Дейкстры. Исходная вершина – s. В вершинах указаны оценки длин кратчайших путей. Серым цветом выделены ребра (f, g), для которых Pr [g] = f. Черные вершины – это вершины, которые лежат в множестве S, остальные находятся в очереди Q. Серая вершина имеет минимальное значение d и выбирается из очереди в качестве вершины u (что соответствует действию в строке 8 алгоритма). На рис. (б–е) показаны последовательные состояния после каждого выполнения цикла while. На рисунке (е) значения d и Pr – окончательные.

III. Варианты заданий

Тема: Графы, деревья, системы дорог

1. Найти все вершины заданного графа, недостижимые от заданной его вершины.

2. Определить, верно ли, что для любой пары вершин заданного орграфа одна из этих вершин достижима от другой.

3.Определить, является ли ободом заданный граф.

4.Определить, является ли связным заданный граф.

5.Найти длину кратчайшего цикла в графе.

6.Для двух выделенных вершин графа построить соединяющий их простой путь.

7.Найти самый длинный простой путь в графе.

8.Найти все вершины графа, к которым существует путь заданной длины от выделенной его вершины.

9.Найти такую нумерацию вершин орграфа, при которой всякая дуга ведет от вершины с меньшим номером к вершине с большим номером.

10.Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

11.Источником орграфа назовем вершину, от которой достижимы все другие вершины; стоком — вершину, достижимую от всех других вершин. Найти все источники и стоки данного орграфа.

12.Известно, что заданный граф — не дерево. Проверить, можно ли удалить из него одну вершину (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево.

13.Подсчитать количество компонент связности в дополнении заданного

графа.

14.Найти такую вершину заданного графа, которая принадлежит каждому

пути между двумя выделенными (различными) вершинами и отлична от

каждой из них.
15. Вершины	и ребра	графа	назовем его элементами. По графу G
построить граф	T(G), у	которого	в качестве вершин взяты элементы G, а

две вершины смежны тогда и только тогда, когда соответствующие элементы в

Gсмежны или инцидентны.

16.Пусть d (u) – степень вершины и в графе G. Степенью ребра x = u,v

назовем неупорядоченную пару d (u), d (v) . Определить, совпадают ли

степени всех ребер заданного графа, и если нет, то можно ли удалить из него одну вершину (вместе с инцидентными ребрами) так, чтобы полученный граф обладал этим свойством.

17. По графу G построить граф K(G) с тем же множеством вершин, что и

у G; вершины в K(G)	смежны тогда и только	тогда, когда расстояние
между ними в G не	превышает 2. Проверить, совпадают ли степени всех
вершин в K(G), и если нет, то нельзя ли удалить		из него одну вершину так,

чтобы полученный граф удовлетворял этому требованию.

18.Задан орграф с циклами. Проверить, можно ли удалить одну вершину так, чтобы в полученном орграфе не было циклов.

19.По графу G построить граф G' следующим образом: в качестве вершин в G' берутся ребра графа G: две вершины в G' смежны тогда и только тогда, когда смежны соответствующие ребра в G. В G' найти все вершины, расстояние от которых до некоторой выделенной равно 2.

20.В дереве, все вершины которого имеют степень не больше 3, найти самый длинный путь от выделенной вершины до вершины со степенью 1.

21.Из графа удалить все вершины, от которых недостижима заданная.

22.Для заданного натурального n (n ≥ 3) построить граф, не содержащий циклов длиной 3, в котором степени всех вершин равны 3.

23.Найти диаметр графа, т. е. максимум расстояний между всевозможными парами его вершин.

24.Вершина графа называется точкой сочленения, если ее удаление приводит к увеличению числа компонент связности. Найти все точки сочленения заданного графа.

25.Найти медиану графа, т. е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.

26.	По графу	G построить последовательность графов G1, ..., Gn с
тем же множеством вершин, что и у G (здесь п — максимум расстояний для
пар	вершин в G,	между которыми имеется соединяющий их путь). Ребро

между вершинами в Gi проводится тогда и только тогда, когда расстояние между соответствующими вершинами в G не превышает i.

27.Гамаком называется подграф заданного графа с таким непустым множеством вершин A, что существует не более одной вершины в A, к которой ведут ребра от вершин вне A, и не более одной вершины вне A, к которой ведут ребра от вершин множества A. Найти количество различных гамаков графа.

28.Задана система односторонних дорог. Найти путь, соединяющей

города	А и В и не проходящий через заданное множество городов.
29.	Система	двусторонних дорог	называется	трисвязной,	если для
любой четверки разных городов A,В,С,D существует два				различных	пути из A
в D причем один		из них проходит через В, а другой — через С. Определить,
является ли трисвязной данная система двусторонних дорог.
30. В системе двусторонних дорог для			каждой пары	городов указать длину
кратчайшего пути между ними.
31.	Задана система двусторонних дорог. Найти два города и соединяющий

их путь, который проходит через каждую из дорог системы ровно один раз.

32.Задана система двусторонних дорог. Найти замкнутый путь длиной не более 100 км, проходящий через каждую дорогу ровно один раз.

33.В заданном графе указать все его четырехвершинные полные подграфы.

34.Задана система двусторонних дорог, причем для любой пары городов можно указать соединяющий их путь. Найти такой город, для которого сумма расстояний до остальных городов минимальна.

35.По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более

100 км.

36.По системе двусторонних дорог определить, можно ли, построив какие- нибудь новые три дороги, из заданного города добраться до каждого из остальных городов, проезжая не более 100 км.

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

38.Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Определить N-периферию для заданного N.

39.Определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.

40.В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города A в город В с минимальной величиной S + Р, где S — сумма длин дорог пути, а Р — сумма пошлин проезжаемых дорог.

41.Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города А в город В (который может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.

42.В орграфе без циклов выделены вершины v и w. Найти какое-нибудь множество путей М из v в w такое, что ни одна вершина, кроме v и w, не лежит на двух путях из М и любое расширение М приводит к нарушению этого свойства.

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

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

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

46.	Множество целых чисел представить в виде дерева двоичного поиска
и на основе этого представления упорядочить
это множество.
47.	Проверить, является ли заданное дерево двоичного поиска АВЛ-

деревом.

48. К множеству целых чисел S, представленному в виде АВЛ-дерева, добавить число п так, чтобы множество S {n} также оказалось представленным в виде АВЛ-дерева.

49.Решить предыдущую задачу для случая, когда число п требуется удалить из множества S.

50.Множество целых чисел S представляется в виде 2-3-дерева следующим образом: листьям приписываются элементы S (в любом порядке), а нелисту v — наименьшее из чисел в поддереве с корнем v. По

множествам S1 и S2 , S1 ∩S2 = , построить соответствующее представление

для S1 S2 .

51. Множество целых чисел S представлено в виде 2-3-дерева следующим образом: листьям приписаны элементы S в порядке возрастания слева направо; нелисту и приписана пара чисел (а, b), где а — наибольшее число в поддереве, корнем которого является самый левый преемник v, a b — наибольшее из чисел в поддереве, корень которого есть второй преемник v. Добавить к S число п так, чтобы множество S {n} оказалось представленным

таким же образом,

52.Решить предыдущую задачу для случая, когда число n требуется удалить

из S.

53.Найти максимальное по числу вершин подмножество попарно

несмежных вершин заданного графа (с n ≤10 вершинами).

54.Для заданных k, п (k < п <10) вершинам графа с п вершинами сопоставить натуральные числа 1,2, ..., k (краски) таким образом, чтобы смежным вершинам были сопоставлены разные числа.

55.Компонентой сильной связности в орграфе называется такой его

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

56.Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины.

57.Определить, изоморфны ли два заданных графа.

58.Определить, изоморфен ли заданный граф своему дополнению.

59.	Подсчитать			количество		попарно		не	изоморфных	графов с п
вершинами и четырьмя ребрами.
60.	Пусть		фиксирована		нумерация вершин				орграфа. Дуга называется
обратной при этой нумерации,						если	она	ведет от вершины с большим
номером		к	вершине с меньшим			номером. Построить такую				нумерацию
вершин		заданного орграфа,			при которой число обратных дуг минимально.
61.	Подмножество			вершин графа			назовем		доминирующим, если каждая

вершина вне подмножества смежна хотя бы с одной вершиной этого

подмножества. Найти минимальное по числу вершин	доминирующее
подмножество вершин заданного графа.
62. Будем говорить, что вершина графа накрывает	ребро, если она

инцидентна этому ребру. Вершинным покрытием графа назовем множество