Реферат Графи

Страница 1 из 2 | Следующая страница

Зміст

Запровадження

1.Графи,орграфи, дерева

2. Операції над графами

3. Збереження графів в ЕОМ

4. Завдання про максимальному потоці

5. Побудова максимального потоку. Прикладиразбираемих завдань

Література


Запровадження

У комерційної діяльності більшість виникаючих завдань зручно цікавити сприйняття й аналізу, у вигляді мереж, що дозволяють вирішити два головні запитання: до якого місця необхідно дійти (мета) і який шлях варто обрати (як).Коммерческую діяльність можна як сукупність завдань, виділені на пересування, складування і розподілу товарів, грошей, документів, інформації про поставки і покупців води, нафти, газу, електроенергії, тілі- і радіосистем.Наглядность і логічна обгрунтованість методів мережного аналізу дозволяє вибрати досить природний підхід вирішення завдань комерційної діяльності. Мережні моделі для таких людей, котрі займаються науковою працею, є як зрозумілими, ніж інші моделі, бо їм набагато краще одного разу побачити, ніж сто раз почути. У значною мірою методи мережного аналізу засновані на теорії графів – математиці, початком розвитку стала завдання прокенигсбергских мости, сформульована швейцарським ученим Л.Эйлером в 1736 р. Через річкуПрегель, де стояв місто Кенігсберг, побудовано сім мостів (рис. 1), які з берегами і один з одним два острова. Завдання полягало у цьому, аби пережити за всі мостам лише одне разів, і повернутися назад до початку маршруту.Эйлер довів нерозв'язність це завдання.

ПізнішеД.К. Максвелл іГ.Р. Кірхгоф з урахуванням дослідження електричних ланцюгів сформулювали деякі принципи мережного аналізу. Розроблено методи розрахунку найбільшої пропускну здатність телефонних ліній. У в 40-ві роки внаслідок розвитку теорії дослідження операцій розробили ряд математичних методів, необхідні аналізу великих систем. У50–60-х роках проводилися роботи з побудові нових мережевих моделей та розробки алгоритмів розв'язання з урахуванням елементів теорії графів.


>Графи,орграфи, дерева

Теорія графів останнім часом широко використовують у різноманітних галузях наук і техніки, особливо у економіки та соціології.

Основи теорії графів розробив Л.Эйлер,решавший завдання про розробку замкнутого маршруту руху по мостам м. Кенігсберзі. За позитивного рішення завдання він позначив кожну частину суходолу точкою, а кожен міст – лінією, їх що з'єднує. У результаті отримано граф (рис. 1).

>Эйлер довів, що завдання рішення немає.

>Эйлер Леонард (1707–1783) швейцарський математик, механік, фізик, астроном. Авторка понад 800 робіт з різним розділах математики інших наук.

Бистре розвиток теорія графів отримала від створенням електронно-обчислювальної техніки, що дозволяла вирішити багато завдань алгоритмізації.

Нехай на площині поставлено деяке безліч вершин X і безліч U що з'єднують їх дуг. >Графом називають бінарну ставлення безлічі X і множин U: G = = (X; U), чи, інакше: X До Тут – відображення >инциденций.

Граф називається орієнтованим, якщо зазначено напрям дуг інеориентированним, коли таке напрям немає. Прикладомнеориентированного графа є карта доріг.

Граф називається петлею, якщо його початок і поклала край збігаються.

Дві вершини називаються суміжними, якщо є з'єднує їх дуга.

>Ребро uj називається >инцидентним вершині xj, коли вона виходить чи входить у вершину.

Ступенем (>валентностью) вершини називається числоинцидентних їй ребер. >Кратностью пари вершин називається число що з'єднують їх ребер чи дуг.

>Подграфом Ga графа G називається граф, куди входить лише деякі з вершин графа G разом із дугами їх з'єднуючими.

Приватним графом Gb графа називається граф, куди входить лише деякі з дуг графа G разом із вершинами їх з'єднуючими. Карта шосейних доріг це граф. Дороги Саратовської області цеподграф, а головні дороги – це приватний граф.

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

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

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

>Ребро – відрізок, котрий поєднує дві вершини, ланцюг – послідовність ребер.

Цикл – кінцева ланцюг, що має початкова й кінцева вершина збігаються.

