Повний граф

Поняття графа

Графові моделі мають велике значення, оскільки використовуються у всіх задачах, де беруть участь кілька обє’єктів, з’єднаних між собою довільним чином (наприклад, комп'ютерні і транспортні мережі).

Отже, введемо основні визначення.

Графом G є пара (V,E) де

V є множиною вершин (vertices or nodes)

E є множиною ребер, які зв’язують вершини (set of edges)

Приклад:

V = {1,2,3,4,5}

E = {(1,2), (1,3), (1,4), (1,5), (2,3), (3,4), (4,5),(5,2)}

Рис.1 Граф

Оскільки ребра можуть іти від будь-якої вершини до будь-якої іншої, тому може бути важлива орієнтація ребер (див. Рис.2). Граф називається орієнтірованним (або орграфом), якщо для кожного ребра виділений напрямок.

Рис.2 Орієнтований граф

Приклад

V = { 1,2,3,4,5}

Повний граф

Повний граф – це граф у якого всі з’єднані всі пари вершин.

Рис. 3 Повний граф

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

Послідовність вершин, сполучених ребрами, називається шляхом.

Замкнутий шлях називається циклом.

Дата добавления: 2015-10-13