asyan.org
добавить свой файл
1

ВОЛИНСЬКИЙ ІНСТИТУТ ПІСЛЯДИПЛОМНОЇ ПЕДАГОГІЧНОЇ ОСВІТИ

“Школа олімпійського резерву”

27.02.2009




Тема заняття: Основні поняття теорії графів.

План заняття


  1. Аналіз методів і задач повного перебору.


Методи перебору:

  • деревом

  • лексичний

  • з поверненням



Задачі на використання перебору:

  • греко-латинський квадрат (знайти квадрати від 5..10)

  • конференція (протестувати на тестах diplom0.dat … diplom9.dat)

  • деталі (протестувати на тестах details1.dat … details5.dat, звернути увагу на зчитування даних)


  1. ГРАФИ

Два з половиною століття тому в жителів тихого Кенігсберга (нині Калінінград) пропав спокій. Всі вони захопились розв'язан­­­ням задачі - як обійти сім мостів, перекинутих через річку Пре­­гель на острів Кнейпхоф, побувавши на кожному з них один і тільки один раз.




Цією задачею зацікавився Л.Ейлер. Вчений у цій задачі побачив важливу математичну проблему і знайшов загальний метод розв'язування подібних задач.

Введемо деякі основні поняття, що стосуються теорії графів.

1. Граф представляє собою не порожню множину точок і ліній, два кінці котрих належать заданій множині точок.



2. Точки 1,2,3,4,5,6 - вершини графа.

3. Відрізки 12,24,45,51,13,34,23,35 – ребра графа.

4. Вершина 6 не належить ребру і називається ізольованою (але вона частина графа).

5. Кількість ребер, які виходять з даної вершини визначають степінь вершини графа. Вершини відрізняються кількістю ребер, котрим вона належить (степінь вершини – число ребер)
^

Вершина 6 має 0 степінь, а 1 – 3 степінь.




Послідовність А1,А2,А3,А4,А5,А6 – Шлях з А1 в А6

Фігури, які складаються з ряду точок, з'єднаних між собою лініями, називаються графами. Точки є вершинами графа, а лінії –­­­ ребра графа.

Відкриті Ейлером властивості графа:

1. Число непарних вершин зв'язного графа завжди парне. Неможливо накреслити граф з непарним числом непарних вершин.

2. Якщо всі вершини графа парні, то можна одним розчерком (тобто не відриваючи олівця від паперу) накреслити граф, не проводячи по кожному ребру більше одного разу. При цьому можна починати з будь-якої вершини графа і закінчувати його в тій же вершині.

3. Граф лише з двома непарними вершинами можна накреслити одним розчерком, при цьому рух потрібно почати в одній точці з цих вершин і закінчити в другій непарній вершині.


4. Граф з більше ніж двома непарними вершинами неможливо накреслити одним розчерком.

Оскільки число непарних вершин графа в задачі про кенігсбергські мости рівне 4, то такий граф неможливо зобразити одним розчерком, неможливо пройти по всіх мостах по одному разу.
Ейлеровим графом (шляхом або циклом) називається граф, що має по одному всі ребра графа. Замкнута лінія, яку можна накреслити одним розчерком, називається універсальною.

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

^ Зв’язний граф – граф, в якого кожні дві вершини є зв’язаними між собою ребрами.


зв’яний незв’язний

Неорієнтований граф:


Орієнтований граф:


Орієнтований, навантажений граф:



Гамільтонів шлях проходить через кожну вершину по одному разу (по ребрах проходить декілька разів або жодного)

Елілеровий шлях – це шлях, який ми проходимо з однієї вершини в іншу через всі ребра тільки один раз.


Практичне завдання
1. Написати матрицю суміжності:


2. Написати фрагмент зчитування графа і заповнення матриці суміжності.
За заданими кількістю верши графа n і зв’язками між і-вершиною та j-вершиною, зв’зком k заповнити матрицю суміжності для: а) навантаженого, неорієнтованого графа; б) навантаженого, орієнтованого графа.
^ Домашнє завдання

1. Задача про зайця. У невеличкій посадці живе заєць. Вискочив­­­ши з нори і бігаючи по снігу, він залишив сліди. Де знаходиться заєць і де знаходиться його нора? З'єднайте точки: B з C, D, K, M, A; C з D, K, L; D з L, R; K з L, Q, N, M; M з N, A; A з P, N; N з P; Q з P, R, L; L з R; R з P.


2. Є N поселень. Деякі поселення попарно з'єднані стежками. За ними ніякі дві стежки загальних точок не мають. В цілочисельній таблиці СТЕЖКИ [1..N,1..N] задана інформація про стежки; кількість стежок між і-m і j-m рівна значенню елемента таблиці СТЕЖКИ [і,j]=СТЕЖКИ[j,і]>0 (в тому числі і=j); Написати алгоритм, який визначає, чи можливо зобразити карту стежок, не відриваючи олівця від паперу і не малюючи жодної стежки двічі.