Граф називається пов'язаним, якщо будь-які його дві вершини можна з'єднати ланцюгом. Граф сильно пов'язаний, для його двох будь-яких вершин xіxj існує шлях, що йде з xі і xj.

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

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

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

На малюнку 3 ребро до – міст, але в малюнку 4 вершина 1 – точка зчленування.

 

 


>Неразделимим називається зв'язний граф, яка має точок зчленування.

Блоком графа називають максимальний нероздільнийподграф.

На малюнку 5 наведено граф G та її блоки А, У, З повагою та D.

 


Дерево це кінцевий, зв'язний, не орієнтований граф, яка має циклів.

>Характеристическое властивість дерев у тому, будь-які дві вершини дерева з'єднані єдиною ланцюгом.

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

Кірхгоф Густав (1824–1887) німецький фізик, механік, математик.

Розвиток теорії графів (дерев) пов'язаний з ім'ям німецького хімікаКели, який успішно застосував її вирішення завдань органічної хімії (вивчення ізомерів вуглеводнів з заданим числом атомів).

Сукупність дерев називається лісом.

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

Найпростіше дерево і двох вершин, з'єднаних руба.

Якщо додати ребро, то додається і вершина. Отже, дерево з п вершинами маєn-1 ребро. Дерево має корінь в вершині Ур якщо є шлях від x1, до кожної з вершин.Ребра графа, належать дереву, називають гілками, інші ребра називаютьхордами.

Граф називаєтьсяпланарним, коли може бути зображений на площині в такий спосіб, що його ребра перетинатимуться лише упланарних вершинах (рис. 6).

Дерево, що єподграфом графа G, називається які покривають їхню граф G, коли вона містить усі його вершини.

Нехай є x1, x2,…, xn вершин і u1, u2…, u>m дуг, які містять. Матрицею суміжності P.S порядку п називається матриця, що складається з чисел P.S., рівних сумі чисел орієнтованих ребер, що йдуть із x в x. (чи чиселнеориентированних ребер, що з'єднують ці вершини). Якщо дуга відсутня, то P.S>r = 0.

Матриця суміжності для орієнтованого інеориентированного графа, власне кажучи, має різний вид. Запишемо матрицю суміжності 5, для орієнтованого графа, зображеного малюнку 7:

 

 

 

 


Матрицею >инциденции Т розміру >m x n називається матриця, що складається з чисел:

>t>ij =

 


Запишемо матрицюинциденции для графа, зображеного малюнку 7:

Операції над графами

Об'єднанням двох, або як графів G1, U G2 U … U Gn називається граф, яка має безліч вершин і безліч дуг об'єднані (рис. 8).

>Рис. 8

 


G1, U G2 >U…U Gn ' = {X1 U X2 U ...; U1, U U2 U ...).

 


Сумою графів G1 і G2 називається граф, визначається як об'єднання графів, причому кожна вершина, не вона до об'єднання, сполучається з іншими вершинами (рис. 9).

Говоритимемо, що вершина іj >конусирует граф G, якщо вона суміжна з усіма вершинами графа.

Твором двох графів називається граф

G1 * G2 = {(Xj1; Xj2)Є G1 * G2}.

Вершина є бінарну ставлення, тобто. вершин ми матимемо 6.

Розглянемо докладно вирішення завдання проКенигсбергских мости. У місті Кенігсберзі є острівКнайпхоф, який охоплено двома рукавами річкиПречель.


За дві рукави перекинуті сім мостів: а,Ь, з, >d, e, >, g. Чи можна спланувати прогулянку в такий спосіб, якби для кожного мосту пройти лише одне разів, і повернутися до початкове положення? Поставимо у відповідність кожному мосту ребро графа, а суші вершину (рис. 11).

>Эйлеровим шляхом в графі G називається цей шлях у якому кожне ребро зустрічається одного разу.Эйлер довів, що така шлях існує тоді й тільки тоді, коли граф G містить трохи більше двох вершиннечетной ступені та є зв'язковими. У цьому завданню існує чотири вершининечетной ступеня (5, 3, 3, 3). Отже, завдання проКенигсбергских мости зовсім позбавленийЭйлеров шлях збереження та немає рішення.

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

Якщо вершиннечетной ступеня немає, то граф має замкнутийейлеров шлях.

На малюнку 12, а немає замкнутогоейлерова шляху; малюнку 12, б >ейлеров шлях замкнутий.

 

Теорему 4. (теоремаЭйлера). У кожному кінцевому графі сума ступенів вершин дорівнює подвоєному числу його ребер. У ХІХ в. Гамільтон придумав гру, яке у тому, що у дошці розташовувалися міста, у виглядідодекаедра (рис. 13).

>Играющий (гравець) має зайняти шнуром замкнуте коло, який би з'єднав послідовно одну вершину з іншого, відвідавши у своїй все міста, зайшовши у кожний лише одне раз. Граф G називають >Гамильтоновим, коли він містить найпростіший шлях, проходить через його вершину.

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

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

Дерево рішень – це система, відбиває структуру оптимізації завдання прийняття рішень. Гілки – події, які мають місце, а вершини – стану у яких виникають проблеми вибору. Вузли вибору різні. У одних рішення приймає керівник, за іншими вибір виробляє «природа», тобто. вибір ситуації від керівника залежною і може лише оцінити можливість прийняття тієї чи іншої рішення. Дерево рішень застосовується тоді, коли кількість альтернатив й положення прийнятих рішень звісно.

Побудова дерев рішень використовують під час вирішення завдань динамічного розподілу пам'яті ЕОМ. У динамічному програмуванні вирішення завдання планування робіт називають проектом. Потрібно вибрати найкращий проект за заданий період із використанням виділених ресурсів. Існують два способу математичного вирішення цього завдання.

1) Метод найкоротшого шляху.

