Графи та їх подання на ЕОМ - навчальна робота, реферат, курсова, диплом на!
Перед Вами представлений документ: Графи та їх подання на ЕОМ.
Федеральне агентство з освіти
Федеральна державна загальноосвітня установа
вищої професійної освіти
Чуваський державний університет ім. І.М. Ульянова
Факультет управління та економіки
Кафедра вищої математики та інформаційних технологій
з дисципліни: Дискетна математика для програмістів
на тему:Графи та їх подання на ЕОМ
→1. Визначення графів
1.1 Основне визначення
1.3 Інші визначення
→2. Способи завдання графів
2.1 Зображення графа
2.2 Способи чисельного представлення графів
2.3 Подання орієнтованих граф
→3. Види графів та операції над ними
3.1 Елементи графів
3.2 Ізоморфізм графів
3.3 Тривіальні та повні графи
3.4 Дводольні графи
3.5 Спрямовані орграфи та мережі
3.6 Операції над графами
→4. Подання графів в ЕОМ
4.1 Вимоги до подання графів
4.2 Реалізація алгоритмів пошуку в глибину і ширину в програмному середовищі Turbo Pascal
Список використаної літератури
Серед дисциплін і методів дискретної математики теорія графів і особливо алгоритми на графах знаходять максимально широке застосування в програмуванні. Між поняттям графа і поняттям відносини, є глибокий зв'язок - по суті це рівнооб'ємні поняття. Виникає природне питання, чому тоді графам виявляється настільки явне перевагу? Справа в тому, що теорія графів надає зручнумовудля описупрограмних (та й багатьох інших) моделей. Цю тезу можна пояснити наступною аналогією. Поняття відносини також можна повністю висловити через поняття множини. Проте незалежне визначення поняття відносинизручніше- введення спеціальних термінів і позначень спрощує виклад теорії і робить її більш зрозумілою. Те саме стосується і теорії графів. Системна система спеціальних термінів і позначень теорії графів дозволяють просто і доступно описувати складні і тонкі речі. Особливо важливо наявність наочної графічної інтерпретації поняття графа. Самоназва «граф» має на увазі наявність графічної інтерпретації. Картинки дозволяють відразу «подивитися» суть справи на інтуїтивному рівні, доповнюючи та прикрашаючи стомлюючі раціональні текстові докази та складні формули.
Графи є максимально абстрактною структурою, з якою доводиться стикатися в теорії ЕОМ (computerscience). Графи використовуються для опису алгоритмів автоматичного проектування, в діаграмах машини кінцевих станів, при вирішенні завдань маршрутизації потоків і т.д. Будь-яка система, що передбачає наявність дискетних станів чи наявність вузлів і переходів з-поміж них може бути описана графом.
Наприклад,ЗавданняпроКенігсберзькихмістах.Обійти всі чотири частини суші, пройшовши по кожному мосту один раз, і повернутися у вихідну точку завдання було вирішено Ейлером в 1736 році.Завданняпротрехбудинкахітрехкриницях.Є три будинки та три колодязі. Провести від кожного будинку до кожного колодязя пинку так, щоб фішки не перетиналися. Це завдання було вирішено Куратовським у 1930 році.Завданняпрочотирьохфарбах.Будь-яку карту на площині розфарбуватичотирма фарбами так, щоб жодні дві сусідні області не були зафарбовані одним кольором.
ГрафомG(V,Е)називається сукупність двох множин - непустої множиниV(множинивершин)і множиниЕнеупорядкованих пар різних елементів множиниV(Е- безлічребер).
G (V, E) = V, E, V, E VV, E = E -
Сполуки між вузлами графа називаються ребрами. Якщо вузли графа не нумеровані, то ребра неориентированными. У графа з нумерованими вузлами ребра орієнтовані. Ребрам можуть бути присвоєні певні ваги або мітки. На рис. 1.1А та 1.1Б наведено приклади звичайного та орієнтованого графа.
Число вершин графаAпозначимор,а число ребер -q:
p : = p ( A ) : = V , q : = = q ( A ) : = E ;
Простіше визначення графа - сукупність точок і ліній, у якій кожна лінія з'єднує дві точки. Для орієнтованого графа E? Vx – кінцевий набір орієнтованих ребер. Ребром може бути пряма чи крива лінія. Ребра що неспроможні мати загальних точок крім вершин (вузлів) графа. Замкнена крива в E може мати тільки одну точку з множини V, а кожна незамкнута крива в E має рівно дві точки множини V. Якщо V і E кінцеві множини, то і граф їм відповідний називаєтьсякінцевим. Граф називаєтьсявиродженим, за умови, що він не має ребер.Паралельнимиребрами графа називаються такі, які мають спільні вузли початку та кінця.
Якщо ребро з'єднають дві вершини, то кажуть, що воно їм інцидентне; вершини, з'єднані ребром, називаються суміжними. Дві вершини, з'єднані ребром, можуть збігатися; таке ребро називається петлею. Число ребер, інцидентних вершині, називається ступенемвершини. Якщо ступінь вершини дорівнює 0, виходить ізольована графа. Якщо два ребра інцидентні однієї й тієї ж вершин, вони називаються кратними; граф, що містить кратні ребра, називається мультиграф.
Зауваження.Якщо не обумовлено неприємне, то мається на увазі Г + і позначається просто Р.
ЯкщоАV- безліч вершин, тоГ(А)- безліч усіх вершин, суміжних з вершинами зА:
Г (А): = u V v A u Г (v);
Часто розглядаються такі споріднені графи об'єкти.
Якщо елементами множиниЕєупорядкованіпари, то граф називаєтьсяорієнтованим(абоорграфом).У цьому випадку є множиниVназиваютьсявузлами,а множини множиниЕ--дугами.
Якщо елементом множиниЕможе бути параоднакових(не різних)елементівV,то такий елемент множиниЕназиваєтьсяпетлею,а граф називаєтьсяграфомзпетлями(абопсевдографом).
ЯкщоЕє не безліччю, анабором,що містить кілька однакових елементів, то ці елементи називаютьсякратнимиребрами,а граф називаєтьсямул'тиграфом.
Якщо елементами множиниЕє не обов'язково двоелементні, абудь-якіпідмножини множиниV,то такі елементи множиниЕназиваютьсягіпердугами,а граф називаєтьсягіперграфом.
Якщо задана функціяЕ:VМта/абоF:ЕМ,то безлічМназивається безліччюпоміток,а граф називаєтьсяпоміченим(абонавантаженим).В якості безлічі поміток зазвичайвикористовуються букви чи цілі числа.
Графи відображаються на площині набором точок і ліній або векторів, що з'єднують їх. При цьому грані можуть відображатися і кривими лініями, а їх довжина не відіграє жодної ролі.
Граф G називаєтьсяплоским, якщо його можна відобразити в площині без перетину його граней. Обрисом графа вважається будь-яка топологічно пов'язана область, обмежена ребрами графа.
Неорієнтований граф G = називаєтьсяпов'язаним, якщо для будь-яких двох вузлів x,y ПРО V існує послідовність ребер з набору E, що з'єднує x і y. Граф G пов'язаний тоді й тільки тоді, коли безліч його вершин не можна розбити на 2 непусті підмножини V1 і V2 так, щоб обидві граничні точки кожного ребра знаходилися в тому самому підмножині. Граф G називаєтьсяk-зв'язковим(k і 1), якщо не існує набору з k-1 або меншої кількості вузлів V`Н V, такого, що видалення всіх вузлів V` і пов'язаних з ними ребер, зроблять граф G незв'язаним.
ТеоремаМенгера: граф G є k-пов'язаним тоді і тільки тоді, коли будь-які 2 різні вузли x і y графа G з'єднані по вкрай ме k шляхами, що не містять загальних вузлів. k-пов'язані графи представляють особливий інтерес для мережевих додатків. Певну проблему становить автоматичне відображення графа на екрані чи папері. Крім того, для багатьох програм (наприклад, CAD) всі вузли графа повинні збігатися з вузлами технологічної сітки. Виникають інші обмеження, наприклад необхідність розміщення всіх вузлів на прямій лінії. У цьому випадку ребра графа можуть являти собою криві лінії, дуги або ламані лінії, що складаються з відхилень прямих.
2.2 Способи чисельного представлення графа
→1. Матричний спосіб (за допомогоюматриці суміжності). Матриця суміжності має m - сторік і n - стовпців, де m - кількість вершин графа.
Елементами матриці суміжності є 0 і 1 Якщо вершини з'єднані, то ставиться 1 і навпаки.