пʼятниця, 12 січня 2018 р.

Введення в теорію графів

Введення в теорію графів
Розглянемо будь-яку скінчену множину елементів (міста на карті, комп’ютери в мережі, люди в соціальних мережах і т.д.) та покажемо їх точками на площині з довільним розташуванням.
Цю множину будемо називати множиною вершин графа V (від англ. vertex – вершина).
Вершини графа зручно позначати цифрами V={1, 2, …, n} або буквами V={a, b, c, …} (мал.1). 
Вершини
Мал.1 множини вершин. 
Зв’язки між елементами множини покажемо у вигляді ліній, які з’єднують відповідні точки – ребер.
Множина ребер графа задається множиною пар вершин  E (від англ. edge – ребро)(мал.2).
ребра
Мал.2 множини ребер. 
Граф – це множина вершин та множина ребер E.
Приклад. V={1, 2, 3, 4, 5}, E={(1,2), (2,3), (3,4), (2,4)}.
Якщо зв’язок між елементами множини односторонній, то його зображають у вигляді лінії із стрілкою – дугою. Граф в цьому випадку називають орієнтованим або орграфом (мал.3).
Дуга – це пара вершин графа, одна з яких є початком, а інша кінцем дуги.
Приклад. V={1, 2, 3, 4, 5, 6}, E={(1, 2), (2, 3), (3,4), (4,5), (4,2), (5,4), (6,5), (6,3), (6,6)}.
Ребро, яке з’єднує вершину з собою називається петлею.
орграф
 Мал. 3 Орграф.
Якщо між двома вершинами є можливість декількох ребер, то такий граф називають мультиграфом або кратним графом. Ребра, які з’єднують однакові вершини називають паралельними або кратними ребрами (мал.4).
мультіграф
Мал. 4 мультиграфом.
Граф називають порожнім графом, якщо в ньому немає ребер (мал.5).
Порожній граф 
Мал. 5. Порожній граф.
Повним графом називають граф, в якому будь-яка пара вершин з’єднана ребром (мал. 6).
Повний граф
Мал. 6. Повний граф.
Навантаженим графом або сіткою називають граф, в якому кожному ребру відповідає число (вага ребра) (мал. 8).
 Сітка
Мал. 7. Навантажений граф або сітка.
 Джерела:
В.М. Котов, О.І. Мельников Інформатика. Методи алгоритмізації. Мінськ 2000р.

Немає коментарів:

Дописати коментар