2) Проект оцінки й перегляду проекту.

Характерним тих методів є зображення проекту на вигляді мережі взаємозалежних робіт.

Збереження графів в ЕОМ

За виконання аналізу комп'ютері граф незручно ставити графічно, а краще представляти її як матриць, операції із якими не так важко проводитися комп'ютері.

Відомо кілька типів матриць, дозволяють ставити граф.

Матрицею суміжності графа, що міститьn-вершин, називається квадратна матриця А>nxn, кожен елемент якої а>ij визначається так:


1, якщо вершини і і j з'єднані руба чи дугою;

a>ij=

0, інакше.

Для графа з кратними ребрами (дугами) замість 1 записується число ребер (дуг) між вершинами і і j.

Для >неориентированного графа, матриця суміжності має розмірність (7 x 7) і записується як

1 2 3 4 5 6 7

А=

Зліва і згори проставлені номери вершин.

Для орієнтованого графа, матриця суміжності має розмірність (4 x 4) і записується як

1 2 3 4                        

А=

Матрицю суміжності частіше застосовують для завдання >неориентированного графа. Для завдання орієнтованого графа краще використовувати матрицюинцидентности.

Матрицеюинцидентности орієнтованого графа з n вершинами і >m ребрами називається матриця У з n рядками і >m стовпчиками, елемент якої b>ij визначається так:

1, якщо вершина є початком ребра (і, j);

-1, якщо вершина є кінцем ребра (і, j);

b>ij= 2, якщо вершина і почав, і поклала край ребра (і, j);

0, якщо вершина і ребро неинцидентни.

Для орієнтованого графа, матрицяинцидентности У>4х5 має такий вигляд:

1 2 3 4 5

У=                         

Зважений орієнтований граф без петель, у якому виділено >k-вершин, званих полюсами, є >k->полюсной ланцюгом. Серед мереж особливо вирізняється двополюсна транспортна мережу (рис. 14)S=(N, U) з безліччю вершин N і безліччю дуг U, котрим виконується таке умова:

1) є тільки одна вершина мережі >sє N, у якому не заходить жодна дуга. Ця вершина називається входом, чи джерелом мережі;

2) є тільки одна вершина мережі >tє N, з якої виходить жодної дуги мережі. Ця вершина називається виходом, чи стоком мережі;

3) кожної дузі мережі uє U поставлено відповідність ненегативне число з(u), зване пропускною спроможністю дуги.

>Рис. 14

Прикладами вершин мережі може бути перетину автострад, електростанції, телефонні вузли, залізничні вузли, аеропорти, водосховища, товарні склади.

Прикладами дуг мережі може бути дороги, ліній електропередач, телефонні лінії, авіалінії, водні магістралі, нафто- і газопроводи.

Постановку і вирішення цих завдань можна з допомогою методів мережного моделювання.

Завдання про максимальному потоці

Розглянемодвухполюсную мережу P.S=(N, U) з однією входом

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація