Графи.основні поняття і означення

Граф G визначається двома множинами - множиною вершин V та множиною ребер або дуг (пар вершин) E: G=(V, E). Якщо пара вершин неупорядкована, то її прийнято називати ребром, а якщо упорядкована - дугою. Граф, що складається тільки з ребер називається неорієнтованим графом. Граф, що містить тільки дуги, - орієнтованим графом чи орграфом.

На малюнку граф можна представити точками, що відповідають вершинам графа, та лініями, що з'єднують вершини і відповідають ребрам графа, або спрямованими від вершини до вершини лініями, що відповідають дугам графа.

<="" p="">

Дві вершини x та y, що з'єднані ребром (x, y), називають суміжними вершинами. Якщо вершини з'єднані дугою (x, y), то вершина x суміжна вершині y, а зворотної суміжності немає.

Два ребра називають суміжними ребрами, якщо вони мають спільну вершину.

Ребро і будь-яка з двох його вершин називаються інцидентними.

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

Способи подання графа. Приклади.

Граф G =(V,E) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам v i w, з'єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Графи можна задавати також за допомогою матриць.

Занумеруємо всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна n*n-матриця, в якій елемент aij і-го рядка і j-го стовпчика дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 у противному разі.

Очевидно, що матриці суміжності неорієнтовних графів симетричні.

Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра числами від 1 до m. Матрицею інцидентності B графа G називається n*m-матриця, в якій елемент bij і-го рядка і j-го стовпчика дорівнює 1, якщо вершина vi з номером i інцидентна ребру ej з номером j, і дорівнює 0 у противному разі.