Элементы теории графов

5

o

ïåì. 2o:делаем текущей конечную вершину ýòîй дуги. Переходим к

Если выбранная на предыдущем

га являетс

перешей-

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

текущеé âершинû, ïомечаåì åå è ïåðåõîäèì

ê ï. 4

o

.

Âûïîëíåíèå àëãîритма ñâîäèì â ñëåдующую таáëèöó.

N

1; 5

2; 6

3; 1

3; 5

4; 6

5; 7

5; 8

6; 3

6; 8

7; 3

8; 2

8; 4

I

0

1

1

+

+

5

2

+

7

3

+

3

4

+

5

5

+

8

6

+

2

7

+

6

8

+

8

9

+

4

0

+

6

1

+

3

12

столбец

первого

последнего)

отвечает дуге

1

Ê

æäûé

(кроме

оргра

мечаем

номер шага выполнения

алгоритма,

ïоследн

номер

. Для пометки дуги ставим над ней черту. В

ервом

îò-

екущей вершины. Если рас матр ваемая дуг

ÿâ

яется

столбцерешейком,

дугизаносим новую текущую вершину. По кончании алгоритма столбец

ставим минус. В противном случае став

ïëþñ

помечаем дугу

òо на пересечении текущей строкè выполнен я

столбца

горитма

уга (6,3)алгоритмаакжå является перешейком,перешейкОтметим,ак ак из вершины

кущей вершины определит эйлеров кîíòóð.

÷òî íà øàãå

4 выполнения

дуга (3,1) является

îì,

àê êàê èç

âå øèíû

1 íåò óæ

вых дящих непомеченных

потому нет пути

до вершины 3 в гра е н

ченных дуг. На шадуг 8 выполнения ал-

3 можно äостиг уть толькпомвершины 1 в гра е непомеченных дуг, но

никак не вершиíû 6.

61

контур:				(1; 5; 7; 3; 5; 8; 2; 6; 8; 4; 6; 3; 1):
14.1		Индивидуальное задание 7
		Общее задание					ребер с их длинами, найти крат
1. Для г а а, заданного списк
íþþ	вершину			(с наибольшим
a) описать алгоритм Дейк трыномером):нах ждения кратчайшего маршрута
чайший ма шрут из первой вершины гра а (с номером 1) в послед-
		гра е с яснением вñех вводимых в алгоритме обозначений;
b)	свести выполнение алгоритма для заданного гра а в т								выделе-
	построить реализацию гра а с указанием длин
	нием жирными ребрами найденного кратчайшегореберма шрутаблицу;.
2. Для гра а (или оргра а), заданного матрицей смежности вер-
шин, найти эйлеров маршрут (цикл, контур, цепь, путь):
a) анализировать гра на существование эйлерова маршрута (цик
	ла, контура, цепи, пути), с ормулировав соответствующий кри-
	терий существования;
b) описать алгоритм нахождения эйлерова маршрута (цикла или
	контура, цепи, пути);							гра а в таблицу;
d)	свести выполнение алгоритма для
	выписать полученный маршрут в кзаданногочестве результата.
14.2 Варианты индивидуального задания 7
1.	(	31 42	12	31 63	24	Задача 1		6),1 ({5,62 }, 2), ({5,8},2 6 7),4
						41 64	3 , ({4,7},2 3
		({6,7}, 3), ({6,8}, 6), ({7,8},					62) ).

4

3.

5.

6.

7.

8.

9.

10.

11.

12.

(	3 5		,
	1	72
	4,68		,
(	3	8	,
	1 2
(	3
	1 2
	3 4		,
(	6,7
	1 2
	3 5		,
(	6,7
	1 2
	3 6		,
(	7,9
	1 2
	3	7	,
(	7,
	1 2
	3	8	,
(	8,9
	1 5
	3 4		,
(	4,8
	1 5
	2
	({4,8},

2			3 6				12				3			1	({4,7},
1	, (({6 8							,			5,68			27	). 5,81
			1	6							1			3		2 3
	,				,		4			({4,7}, 5), ({5,6},
3	, ({3,7},						2),			({4,8}, 4), ({5,7},
4	,		1	8			2			).	1			3		2 3
2
1			1					, ({4,5}, 2), ({4,7},
2				6							4 6			4		2 3
3			1												, ({4,7},
	,							,			1 4		,		).	2 3
1			6 8								7,8			2
				6			4				3 7				({4,7},
2			6 8								7			3	).	1
			1						).		1
4		({8,9},				2)					1 4					1
1			1 3
2	, ({4,7}, 1),										5,8 , 2), ({5,9},
1	, ({4,7}, 3),({8,9},5,7 , 1), ({5,8},
3		({7,9}, 6),									1 4			5) ).		1
		).	1 3				2							4
62			3 5				4				3 6			3		2
3														2 , ({3,7},
6			1 6		, 1 ,						1 7		,	5	).	2
2	, ({5,			5							6,	6		1
			3				2				3				, ({3,8},
2), ({5,6},							4), ({5,7}, 1)								).
														63

6),1),4

2), 3),1 4),1

3),1

3),

2),7

2),6 3),2

6),4

({5,6},6,85,82 , ({ }

({5,82 }, ({5,62 }, ({5,62 },

({6,92 3},

({6,72 },

({6,92 7}, ({3,82 5},

({4,52 },

6),4),42

4),3 1),5

1),3

3),1

1),2

4), 6),2

1),

({6,7},({5,8},7,83 5

({6,7},2

({5,8},2 6

({5,8},3 4

({7,8},2 6

({6,9},3

({7,9},3 6 ({4,7},2 8

({4,7},2 5

1),6),4 ).

1),5 3),4

4),1

1),4

6),1

2)3 , 6),7

1),2

14.(

15.(

16.(

17.(

18.(

19.(

20.(

21.(

22.(

23.(

22,841,7852 ,

3,4 ,

61 85

3,4 ,

41 82

3,6 ,

51 83

2,9 ,

71 82

3,8 ,

71 2

3,7 ,

81 95

2

4 , ({41 5}

3,841 5 ,

1			3,4			,
3			2		6
6					8
	, ({6,				3
3			1
			3		7	,
4	, ({7,8
2			1		6
1	,		3			,
4			5,
2			1
4			3
	, ({6
			1	5
3	,		3
					9
2			1 3
					6	,
4					9
			1 3
1	, ({4,7},
4		).
7			3		4
2						,
3	, ({5,
6			1 6
1			3	5		,
56			51

4), ({4,6},

1			1 7		,
4	,	({3,5},
5		).	1
		({4,5},
2		).		7
4			3 8
3			1	6	,
1	,		6,7
			3
2	,		7,8
			1
		({4,6},
4)		).
1			4
2
6			1 4
4),			8,9
		({5,6},
6			3 6
1
	,		1 7		,
			6,	6
2			3
1),		({4,7},
4			61

14			2	4),1	4,72	2	4,82 5	6)4 ).
5),		({3,8},		2),	({4,6},	4),	({4,7},	2
3			2 3	1	2	1	2
2),		({4,8},		4),	({5,6},	3),	({6,7},	1),
2	, ({2,4}, 1), ({2,5}, 5), ({2,8}, 3),
		({4,5}, 4), ({4,6}, 2), ({4,7}, 4),
1	,	).		1),3	({4,72 6}, 3),1		({5,6},3	2),
4		({4,6},2 5
4		).	1 8	3	2 6	4	2 4	3 ,
2
1),		({4,7},		2),	({5,7},	1),	({5,9},	2)
27	,	({5,7},1		1),2	({6,2 7},	1),2	({6,9},2 8	5)1 ,
63		).	1	2	2 7 3		3 6	2)	,
1),		({5,8},		3),	({6,9}, 6),		({7,9},
2	,	({3,8},2		4),1	({4,62 5}, 3),2		({4,7},2 6	6),4
3		).		1),4	({3,82 5}, 6),1		({4,7},2 8	1),2
2	, ({3,7},2
		).	2 5 2		2 8 1		3 7		,
1), ({4,8}, 7), ({5,6}, 2), ({5,8},								4) ).
64

25.(

26.(

27.(

28.(

29.(

30.(

31.(

32.(

33.(

34.(

4

2531,865 ,

2,8 ,

41 5

3,4 ,

41 86},

51 95

51 69 ,

8 ,

3,51 92 ,

61 72 ,

1 82

({2,7},

6 8

214	, ({63,74				,
3			1 6
2			3	4	,
4	, ({5,
			1 6
1			3 5		,
2	, ({5,6
3	,		1	7	,
			7 8
2			1 6
1			6		,
7
4			1 7
1	, ({3,9},
6		).
7			3 6
4					,
1	, ({6,8
2			1 3
			3 6		,
6			6 8
1	, ({4,7
4			1 3
			3 5

1), ({7,8},

42		({3,8},1				4),({2,3},({4,6},1), ({2,5},({4,7},3),5),({2,6},({4,8},5),
1)		).
4	, ({3,7}, 2), ({3,8}, 4), ({4,5}, 2), ({4,7}, 3),
	,		3	6	,	42	, ({3,8},2			2),1 ({4,62 5}, 2),5 ({4,7},2 6 4),
1			6,			1	).	2		1	2 5		3	2 8
2			1 7
			3 6			4 , ({3,7}, 2), ({3,8}, 4), ({4,7}, 3),
4) ({1,8},2),							({2,3}, 1), ({2,6}, 4), ({2,9}, 2),
1	,		6 7				).
2		({3,9}, 4), ({4,8}, 4), ({4,9}, 3), ({5,7}, 3),
1		).		7				1 8		5	2 6			2 9	1
6
2			3 9			2 , ({4,7}, 1), ({4,9}, 2), ({5,8}, 2),
1		({1,8},6),					({2,7},				({2,9}, 3), ({3,6}, 3),
			7			1	).			4), ({5,7}, 1), ({5,8}, 2),
2),		({4,7},				3), ({4,9},
2			3 7			6	, ({4,7},2 3 6),2 ({5,62 }, 1),2 ({5,8},3 4 2),3
2	,		4,81		,		).	2	3		2	4	2	2 5	4
4			7			3)		2 3		4	2 4		1	2	2
6			1	5		2
1			7			1 , ({4,7}, 1), ({5,6}, 4), ({5,7}, 1),
2						5	).			1				3 4	2 ,
4								5,8			6,8		4
5										7),				7,8	1) ).
	, ({4,6}, 4), ({4,7},									1), ({5,8}, 3), ({6,7},					2),
4)		).				65

36.(

37.(

38.(

39.(

40.(

41.(

42.(

43.(

44.(

45.(

3521,8,62 ,

6 73

3,5 ,

51 62

3,9 ,

71 84

2,9 ,

51 6

3,7 ,

51 92

3,4 ,

61 72

2 6

3 ,

4,761 2 ,

61 82

({3 },

6 8

43			43	743	,
1	, ({6,8
			1 5
2			3 6		,
	, ({6,7
			1 5
3	,		4 6		,
			8 9
2			1 6		,
			6	8
6			1 7
1	, ({3,9},
4		).	3 7
2					,
3	, ({6,8
6			1 3
1			2 7
			6
4	, ({1 3 ,
2
2				7	,
	, ({4,87
3			1 3
			3 7

4), ({7,8},

3		({3,7}, 5), ({3,8}, 2), ({4,5}, 2), ({5,6}, 3),
1		).			4), ({2,4}, 1), ({2,5}, 5), ({3,4}, 1),
2)		({1,4},
	,				4				2 5	3	2 6		1	2	2
				6	2)		, ({4,7}, 4), ({5,7}, 1), ({5,8}, 2),
			7 8					).
2)		({1,7},			4)		({2,4}, 3), ({2,6}, 4), ({3,5}, 4),
4	,		3,6 8		1	)	, ({4,6}, 1), ({4,7}, 3), ({4,8}, 3),
1								).
		({4,7}, 2), ({4,9}, 4), ({5,7}, 1), ({6,9}, 2),
3		).			6), ({1,8}, 6), ({2,7}, 2), ({2,8},
5)		({1,7},
1					1)			).
2)			3 9				, ({4,6}, 2), ({4,9}, 7), ({5,7},1),
		({1,8},			4),			({2,7},		3),	({2,9}, 4), ({3,6}, 2),
6),		({4,7},						({4,9},			({5,6}, 1), ({5,8}, 3),
42			4 7		23 , ({4,8},2 3 7),1 ({5,62 }, 6),1 ({5,7},2										3),2
1	,		5,61		3			).	2 3	2	2	4	1	2	4
			7 8 ,		6				2 3		2		2	2
			1		5
2			3		1 , ({4,7}, 4), ({4,8}, 6), ({5,6}, 1),
			7 8		2			).	1	7				3 4	2
6				4	4						6,8					).
					1				5,7	1),				7,8
4	, ({4,8}, 6), ({5,6},									5), ({5,7}, 4), ({6,7}, 1),
		).													1),2
5	, ({4,1 5}, 2),3 ({4,8},2 3 4),1 ({5,62 }, 3),1 ({6,7},2
2)		).			66

47.(

48.(

49.(

50.(

51.(

2631,6742 ,

2, ,

71 92

3,7 ,

61 92

3,7 ,

81 93

({2,7},

5 6

5			3
1	, ({62,87				,
2
4			1 3
3	,		3 7		,
			8 9
			1 3
26			71	8	,
				93
6	, ({4,6},
		).	1 4
4
3			2

2), ({5,8},

2	,		3	7	,
3				5
2			71	8
4		({4,6},
2		).	1,9
63
1),		({4,8},
3			1 6
6			3 4

7), ({7,8},

3241 ,)({4,7},({4,8},. 2 3

3), ({5,8},1

27 , ({5,6},1

56 ). 2), ({5,6},1 12), ({3,6},2 2 ).

1),3),

4),3

1),2 3),4

1),2

(({5,6},{4,82 },

({6,82 3},

({6,72 }, ({6,92 7},

({4,72 },

4),2 ({5,6},({5,7},2 3),2),1

1), ({6,9},2 4)2 ,

1),2 ({6,8},2 7 1),

2)3 , ({2,8}, 1), ({7,9}, 4),

6),3 ({5,2},6 2),4

67

1.			2
2.	2		6
			4
	6		0
3.	4	1
	2	0	1
	6	1	1
		0	1
	4
		1	0

10 10

0 00

1 11

1 1

0 0

01

0

1

0

1

1

1

0

1

1 10

0 1

1 1

1 01

0 1

1

1 0

0 1

68

1 1 0

0 0 1

1 1 0

1 1

1

0 0

10 1 1

1 0 01

0 1

3

75 1 3

0 75

1 1 3

10 10 75

5.	6	1
	4	0
		1
6.	2	0
	6	1
7.	4
		0

10

200

64 1

000

1

2

64

1

00

1

01

1

1

0 0

1 1

0 0

1				0
	0		1
0			1	0
	1			1
1	0		0
0			1	0
	1			1
	1		1
	0			0
1		1	1
0				1
		0		0
1		1
	69

011

1

1

0

1

1

0

1

1 0 0 1 1 0 0

0

0 310

1 75

0 0

1

3 0

75

0 7

1 5

0

0 3

01 75

				0			1			1	0			0			1		0
	6	1 1														0				7
				1								1					0	1
	4		0				0						1							5
9.				0					1	1	1	0					1		0
				2	0		1					1		0		0 3
				4	1		0		1	0	0	0		1		1	5
10.		2		6	0		1		0	1	1	1		0		0	7		3
													1				1
				0 1				0		1					1
		6				1				1			0						7
		4		1					1							0		0	5
						0					0	1

70