Теорія графіків: основні поняття

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

До основних понять графів належать:

• Ступінь вершини — це кількість ребер, які виходять із даної вершини.
• Шлях між двома вказаними вершинами існує, якщо ми можемо провести ребра від однієї вершини до іншої у графі.
• Відстань двох вершин — це довжина найкоротшого шляху між цими вершинами. І навпаки, нам абсолютно байдуже, на якій відстані одна від одної знаходяться вершини зображення, якщо ми малюємо граф.

Далі ми покажемо деякі розширення звичайних графів, тобто типи графів, властивості яких певним чином змінені.

В орієнтованому графі ребра мають точно визначений напрямок, у якому вони ведуть, а отже, також початкову та кінцеву вершини. Це відрізняється від графів, які ми розглядали досі: там ребра ведуть «між вершинами» і не мають заданого місця, де вони починаються і де вони закінчуються. Ребра орієнтованих графів часто зображують у вигляді стрілок.

У визначеному графі кожному ребру присвоюється певне значення (також називається вагою). На малюнку ми пишемо ваги цифрами до країв. Використовуючи ці значення, ми можемо легко показати, наприклад, довжину поїздок між містами.