Домашнє завдання

1. Правильно розфарбувати грані заданого графа чотирма кольорами.

2. Робота з індивідуальним завданням. Література

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С.112-127.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.84-100.

3. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С.180-190.

4. Федосеева л.И. Дискретная математика: Учеб.-практич. Пособие. – Пенза: Изд-во Пенз. Технол. Ин-та, 1998. – с.37-43. Дискретна математика” практичне заняття №7

Тема. “ГАМІЛЬТОНОВІ ТА ЕЙЛЕРОВІ ГРАФИ. ЗАДАЧА КОМІВОЯЖЕРА”.

ПЛАН

1. Ейлерові ланцюги і шляхи.

2. Ейлерові цикли і контури.

3. Гамільтонові ланцюги і шляхи.

4. Гамільтонові цикли і контури.

5. Задача комівояжера.

Завдання 1. Побудувати у заданому графі ейлеровий шлях. Чи існує у цьому графі ейлеровий контур?

Завдання 2. Довести, що заданий граф є ейлеровим. Застосувавши алгоритм побудови ейлерового циклу, побудувати такий цикл.

Завдання 3. Побудувати у заданому графі гамільтоновий ланцюг. Чи існує у цьому графі гамільтоновий контур?

Завдання 4. Розв’язати задачу комівояжера для випадку, коли торговець повинен об’їхати 5 міст? Причому з будь-якого з них можна проїхзати до іншого. Введмо поначення:

• і та j – номери пунктів виїзду та в’їзду;

• – час для перїзду з пункту і в пункт j , причому .

Дано матрицю ваг 55, що вказує тривалість переїзду з одного пункту до іншого.

Введемо булеві змінні:

Модель буде описана повним графом на 5-ти вершинах.

З п.1 можна поїхати в будь-який з п.2, п.3, п.4 чи п.5, або залишитися в п.1. При цьому можна виїхати лише в одному напрямку. Цю умову можна записати так:

, або .

Д ля довільного пункта .

Аналогічно можна описати умову виїзду:

, або .

Для довільного пункта .

Умову мінімізації тривалості маршруту запишемо у вигляді цільової функції:

,

де беруть з матриці ваг, а – шукані змінні.

Тоді всю задачу можна сформулювати:

В результаті виконання цієї системи, отримаємо такі значення:

, інші .

Отже, .

Домашнє завдання

1. Побудувати ейлеровий ланцюг, що складається з чотирьох ребер через задані 9 точок так, щоб цей ланцюг пройшов через всі 9 точок.

2. Робота з індивідуальним завданням. Література

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С.61-75.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.168-179.

3. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С.50-60.

4. Федосеева л.И. Дискретная математика: Учеб.-практич. Пособие. – Пенза: Изд-во Пенз. Технол. Ин-та, 1998. – с.170-182. Дискретна математика” практичне заняття №8

Тема. “ПОШУК МІНІМАЛЬНИХ ШЛЯХІВ НА ГРАФАХ”.

ПЛАН

1. Пошук шляху з мінімальною кількістю дуг.

2. Пошук шляху мінімальної довжини. Алгоритм Дейкстри.

Завдання 1. Використовуючи алгоритм пошуку шляху з мінімальною кількістю дуг, знайти такий шлях з вершини А до вершини В.

Завдання 3. Використовуючи алгоритм Дейкстри, визначити найкоротші шляхи з вершини А до всіх інших вершин заданого графа.

Щоб прослідкувати дію алгоритму покроково, заповнимо такі таблиці:

• міток LABEL (у цій таблиці відмічати вершини з незмінною міткою, обвівши мітку в квадрат. Мітки останніх вершин, помічених незмінною міткою (тобто ) відмічати *);

• міток PRED;

• найкоротших шляхів

за вказаними шаблонами.

Таблиця міток LABLE

Крок і	Вершини
	A	B	C	D	E	F	G	H
0	0*							
1	0	7		8			1*	
2	0	7		6*			1	
3	0	7*		6	14		1	19
4	0	7		6	14*		1	19
5	0	7		6	14*		1	19*
6	0	7		6	14	23*	1	19
7	0	7	*	6	14	23	1	19

Таблиця міток PRED

PRED (A)	A
PRED (B)	A
PRED (C)	C
PRED (D)	G
PRED (E)	D
PRED (F)	H
PRED (G)	A
PRED (H)	D

Таблиця найкоротших шляхів

Від

До

Найкоротший шлях

A	B	A,B
A	C	Немає шляху
A	D	A,G,D
A	E	A,G,D,E
A	F	A,G,D,H,F
A	G	A,G
A	H	A,G,D,H