цьому x - початок (початкова вершина) дуги, x - кінець (кінцева вершина) дуги. Кажуть також, що дуга виходить з вершини xі заходить у вершину x. Зауважимо, що і - Це різні дуги в графі. При зображенні орграфа дуги позначаються стрілками, що вказують їх орієнтацію (направлення). Пара вершин (x, x) у графі може з'єднуватися двома або більше ребрами (дугами одного напрямку).
Відзначимо, що будь неорієнтовані граф можна представити у вигляді орграфа шляхом заміни кожного його ребра двома протилежно спрямованими дугами. [1]
Іноді дуг графа G зіставляються (приписуються) числа - дузі (x, x) ставиться у відповідність деяке число с, зване вагою, або довжиною, або вартістю (ціною) дуги. Тоді граф G називається графом зі зваженим дугами. Іноді ваги (числа v) приписуються вершин x графа, і тоді виходить граф зі зваженими вершинами. Якщо в графі ваги приписані і дуг, і вершин, то він називається просто зваженим.
Петлею називається дуга, початкова та кінцева вершини якої збігаються. Прикладом петлі є дуга u на малюнку 1. [2]
Послідовність ребер неорграфа (x, x), ...., (x, x), в якій кінець кожного попереднього ребра збігається з початком наступного, називається маршрутом, що з'єднує вершини x і x. Аналогом маршруту для орграфа є орієнтований маршрут з x в x, що представляє собою послідовність дуг, в якій кінець попередньої дуги збігається з початком наступної. При цьому x і xназиваются початковою і кінцевою вершинами маршруту. Якщо будь-які дві вершини графа з'єднані маршрутом, то граф називається зв'язковим.
Маршрут є замкнутим, якщо початкова вершина збігається з кінцевою, і незамкнутим в іншому випадку. Незамкнутий маршрут, в якому всі ребра різні, називають ланцюгом. Незамкнутий орієнтований маршрут, який містить попарно різні дуги називається шляхом. Ланцюг (шлях) у якій (в якому) всі вершини попарно різні, називається простий (простим).
Замкнута ланцюг називається циклом, замкнута проста ланцюг - простим циклом. Замкнутий шлях називається контуром, замкнутий простий шлях - простим контуром. Граф, що не містить циклів, називають ациклічним.
Число дуг, що виходять з вершини x орієнтованого графа, називається полустепенью результату вершини x і позначається (x). Число дуг, що заходять в вершину x, називається полустепенью заходу вершини x і позначається (x). [1]
Раніше ми розглянули графічні способи завдання графа. Існують і інші способи визначення графа, наприклад за допомогою матриці суміжності. Нехай дано граф G (малюнок 3)
Рисунок 3 - Граф G
Матрицею суміжності неорієнтованого графа G=(X, U) з n вершинами називається квадратна матриця А порядку n, елементи якої визначаються таким чином:
Для орієнтованого графа:
Отже, матриця суміжності графа, зображеного на малюнку 3 має вигляд, в іншому випадку
Малюнок 4 - Матриця суміжності графа G
петлю в матриці суміжності відповідають елементи, розташовані на головній діагоналі. Матриця суміжності повністю визначає структуру графа. Наприклад, сума всіх елементів рядка x матриці дає полустепені результату вершини x, а сума елементів стовпця x - полустепені заходу вершини x. Безліч стовпців, що мають 1 в рядку x, є безліч Г (x), а безліч рядків, які мають 1 у стовпці x, збігається з безліччю Г (x). [2]
