Задание к лабораторной работе

Исходные графы G1: (13, {5, 6})

G2: (7,{3,4})

1. Определить, является ли граф G1 эйлеровым.

Если граф G1 – эйлеров, то:

· построить эйлеров цикл по алгоритму Флёри;

· решить задачу «китайского почтальона», удалив минимальное число ребер, делающих его не эйлеровым (в качестве весов ребер взять 1).

Если G1 не является эйлеровым, то:

· построить эйлеровы цепи в графе G1;

· добавить минимальное число ребер, делающих его эйлеровым и найти эйлеров цикл по алгоритму Флёри;

· решить задачу «китайского почтальона» (в качестве весов ребер взять 1).

2. Определить, является ли граф G2 гамильтоновым.

Если граф – гамильтонов, то:

· построить гамильтонов цикл, используя дерево полного перебора;

· построить гамильтоновы циклы, используя алгоритм Робертса-Флореса;

· решить для него задачу коммивояжера, удалив минимальное число ребер, нарушающих свойство гамильтоновости (в качестве весов ребер взять 1).

Если граф не является гамильтоновым, то:

· решить задачу коммивояжера (в качестве весов ребер взять 1);

· добавить минимальное число ребер, делающих его гамильтоновым; построить гамильтонов цикл, используя дерево полного перебора и алгоритм Робертса-Флореса.

3. Привести примеры гамильтоновых графов, не удовлетворяющих теоремам Оре и Дирака.

Контрольные вопросы

1. Определение эйлерова цикла, графа.

2. Сформулировать критерий существования в графе эйлерового цикла.

3. Какой граф называется гамильтоновым? Дать определение гамильтонова цикла.

4. Сформулировать теоремы Оре, Дирака

5. Что находят задача китайского почтальона, задача коммивояжера?

Литература

1. Лекции по теории графов /под ред. Емеличева Е.А./ – М.: Наука, 1990. – 384с.

2. Кристофидес Н. Теория графов : алгоритмический подход. – М.: Мир, 1978. – 432с.

3. Оре О. Теория графов. М.: Наука, 1980. – 336c.

4. Харари Ф. Теория графов. – М.: Мир, 1973. – 300с.

5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1988. –455с.

Приложение А

Алгоритм генерации варианта

GV ( p,X ) : A[1:p,1:p],где

p - количество вершин в графе;

X - параметр генерации (множество целых);

А - матрица смежности неориентированного графа.

S = <фамилия>< имя>< отчество>

n (c) - функция - номер буквы в алфавите (1..32)

1. Вычеркнуть из S все повторные вхождения букв.

2. Построить Y = || y_{i j} ||, i,j =1..p,