w . Дугу е и вершини v та w назівають
інцідентнімі между собою, а вершини v i w
суміжнімі .
Дуга ( v , v < span align = "justify">), в якій качан и Кінець збігаються назівається за сітку . Надалі розглядатімемо Тільки орграфов без петель.
Приклади орграфів показані на рис. 1.5.1. br/>В
Рис. 1.5.1 Орієнтовані графи
1.6 Представлення графів
Найбільш відомій и Популярний способ представлення графів Полягає в геометричність зображенні точок (вершин) i ліній (ребер) на папері. При чисельного вірішенні Завдання на обчислювальних машинах граф винен буті представлення дискретних способом. Існує й достатньо багатая способів такого роду представлення графів. Прото простота Використання представлення графа, як и ефективність алгоритмом, в Основі котрого ВІН лежить, ПОВНЕ мірою залежиться від конкретного Вибори. Один з напрямів Теорії графів пов'язаний з їх матричний уявленням. Існують Різні види матриць, Асоційовані з графами. Ці форми алгебри Використовують для Вирішення багатьох Завдання Теорії графів. Нижчих розглядаються Дві Такі матрічні форми I декілька нестандартних уявлень, Які найшірше Використовують в алгоритмах на графах. p align="justify"> Одним Зі способів Завдання графа G = ( V , E ) Вє Завдання кожної з множини V и E помощью Переліку їх ЕЛЕМЕНТІВ.
Приклад 1.6.1. Граф G 1 = ( V 1 < span align = "justify">, E 1 ), V 1 = { v 1 , v 2 , v
