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

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

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

16.09.2005



Заняття 1 (2006)

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

План заняття


  1. Аналіз задачі «Реклама», практичного туру обласної олімпіади з інформатики.

Задача 3. Реклама.

В одному гіпермаркеті вирішили час від часу транслювати рекламу нових товарів. Для того, щоб скласти оптимальний розклад реклами, керівництво гіпермаркету наказало провести дослідження: на протязі дня для кожного покупця, який відвідав гіпермаркет, зафіксувати час, коли він зайшов до гіпермаркету та час, коли він звідти вийшов.

В припущенні, що такий розклад відвідування збережеться і надалі, менеджеру по рекламі було доручено скласти розклад трансляції реклами з дотриманням таких вимог:

  1. кожен відвідувач має почути рекламне оголошення не менше двох разів;

  2. два оголошення не можуть транслюватись одночасно;

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

Необхідно допомогти менеджеру та розробити програму для складення розкладу трансляції рекламних роликів. Рекламні оголошення можна починати транслювати тільки в цілі моменти часу. Рахується, що кожен рекламний ролик завершується до початку наступного цілого моменту часу. Якщо рекламне оголошення транслюється в момент часу, коли покупець входить в гіпермаркет або з нього виходить, то покупець встигає почути це оголошення.

^ Вхідні дані.

Перший рядок вхідного файлу REKLAMA.IN містить число N - кількість відвідувачів за день (1 < N < 3000). Наступні N рядків містять пари натуральних чисел аі, В] , що вказують, відповідно, на момент часу, коли 1-ий покупець зайшов в гіпермаркет та момент часу, коли він вийшов з гіпермаркету (0 < аі < ВІ< 100).

^ Вихідні дані.

Перший рядок вихідного файлу REKLAMA.OUT повинен містити отриману кіль­кість рекламних роликів. Далі - в зростаючому порядку моменти часу, коли потрібно транслювати рекламні оголошення. Якщо є декілька рішень, вказати довільне.
Приклад.

PvEKLAMA.IN

5

1 10

1012

1 10

1 10

2324

REKLAMA.OUT

5

5 10 12 23 24


var a,b,r:array[1..3000] of byte;

j,i,n:integer;

temp:integer;

f1,f2:text;

min,k,kol:integer;

per:boolean;

begin

{§зЁвгў ­­п}

assign(f1,'reklama.in');

reset(f1);

readln(f1,n);

for i:=1 to n do readln(f1,a[i],b[i]);

close(f1);

for i:=1 to n-1 do

for j:=1 to n-1 do

if a[j]>a[j+1] then begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp;
temp:=b[j];

b[j]:=b[j+1];

b[j+1]:=temp;

end;

kol:=0; i:=1; j:=1;

per:=false;

while i<=n do begin

min:=b[i];

while (a[i]
begin

if (b[i]
i:=i+1;

end;
i:=i-1;


if not(per) then

begin

kol:=kol+2;

r[kol-1]:=min-1;

r[kol]:=min;

end

else

begin

kol:=kol+1;

r[kol]:=min;

end;

if (a[i+1]=min){and(min=b[j])} then per:=true else per:=false;

i:=i+1;

j:=i;

end;

{ўЁўҐ¤Ґ­­п}

assign(f2,'reklama.out');

rewrite(f2);

writeln(f2,kol);

for i:=1 to kol do write(f2,r[i],' ');

close(f2);

end.


2. ГРАФИ


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

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

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

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. Задача про зайця. У невеличкій посадці живе заєць. Вискочив­­­ши з нори і бігаючи по снігу, він залишив сліди. Де знаходиться заєць і де знаходиться його нора? З'єднайте точки: 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); Написати алгоритм, який визначає, чи можливо зобразити карту стежок, не відриваючи олівця від паперу і не малюючи жодної стежки двічі.