|
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Розрахунково-графічна робота
з курсу «Інформатика інфокомунікаційних систем»
на тему: «Рішення задач на графах»
Варіант 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 |
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 |
4 0
8 4
9 5
(b,c) (d,c) (d,e) |
Завдання 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; просмотров: 14 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
· Находится в красивейшей бухте, окруженной горами Шапсуго и знаменитой горой Ежик, на побережье Черного моря в курортном поселке Джубга Туапсинского района. | | | Russia’s with- drawal from the region, symbolized by the 1989 pullout from Afghanistan, has been reversed. Moscow has re-established political ties with its former allies, such as Syria; engages in |