ДОМАШНЄ ЗАВДАННЯ. ЛІТЕРАТУРА. ПРАКТИЧНЕ ЗАНЯТТЯ №7

⇐ ПредыдущаяСтр 7 из 11Следующая ⇒

ДОМАШНЄ ЗАВДАННЯ

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. При цьому можна виїхати лише в одному напрямку. Цю умову можна записати так: