Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом. Точки називаються його вершинами (вузлами), а лінії – ребрами (вітками). Лінія на графі, яка не проходить вздовж жодного його ребра більш ніж один раз, називається ланцюгом. Якщо, рухаючись від однієї вершини, пройти по кількох вершинах графа так, щоб на кожному ребрі побувати лише один раз, а потім знову повернутись у цю ж вершину, такий шлях називається циклом. Т. т. будь- який замкнений ланцюг – цикл. Графи бувають неорієнтованими та орієнтованими, т.т. з напрямленими ребрами. Якщо кожному ребру приписати деяке число(вагу), то граф називається зваженим. Граф називається звязним, якщо будь-які дві його вершини звязані ланцюгом. B E D F А C

Представлення графів Матриця суміжності – це двовимірний масив розмірності N*N, де кожен елемент визначається співвідношенням A[i,j]= Для збереження ребер необхідний двовимірний масив розмірності M*2. Рядок такого масиву описує ребро. Для наведеного вище графу це буде

Алгоритм пошуку в глибину (т. т. обходу всіх вершин графу) Спочатку помітимо усі вершини графу як нерозглянуті (т.т. заповнимо масив міток значенням true). Пошук почнемо з будь-якої вершини v, наприклад з першої - значення мітки міняємо на протилежне (false - вершина розглянута). Опрацьовуємо дану вершину (наприклад, виводимо її номер) Для кожної вершини, яка суміжна з v і раніше не розглядалась, рекурсивно застосовуємо пошук в глибину. Будемо рахувати, що граф заданий матрицею суміжності, а для міток вершин використовується булевий масив

Текст програми var a:array[1..100,1..100] of integer; cnt,n,i,j,k:integer; vert: array[1..100] of boolean; {процедура заповнення матриці суміжності з файлу} procedure inpt; var f:text; i,j:integer; begin assign(f,'in.dat'); reset(f); readln(f,n); for i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end;

{рекурсивна процедура пошуку в глибину} procedure seach_g(v:byte); var i:byte; Begin {опрацювання вершини} writeln(пройдено вершину ',v); vert[v]:=false; {вершина відвідана} for i:=1 to n do if (a[v,i]<>0) and vert[i] then begin {опрацювання вершини} seach_g(i); end;

{основна програма} Begin {заповнення матриці суміжності} inpt; {присвоєння міток усім вершинам} fillchar(vert,n,true); {лічильник компонент звязності} cnt:=0; {виклик процедури пошуку в глибину для чергової нерозглянутої вершини} for i:=1 to n do if vert[i] then begin {нарощування кількості компонент звязності} inc(cnt); seach_g(i) end; writeln(cnt); end.

Редагування файлу файлу 1 Виклик процедури пошуку

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

Текст програми const n=10; const n=10; type mnog=set of ; type mnog=set of ; var a:array[1..n,1..n] of integer; var a:array[1..n,1..n] of integer; i,k:integer; i,k:integer; vergr:mnog; vergr:mnog; procedure svyaz(nr:integer;var versh:mnog); procedure svyaz(nr:integer;var versh:mnog); var j:integer; var j:integer; begin begin for j:=1 to n do for j:=1 to n do if a[nr,j]<>0 then if a[nr,j]<>0 then if not(j in versh) then if not(j in versh) then begin begin versh:=versh+[j]; versh:=versh+[j]; svyaz(j,versh); svyaz(j,versh); end; end; if nr=n then exit; if nr=n then exit; end; end; begin begin for i:=1 to n do for i:=1 to n do for k:=1 to n do for k:=1 to n do read(a[i,k]); read(a[i,k]); k:=1; k:=1; vergr:=[1]; vergr:=[1]; svyaz(k,vergr); svyaz(k,vergr); k:=0; k:=0; for i:=1 to n do for i:=1 to n do if i in vergr then begin writeln('=',i); k:=k+1; end; if i in vergr then begin writeln('=',i); k:=k+1; end; if k=n then writeln(svyaznij) else writeln(ne svyaznij); if k=n then writeln(svyaznij) else writeln(ne svyaznij); end. end.

Граф називається повним, якщо будь-які дві його вершини сполучені ребром. Повний граф має n вершин, то він матиме ребер. Граф без циклів – дерево. Остовне дерево(каркас) – дерево, в якому n вершин та n-1 ребер Мінімальний каркас : сума ваг усіх ребер, які входять до нього – мінімальна

Алгоритм побудови мінімального каркасу ( Алгоритм Краскала ) 1. к=0 2.поки к<= виконувати –пошук максимуму в матриці ваг –побудова матриці звязності, що відповідає графу з викинутим максимальним ребром –якщо граф звязний, то обнуляємо відповідний елемент в обох матрицях, збільшуємо к на 1 і переходимо до п.2, інакше в матриці ваг робимо відємним значення максимуму і йдемо на п.2 3.знаходимо суму модулів елементів матриці ваг над головною діагоналлю(це і буде мінімальний каркас)

Приклад Видалення ребра 5-3 (18) Видалення ребра 1-4 (16)

Видалення ребра 5-2 (13) Видалення ребра 5-4 (10)

Ребро 5-1 (9) видалити неможливо, тому видаляємо наступне ребро 1-2 (8) Видаляємо ребро 2-4 (7) Отримуємо мінімальний каркас, його вартість =17

Фрагменти програми procedure buld;{побудова матриці суміжності по матриці ваг} var i,j:integer; begin for i:=1 to n do for j:=1 to n do if a[i,j]<>0 then matr_svz[i,j]:=1 else matr_svz[i,j]:=0; end; begin inpt; buld; rebr:=n*(n-1) div 2; while rebr>n-1 do begin imax:=1; jmax:=1; for i:=1 to n do for j:=1 to n do if a[i,j]>a[imax,jmax] then begin imax:=i;jmax:=j; end;

matr_svz[imax,jmax]:=0; matr_svz[jmax,imax]:=0; {--perevirka na zvjazok---} {--perevirka na zvjazok---} k:=1; k:=1; vergr:=[1]; flag:=0; vergr:=[1]; flag:=0; svyaz(k,vergr); svyaz(k,vergr); l:=0; l:=0; for i:=1 to n do for i:=1 to n do if i in vergr then l:=l+1; if l=n then begin if l=n then begin a[imax,jmax]:=0; a[jmax,imax]:=0; rebr:=rebr-1; end a[imax,jmax]:=0; a[jmax,imax]:=0; rebr:=rebr-1; end else begin else begin a[imax,jmax]:=-a[imax,jmax]; a[imax,jmax]:=-a[imax,jmax]; a[jmax,imax]:=-a[jmax,imax]; a[jmax,imax]:=-a[jmax,imax]; matr_svz[imax,jmax]:=1; matr_svz[jmax,imax]:=1; matr_svz[imax,jmax]:=1; matr_svz[jmax,imax]:=1; end; end; s:=0; s:=0; for i:=1 to n do for i:=1 to n do for j:=i+1 to n do for j:=i+1 to n do s:=s+abs(a[i,j]); s:=s+abs(a[i,j]); writeln('ostov=',s); writeln('ostov=',s);end.

Перевірка програми Перевірка програми In.dat OSTOV_KR.EXE

Алгоритм пошуку в ширину (т. т. обходу всіх вершин графу) Алгоритм знаходження мінімального по кількості вершин шляху. Між деякими містами існує авіасполучення. Потрібно знайти мінімальний по кількості пересадок шлях з міста А в місто В (т.т. вказати перелік міст, в яких необхідно здійснити пересадку). Використаємо такі структури даних : масив А[1..N], в який ми будемо записувати номери вершин, що доступні на даний момент з активної вершини, масив B[1..N], i -тим елементом якого буде номер вершини, з якої ми попали в вершину А[i], масив C[1..N], i -тим елементом якого буде true – якщо вершина А[i] уже розглядалась і false – якщо не розглядалась.

Алгоритм Ініціалізація : вибираємо активною вершину, звязану з містом А (наприклад, і). Записуємо в А[1] значення і, в В[1] – 0, в С[1] – true. З і –го рядка матриці суміжності переносимо номери вершин, з якими звязана і- та вершина поступово у масив А. У відповідні елементи масиву В записуємо значення і, а у С – ставимо true в ті комірки, номер яких співпадає з номером суміжної з і вершини, яку ми розглянули. Повторюємо цей крок алгоритму для вершини, номер якої записаний в А[2] і т. д.

Для даного прикладу першим кроком алгоритму масиви заповняться так А10000 В00000 С truefalse А12450 В01110 С true falsetrue А12453 В01115 С Редагування файлу IN.DAT Програма POSH_SHI.EXE

Тепер знайдемо шлях. Його шукаємо методом зворотної розкрути, т.т. ідемо від кінцевої вершини (шукаємо її номер в А), дивимось на відповідний елемент в В (це і буде номер вершини, з якої ми попали в дану). Тепер знову шукаємо вже цю вершину в А і, аналогічно, відповідний їй елемент В – частина маршруту, і т.д., доки не зустрінемо вершину, з якої ми мали відправитись – це і буде шуканий маршрут, тільки у зворотному порядку. Тепер знайдемо шлях. Його шукаємо методом зворотної розкрути, т.т. ідемо від кінцевої вершини (шукаємо її номер в А), дивимось на відповідний елемент в В (це і буде номер вершини, з якої ми попали в дану). Тепер знову шукаємо вже цю вершину в А і, аналогічно, відповідний їй елемент В – частина маршруту, і т.д., доки не зустрінемо вершину, з якої ми мали відправитись – це і буде шуканий маршрут, тільки у зворотному порядку. Для даного прикладу шлях з вершини 1 в 3 буде 1- 5 – 3. Для даного прикладу шлях з вершини 1 в 3 буде 1- 5 – 3.

var matr_svz:array[1..100,1..100] of integer; a,b:array[1..100]of integer; c:array[1..100] of boolean; z,n,l,k,i,j,vp,vk:integer; sum:boolean; s:string; procedure inpt; var f:text; i,j:integer; begin assign(f,'in.dat'); reset(f); readln(f,n); readln(f,vp,vk); for i:=1 to n do for k:=1 to n do read(f,matr_svz[i,k]); close(f); end; procedure rozkr(w:integer); var i:integer; t:string; begin if w=vp then exit; for i:=1 to n do if a[i]=w then break; str(b[i],t); s:=' '+t+s; writeln(b[i]); rozkr(b[i]); end; begin inpt; for i:=1 to n do begin for k:=1 to n do write(matr_svz[i,k],' '); writeln; end; i:=1; a[i]:=vp; b[vp]:=0; c[vp]:=true; k:=i+1; repeat l:=k; for j:=1 to n do if (matr_svz[a[i],j]<>0)and(not(c[j])) then begin a[k]:=j; b[k]:=a[i]; c[a[k]]:=true; k:=k+1; end; i:=i+1; sum:=true; for j:=1 to n do sum:=sum and c[j]; i:=i+1; until sum; writeln('======='); for j:=1 to n do write(a[j],' '); writeln('*********'); str(vk,s); s:=' '+s;rozkr(vk); writeln(s); end.

Алгоритм хвильки (вихід з лабіринту) 1. В стартову клітинку записуємо k (початкове значення 2) 2. Поки не досягнуто фінішної клітинки( або повторювати стільки раз, скільки в матриці є нульових елементів) в сусідні не рівні 1 клітинки записати значення к+1 3. Збільшити значення к на 1, перейти на п

Цікаві сайти та книги Uoi.kiev.ua Uoi.kiev.ua Olymp.vinnica.ua Olymp.vinnica.ua Ф. Меньшиков. Олимпиадные задачи по программированию.: Питер, 2006 Ф. Меньшиков. Олимпиадные задачи по программированию.: Питер, 2006 Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, Липский В. Комбинаторика для программистов. М.: Мир, Липский В. Комбинаторика для программистов. М.: Мир, Вирт Н. Алгоритмы и структуры данных. СПб: Невский диалект, Вирт Н. Алгоритмы и структуры данных. СПб: Невский диалект, Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000 Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000 Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: Невский диалект, 2001 Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: Невский диалект, 2001 Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978 Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978 Мої координати : д. т