Орграф - це

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

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

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

визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

змішаний граф

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

Зрозуміло, що орієнтований і неорієнтований графи є окремими випадками змішаного.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

матриця інцидентності

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

1 в разі, якщо зв'язок j «виходить» з вершини i. -1, якщо зв'язок «входить» в вершину, будь-яке число, відмінне від 0, 1, -1, якщо зв'язок є петлею, 0 у всіх інших випадках.

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

список ребер

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

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

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

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

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

література

Популярні програми для візуалізації графів

Дивитися що таке "Орграф" в інших словниках:

орграф - orientuotasis grafas statusas T sritis automatika atitikmenys: angl. directed graph; oriented graph vok. gerichteter Graph, m; orientierter Graph, m rus. орграф, m; орієнтований граф, m pranc. graphe de fluence, m; graphe directe, m; graphe ... ... Automatikos terminų žodynas

Компонента сильної зв'язності графа - Орграф називається сильно зв'язковим (англ. Strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві вершини s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. ... ... Вікіпедія

Компонента сильної зв'язності графа - Орграф називається сильно зв'язковим (strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві пари вершин s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. Сильно зв'язковими ... ... Вікіпедія

Орієнтований граф - (коротко орграф) (мульти) граф, ребрам якого присвоєно напрямок. Спрямовані ребра іменуються також дугами, а в деяких джерелах (Оре) і просто ребрами ... Вікіпедія

ГРАФІВ ТЕОРІЯ - в хімії, область кінцевої математики, що вивчає дискретні структури, наз. графами; застосовується для вирішення різних теоретичних. і прикладних задач. Деякі основні поняття. Граф сукупність точок (вершин) і сукупність пар цих точок (Не рахую ... ... Хімічна енциклопедія

Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія

Вершина (граф) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Довжина шляху в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія