Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом


НазваОсновні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом
Дата конвертації25.04.2013
Розмір445 b.
ТипПрезентации


Основні поняття теорії графів

  • Сукупність точок та ліній, зображена на малюнку і є графом.

  • Точки називаються його вершинами (вузлами), а лінії – ребрами (вітками).

  • Лінія на графі, яка не проходить вздовж жодного його ребра більш ніж один раз, називається ланцюгом.

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

  • Графи бувають неорієнтованими та орієнтованими, т.т. з напрямленими ребрами. Якщо кожному ребру приписати деяке число(вагу), то граф називається зваженим.

  • Граф називається зв’язним, якщо будь-які дві його вершини зв’язані ланцюгом.


Представлення графів

  • Матриця суміжності – це двовимірний масив розмірності N*N, де кожен елемент визначається співвідношенням

  • A[i,j]=



Алгоритм пошуку в глибину (т. т. обходу всіх вершин графу)

  • Спочатку помітимо усі вершини графу як нерозглянуті (т.т. заповнимо масив міток значенням true).

  • Пошук почнемо з будь-якої вершини v, наприклад з першої - значення мітки міняємо на протилежне (false - вершина розглянута) .

  • Опрацьовуємо дану вершину (наприклад, виводимо її номер)

  • Для кожної вершини, яка суміжна з v і раніше не розглядалась, рекурсивно застосовуємо пошук в глибину.









Редагування файлу



Алгоритм перевірки графу на зв’язність (застосування пошуку в глибину)

  • В множину заносимо першу вершину

  • Рекурсивно для кожної вершини, яка зв'язана з нею, викликаємо процедуру, яка добавляє до множини ті вершини, з якими вона суміжна

  • Перевіряємо множину. Якщо вона містить N елементів, значить граф зв'язний, інакше – ні.



Текст програми

  • const n=10;

  • type mnog=set of 1..100;

  • var a:array[1..n,1..n] of integer;

  • i,k:integer;

  • vergr:mnog;

  • procedure svyaz(nr:integer;var versh:mnog);

  • var j:integer;

  • begin

  • for j:=1 to n do

  • if a[nr,j]<>0 then

  • if not(j in versh) then

  • begin

  • versh:=versh+[j];

  • svyaz(j,versh);

  • end;

  • if nr=n then exit;

  • end;

  • begin

  • for i:=1 to n do

  • for k:=1 to n do

  • read(a[i,k]);

  • k:=1;

  • vergr:=[1];

  • svyaz(k,vergr);

  • k:=0;

  • for i:=1 to n do

  • if i in vergr then begin writeln('=',i); k:=k+1; end;

  • if k=n then writeln(‘svyaznij’) else writeln(‘ne svyaznij’);

  • end.



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



Алгоритм побудови мінімального каркасу (Алгоритм Краскала)

  • 1. к=0

  • 2. поки к<= виконувати

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



Приклад







Фрагменти програми

  • 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;



matr_svz[imax,jmax]:=0; matr_svz[jmax,imax]:=0;

  • matr_svz[imax,jmax]:=0; matr_svz[jmax,imax]:=0;

  • {--perevirka na zvjazok---}

  • k:=1;

  • vergr:=[1]; flag:=0;

  • svyaz(k,vergr);

  • l:=0;

  • for i:=1 to n do

  • if i in vergr then l:=l+1;

  • if l=n then begin

  • a[imax,jmax]:=0; a[jmax,imax]:=0; rebr:=rebr-1; end

  • else begin

  • a[imax,jmax]:=-a[imax,jmax];

  • a[jmax,imax]:=-a[jmax,imax];

  • matr_svz[imax,jmax]:=1; matr_svz[jmax,imax]:=1;

  • end;

  • end;

  • s:=0;

  • for i:=1 to n do

  • for j:=i+1 to n do

  • s:=s+abs(a[i,j]);

  • writeln('ostov=',s);

  • end.



Перевірка програми





Алгоритм

  • Алгоритм

  • Ініціалізація : вибираємо активною вершину, зв’язану з містом А (наприклад, і). Записуємо в А[1] значення і, в В[1] – 0, в С[1] – true.

  • З і –го рядка матриці суміжності переносимо номери вершин, з якими зв’язана і- та вершина поступово у масив А.

  • У відповідні елементи масиву В записуємо значення і, а у С – ставимо true в ті комірки, номер яких співпадає з номером суміжної з і вершини, яку ми розглянули.

  • Повторюємо цей крок алгоритму для вершини, номер якої записаний в А[2] і т. д.



Для даного прикладу першим кроком алгоритму масиви заповняться так

  • Для даного прикладу першим кроком алгоритму масиви заповняться так



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

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

  • Для даного прикладу шлях з вершини 1 в 3 буде 1- 5 – 3.





Алгоритм “хвильки” (вихід з лабіринту)

  • Алгоритм “хвильки” (вихід з лабіринту)

  • В стартову клітинку записуємо k (початкове значення 2)

  • Поки не досягнуто фінішної клітинки( або повторювати стільки раз, скільки в матриці є нульових елементів) в сусідні не рівні 1 клітинки записати значення к+1

  • Збільшити значення к на 1, перейти на п. 2





Цікаві сайти та книги

  • Uoi.kiev.ua

  • Olymp.vinnica.ua

  • Ф. Меньшиков . Олимпиадные задачи по программированию.: Питер, 2006

  • Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.

  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.

  • Липский В. Комбинаторика для программистов. М.: Мир, 1988.

  • Вирт Н. Алгоритмы и структуры данных. СПб: Невский диалект, 2001.

  • Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000

  • Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001

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

  • Мої координати : 2jak@ua.fm, д. т. 58-03-08



Схожі:

Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconТема 2: «Основи теорії графів»
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconТема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Теорія графів — розділ математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне...
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconТема № математичні основи теорії алгоритмів. 4 Елементи теорії графів
Широко використовується теорія графів при рішенні різних задач на обчислювальних машинах. Вірогідно і те, що теорія графів служить...
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconОснови теорії ймовірності та математичної статистики План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconОснови теорії ймовірності та математичної статистики проф. В. П. Марценюк План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconЛекція основи теорії держави І права основні теорії походження держави І права. Поняття й ознаки держави. Внутрішні І зовнішні функції держави
Класифікація держав за їхньою формою (форми правління, форми державного устрою та форми державно-правового режиму)
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconОсновні функції економічної теорії: Основні функції економічної теорії
Дави́д Ріка́рдо (18 квітня 1772, Лондон †11 вересня 1823), англійський економіст, класик політичної економії, послідовник і одночасно...
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом icon«Алгебра. 9 клас» Ю.І. Мальованого, Г. М. Литвиненко, Г. М. Возняк Готуємося до уроку
Більшість понять теорії імовірностей описують за допомогою строгих означень, але є ряд основних, неозначуваних понять, як, наприклад,...
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconПлан Поняття про фармакогнозію. Історична довідка Основні поняття і терміни фармакогнозії
Фармакогнозія. Основні поняття та завдання фармакогнозії. Способи заготівлі, сушіння та зберігання лрс
Основні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом iconТеорія графів – спеціальний розділ математичного програмування, який вивчає кількісні і якісні характеристики графів
Певна вершина може бути з’єднана ребром сама з собою, тоді таке ребро називається

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка