Введення в теорію графів
Розглянемо будь-яку скінчену множину елементів (міста на карті, комп’ютери в мережі, люди в соціальних мережах і т.д.) та покажемо їх точками на площині з довільним розташуванням.
Цю множину будемо називати множиною вершин графа V (від англ. vertex – вершина).
Вершини графа зручно позначати цифрами V={1, 2, …, n} або буквами V={a, b, c, …} (мал.1).
Мал.1 множини вершин.
Зв’язки між елементами множини покажемо у вигляді ліній, які з’єднують відповідні точки – ребер.
Множина ребер графа задається множиною пар вершин E (від англ. edge – ребро)(мал.2).
Мал.2 множини ребер.
Граф – це множина вершин V та множина ребер 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р.
Немає коментарів:
Дописати коментар