ідовності вершин ребром.
Орієнтованим шляхом у орграфе називають кінцеву послідовність вершин vi, для якої всі пари (vi, vi + 1) є (орієнтованими) ребрами.
Циклом називають шлях, в якому перша і остання вершини збігаються. При цьому довжина шляху (або циклу) називають число складових його ребер. Зауважимо, що якщо вершини u і v є кінцями деякого ребра, то згідно з цим визначенням, послідовність (u, v, u) є циклом. Щоб уникнути таких В«виродженихВ» випадків, вводять такі поняття. p align="justify"> Шлях (або цикл) називають простим, якщо ребра в ньому не повторюються; елементарним, якщо він простий і вершини в ньому не повторюються. Нескладно бачити, що, всякий шлях, що з'єднує дві вершини, містить елементарний шлях, що з'єднує ті ж дві вершини. Всякий простий Неелементарні шлях містить елементарний цикл. Всякий простий цикл, що проходить через деяку вершину (або ребро), містить елементарний (під-) цикл, що проходить через ту ж вершину (або ребро). Петля - елементарний цикл. p align="justify"> Граф з петлями і кратними ребрами (дугами) називається псевдографом. Граф з кратними ребрами (дугами) і без петель називається мультиграфом. p align="justify"> Граф, що не містить петель і кратних ребер, називається простим графом.
Дві вершини графа xi і хj називаються суміжними, якщо існує з'єднує їх ребро (дуга). Два ребра (дуги) суміжні, якщо вони мають спільну вершину
Безліч вершин графа називається незалежним, якщо ніякі дві вершини цього множини не з'єднані ребром. Іншими словами, індукований цим безліччю подграф складається з ізольованих вершин. Іноді також говорять, що кожне ребро графа інцидентне не більше ніж одній вершині з незалежного множини. br/>
Способи представлення графа в інформатиці
Матриця суміжності. Таблиця, де як стовпці, так і рядки відповідають вершинам графа. У кожній клітинці цієї матриці записується число, що визначає наявність зв'язку від вершини-рядка до вершини-колонки (або навпаки). p align="justify"> Недоліком є ​​вимоги до пам'яті, прямо пропорційні квадрату кількості вершин, двовимірний масив; матриця з пропусками; неявне завдання (за допомогою функції).
Матриця інцидентності. Кожен рядок відповідає певній вершині графа, а стовпці відповідають зв'язкам графа. У комірку на перетині i-го рядка з j-м стовпцем матриці записується: 1в випадку, якщо зв'язок j В«виходитьВ» з вершини i,? 1, якщо зв'язок В«входитьВ» у вершину, 0 у всіх інших випадках (тобто якщо зв'язок є петлею або зв'язок не інцидентна вершині)
Даний спосіб є найбільш ємним (розмір пропорційний | E | | V |) для зберігання, але полегшує знаходження циклів у графі.
Список ребер - це тип представлення графа в пам'яті комп'ютерної програми, що припускає, що кожне ребро представляється двома ...
