Означення графа. Зображення графів

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

Приклад 1. Нехай ,

. Тоді множини  і  визначають граф .

    Будь-який граф  визначається відношенням інцидентності між множинами вершин  і ребер . Якщо вершина  є кінцем ребра , то кажуть, що  інцидентна . Відношення інцидентности є узагальненням відношення належності, воно нерефлексивне і симетричне. Зауважимо, що кожен елемент  інцидентний рівно двом елементам  і  з .

Означення. Два ребра, інцидентні одній вершині, називаються суміжними; дві вершини, інцидентні одному ребру , також називаються суміжними.

Часто розглядають наступні поріднені до графів об’єкти.

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

Означення. Якщо елементом множини  є пара однакових елементів множини , то такий елемент множини  називається петлею, а граф називається графом з петлями (або псевдографом).

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

Приклад 2. Нехай ,

. Тоді  - граф (мультиграф),  - петля,  - кратне ребро.

Введене поняття графа є абстрактним.

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

Означення. Фігура  називається геометричним зображенням графа G , якщо існує взаємно однозначна відповідність між вершинами фігури  и вершинами графа , а також між кривими фігури  и ребрами графа  така, що якщо , то   (відповідні криві і ребра з'єднують відповідні вершини).

Приклад 3. Наступні фігурі є геометричним зображенням графів з прикладів 1 і 2.

Приклад 1.                                          Приклад 2.

 

 - ізольована вершина; ,  - кінцеві вершини$

ребро  - петля, ребро  - кратне ребро.

Теорема.(Про геометричне зображення скінченного графа). Будь-який скінченний граф може бути зображений у 3-вимірному евклідовому просторі.

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

Приклад 4.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: