Задачі з теорії графів

Задача 1. Знайти максимальний потік для мережі; причому відсутні c и прорахувати по закону збереження

а) будь-який потік

З	в	потік
X4 5	10	1
6	9	0
6 0	1	6
2 9 0	2	6
0	3	8
1	2	3
X8 X1 2 1 3	2	0
X5 9 1	4	3
6 5 8 3 1	5	1
X0 5 8 6	1	1
X11 X2 6 6	2	6
X9 6 14 3	6	6
1 7 6 12 3	7	2
X6 X10 8 4 4	5	2
X3 6	7	11
2 9 4	8	1
11 5	8	1
2 5	9	1
X7 6	9	0
7	9	3
7	11	2
7	10	8
8	9	1
9	10	2
8	11	1
9	11	6
10	11	11

б) Одержуємо повний потік

• X0, X2, X6, X1, X4, X8, X11 - збільшувати на 1 (X2,X6), (X4,X8)

• X0, X3, X6, X1, X5, X8, X11 - збільшувати на 1 (X1,X5)

• X0, X3, X6, X1, X4, X5, X8, X11 - збільшувати на 1 (X3,X6)

в) максимальний потік : розмітка 1

X0+

X2+0 т.щ. з X0

X1-2 т.щ. з X2

X4+1

X5+4

X8+5

X11+8

Випишемо ланцюг : X0, X2, X1, X4, X5, X8, X11

(X0,X2)=1

(X1,X2)= (X2,X1)=1

(X1,X4)=1

(X4,X5)=5

(X5,X8)=6

(X8,X11)=5

тобто

Зменшимо X1, X2 на 1 та збільшемо на 1 всі інші. Отримаємо (X1,X2)-насичена та (X0,X2)

Повторюємо розмітку

X0+, X3+0, X2+3, X1-2, X6-1

Т.ч. жодну з вершин помітити не можна, то

не позначені :

A={X4,X5,X7,X8,X9,X10,X11}

розріз (X1,X4), (X1,X5), (X2,X9), (X6,X7), (X7,X7)

C(u) = 6+2+3+11+2 = 24

Задачі для самостійної роботи студентів

Задача 1. Граф заданий матрицею суміжності (матрицею досяжності). Визначите, чи є заданий граф деревом. Знайдіть остов графу. Указівка. Граф повинний бути зв'язковим, а кількість його ребер на одиницю більше кількості вершин.

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

З

адача 2. На заданій мережі знайти максимальний потік із X4 в X1 и мінімальний розріз. Контрольні питання

1. Що називається остовом в графі?

2. Який граф є транспортною мережею?

3. Що таке розріз в мережі?

4. Що таке пропускна здатність дуги? Розрізу?