Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Граф (математика)



План:


Введення

Неорієнтований граф з шістьма вершинами та сімома ребрами

У математичній теорії графів і інформатики граф - це сукупність непорожньої безлічі вершин і безлічі пар вершин.

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

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


1. Визначення

Теорія графів не володіє усталеною термінологією. У різних статтях під одними і тими ж термінами розуміються різні речі. Наведені нижче визначення - найбільш часто зустрічаються.

1.1. Граф

Undirected.svg

Граф або неорієнтований граф G - Це упорядкована пара G: = (V, E) , Для якої виконані наступні умови:

  • V це непорожня безліч вершин або вузлів,
  • E це безліч пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами.

V (А значить і E , Інакше воно було б мультімножество) зазвичай вважаються кінцевими множинами. Багато хороші результати, отримані для кінцевих графів, невірні (або яким-небудь чином відрізняються) для нескінченних графів. Це відбувається тому, що ряд міркувань стає помилковим у разі нескінченних множин.

Вершини і ребра графа називаються також елементами графа, число вершин у графі | V | - Порядком, число ребер | E | - Розміром графа.

Вершини u і v називаються кінцевими вершинами (або просто кінцями) ребра e = {u, v} . Ребро, в свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми.

Два ребра називаються суміжними, якщо вони мають загальну кінцеву вершину.

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

Ребро називається петлею, якщо його кінці збігаються, тобто e = {v, v} .

Ступенем deg V вершини V називають кількість ребер, для яких вона є кінцевий (при цьому петлі вважають двічі).

Вершина називається ізольованою, якщо вона не є кінцем для жодного ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.


1.2. Орієнтований граф

Directed.svg

Орієнтований граф (скорочено орграф) G - Це упорядкована пара G: = (V, A) , Для якої виконані наступні умови:

  • V це непорожня безліч вершин або вузлів,
  • A це безліч (впорядкованих) пар різних вершин, званих дугами або орієнтованими ребрами.

Дуга - це впорядкована пара вершин (v, w), де вершину v називають початком, а w - кінцем дуги. Можна сказати, що дуга v \ to w веде від вершини v до вершини w.


1.3. Змішаний граф

Змішаний граф G - Це граф, в якому деякі ребра можуть бути орієнтованими, а деякі - неорієнтованим. Записується впорядкованої трійкою G: = (V, E, A) , Де V, E і A визначені так само, як вище.

Орієнтований і неорієнтований графи є окремими випадками змішаного.

1.4. Ізоморфні графи

Граф G називається ізоморфним графу H , Якщо існує біекція f з безлічі вершин графа G в безліч вершин графа H , Що володіє наступною властивістю: якщо у графі G є ребро з вершини A в вершину B , То в графі H повинно бути ребро з вершини f (A) в вершину f (B) і навпаки - якщо в графі H є ребро з вершини A в вершину B , То в графі G повинно бути ребро з вершини f - 1 (A) в вершину f - 1 (B) . У випадку орієнтованого графа ця біекція також повинна зберігати орієнтацію ребра. У випадку зваженого графа біекція також повинна зберігати вагу ребра.


1.5. Інші пов'язані визначення

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

Орієнтованим шляхом в Орграф називають кінцеву послідовність вершин v i (I = 1, \ ldots, k) , Для якої всі пари (V i, v i + 1) (I = 1, \ ldots k-1) є (орієнтованими) ребрами.

Циклом називають шлях, в якому перша і остання вершини збігаються. При цьому довжиною шляху (або циклу) називають число складових його ребер. Зауважимо, що якщо вершини u і v є кінцями деякого ребра, то згідно з цим визначенням, послідовність (U, v, u) є циклом. Щоб уникнути таких "вироджених" випадків, вводять такі поняття.

Шлях (або цикл) називають простим, якщо ребра в ньому не повторюються; елементарним, якщо він простий і вершини в ньому не повторюються. Нескладно бачити, що:

  • Всяка дорога, що сполучає дві вершини, містить елементарний шлях, що з'єднує ті ж дві вершини.
  • Всякий простий неелементарний шлях містить елементарний цикл.
  • Всякий простий цикл, що проходить через деяку вершину (або ребро), містить елементарний (під-) цикл, що проходить через ту ж вершину (або ребро).
  • Петля - елементарний цикл.

Бінарне відношення на множині вершин графа, заданий як "існує шлях з u в v ", Є ставленням еквівалентності, і, отже, розбиває це безліч на класи еквівалентності, що називаються компонентами зв'язності графа. Якщо у графа рівно одна компонента зв'язності, то граф зв'язний. На компоненті зв'язності можна ввести поняття відстані між вершинами як мінімальну довжину шляху, що з'єднує ці вершини.

Всякий максимальний зв'язний подграф графа G називається зв'язковий компонентою (або просто компонентою) графа G. Слово "максимальний" означає максимальний щодо включення, тобто не міститься в зв'язковому підграфі з великим числом елементів

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


1.6. Додаткові характеристики графів

Граф називається:

  • зв'язковим, якщо для будь-яких вершин u , v є шлях з u в v .
  • сильно зв'язковим або орієнтовано зв'язковим, якщо він орієнтований, і з будь-якої вершини в будь-яку іншу мається орієнтований шлях.
  • деревом, якщо він зв'язний і не містить простих циклів.
  • повним, якщо будь-які його дві (різні, якщо не допускаються петлі) вершини з'єднані ребром.
  • дводольним, якщо його вершини можна розбити на два непересічних підмножини V 1 і V 2 так, що всяке ребро з'єднує вершину з V 1 з вершиною з V 2 .
  • k-долинним, якщо його вершини можна розбити на k непересічних підмножини V 1 , V 2 , ..., V k так, що не буде ребер, що з'єднують вершини одного і того ж підмножини.
  • повним дводольним, якщо кожна вершина одного підмножини з'єднана ребром з кожною вершиною іншого підмножини.
  • планарним, якщо граф можна зобразити діаграмою на площині без перетинань ребер.
  • зваженим, якщо кожному ребру графа поставлено у відповідність деяке число, зване вагою ребра.

Також буває:


2. Способи представлення графа в інформатиці

2.1. Матриця суміжності

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

Недоліком є ​​вимоги до пам'яті, прямо пропорційні квадрату кількості вершин.

  • Двовимірний масив;
  • Матриця з пропусками;
  • Неявне завдання (за допомогою функції).

2.2. Матриця інцидентності

Кожен рядок відповідає певній вершині графа, а стовпці відповідають зв'язкам графа. У комірку на перетині i -Го рядка з j -М стовпцем матриці записується:

1
у випадку, якщо зв'язок j "Виходить" з вершини i ,
-1,
якщо зв'язок "входить" в вершину,
0
у всіх інших випадках (тобто якщо зв'язок є петлею або зв'язок не інцидентна вершині)

Даний спосіб є самим ємним (розмір пропорційний | E | | V | ) Для зберігання, але полегшує перебування циклів в графі.


2.3. Список ребер

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

3. Узагальнення поняття графа

Простий граф є одновимірним сімпліціальним комплексом.

Більш абстрактно, граф можна задати як трійку (V, E, φ) , Де V і E - Деякі безлічі (вершин і ребер, соотв.), А \ Varphi - Функція інцидентності (або інцідентор), що зіставляє кожному ребру e \ in E (Впорядковану або невпорядковану) пару вершин u і v з V (Його кінців). Окремими випадками цього поняття є:

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

Під дане вище визначення не підходять деякі інші узагальнення:


Література

  • Оре О. Теорія графів. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
  • Уілсон Р. Введення в теорію графів. Пер з англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
  • Харарі Ф. Теорія графів. М.: Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
  • Кормен Т. М.І ін Частина VI. Алгоритми для роботи з графами / / Алгоритми: побудова й аналіз = INTRODUCTION TO ALGORITHMS - 2-е вид. - М .: "Вільямс", 2006. - С. 1296. - ISBN 0-07-013151-1.
  • Салій В. Н. Богомолов А. М. Алгебраїчні основи теорії дискретних систем - М .: Фізико-математична література, 1997. - ISBN 5-02-015033-9.
  • Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М.: Наука, 1990. 384с. (Ізд.2, испр. М.: УРСС, 2009. 392 с.)
  • Кірсанов М. Н. Графи в Maple. М.: Физматлит, 2007. - 168

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
E8 (математика)
Математика
G2 (математика)
E6 (математика)
F4 (математика)
Пара (математика)
Варіація (математика)
Алфавіт (математика)
Мінімум (математика)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru