Міністерство освіти і науки України

Міністерство освіти і науки України

Національний університет «Львівська політехніка»

Розрахунково-графічна робота

з курсу «Інформатика інфокомунікаційних систем»

на тему: «Рішення задач на графах»

Варіант 11

Виконав:

ст. гр. РА-12

Рапак Ігор

Прийняла:

доц. Атаманова І. В.

Львів – 2015.

Завдання 1. Для заданого неорієнтованого графа розв’язати задачу листоноші.

Будуємо граф:

Вершини з непарним ступенем: (2,5);

Матриця мінімальних шляхів:

Паросполучення: (2,5);

Вага: 2

Ребра повторного обходу: (2,5);

Оптимальний маршрут:

L=(2,3),(3,4),(4,5),(5,6),(6,4),(4,1),(1,2),(2,5),(5,2)=8+7+9+7+7+3+9+2+2=54

Завдання 2. Орієнтований граф заданий матрицею інцидентності.

1. Побудувати граф.

2. Розв’язати задачу листоноші на орієнтованому графі.

	u1	u2	u3	u4	u5	u6	u7	u8
a						-1
b	-1	-1
c			-1
d				-1				-1
e					-1		-1

Будуємо граф G:

В граф G вводимо дві вершини: S-загальне джерело, t-загальний стік:

(a)=2 D(a)=1 - джерело (2

уємо граф і.

тоноші на орієнданий матрицею інцидентності.

0+3=3

(b)=1 D(b)= -1 - стік

(c)=2 D(c)= 1 - джерело

(d)=2 2 D(d)= 0 - проміжна

(e)=1 2 D(e)= -1 - стік

Оптимальний маршрут: L=(a,d),(d,e),(e,c),(c,d),(d,b),(b,c),(c,b),(b,a),(a,e),(e,a).

Завдання 3. За заданою матрицею ваг необхідно:

- побудувати граф;

- побудувати мінімальне (максимальне) остовне дерево;

Будуємо граф:

Максимальне дерево:

L=(6,4),(5,2),(2,6),(6,0),(1,0),(2,4)=25+23+24+23+22+22=139

Мінімальне дерево:

L=(1,6),(5,1),(4,1),(4,3),(3,2),(2,4)=20+21+20+21+20+22=124

c

d

e

b

Завдання 4. На заданому графі розв’язати задачу комівояжера.

a

b

Запишемо матрицю ваг:

	a	b	C	d	e	f
A	∞
b		∞
c			∞
d				∞
e					∞
f						∞

	a	b	c	d	e	f
a	∞
b		∞
c			∞
d				∞
e					∞
f						∞

⇒

	A	B	C	d	e	f
a	∞
b		∞
C			∞
D				∞
E					∞
F						∞

⇒

ɣ=0+0=0 – нижня границя множини маршрутів

Отже, найбільший ступінь елемента і подальше розбиття будемо проводити по дузі (f,d).

	A	B	C	E	f
A	∞
B		∞
C			∞
D					∞
E				∞

Отже, найбільший ступінь елемента і подальше розбиття будемо проводити по дузі (e,b).

	a	C	e	f
A	∞
B			∞
C		∞
D				∞

Отже, найбільший ступінь елемента і подальше розбиття будемо проводити по дузі (c,a).

	c	e	F
A	∞
B		∞
D			∞

Отже, найбільший ступінь елемента і подальше розбиття будемо проводити по дузі (a,f).

	c	E
B		∞
D

Z

Матриця 2𝘹2 дає нам три переходи з вартістю (b,c)=1; (d,c)=6 та (d,e)=4

4 0

8 4

9 5

6+1+6+4=17

(b,c)

(d,c)

(d,e)

10

Завдання 5. За заданою матрицею ваг необхідно:

- побудувати граф;

- знайти найкоротші шляхи від вершини 1 графа до усіх інших вершин цього графа.

Будуємо граф:

Беремо за джерело вершину 1.S={1}

Min{d[2],d[3],d[4],d[5],d[6]}

d[2]= 7

d[3]= 9

d[4]= ∞

d[5]=∞

d[6]=14

Тепер до вершини 1 приєднується вершина 2. S{1,2}

d[3]=min{d[3],d[2]+c[2,3]}={9,7+10}=9,

d[4]=min{d[4],d[2]+c[2,4]}={∞,7+15}=22,

d[5]=min{d[5],d[2]+c[2,5]}={ ∞,7+∞}=∞,

d[6]=min{d[6],d[2]+c[2,6]}={14,7+∞}=14.

Наступна вершина 3. S{1,2,3}

d[4]=min{d[4],d[3]+c[3,4]}={22,9+11}=20,

d[5]=min{d[5],d[3]+c[3,5]}={ ∞,9+∞}=∞,

d[6]=min{d[6],d[3]+c[3,6]}={ ∞,9+2}=11.

Наступною буде вершина 6. S{1,2,3,6}

d[4]=min{d[4],d[6]+c[6,4]}={20,14+∞}=20,

d[5]=min{d[5],d[6]+c[6,5]}={ ∞,14+9}=23.

Тепер до вершин 1,6,3,5 приєднаються спочатку вершина 4 а потім 5.

S{1,2,3,6,4,5}.

Роботу представимо у вигляді наступної таблиці.

Інтерація	S	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
Початок	{1}				∞	∞
	{1,2}					∞
	{1,2,3}					∞
	{1,2,3,6}
	{1,2,3,6,4}
	{1,2,3,6,4,5}

Дата добавления: 2015-09-29