Граф

або точок) та множини ребер (Edge зв'язків або відрізків).

V = {0, 1, 2, 3} від англ. vertex
E = {e0, e1, e2, e3,} від англ. edge
e0= (0, 1)
e1= (0,2)
e2= (0,3)
e3= (1,2)
G = {V, E}

Ребро може мати направленість, тоді воно називається орієнтоване ребро або дуга. Відповідно і граф може бути орієнтованим, неорієнто-ваним, мішаним.

яке їх з'єднує.
Наприклад, вершини 0 та 1 – суміжні, а вершини 2 та 4 не є суміжними, тому що між ними немає ребра.

Інцидентність – ребро інцидентне вершині, якщо вона є його кінцем. Наприклад, ребро e4 інцидентне вершинам 3 та 4.
Шлях (Path) - це послідовність об'єднаних ребрами вершин. Наприклад, ми декілька шляхів з вершини 0 до вершини 4: 0-5-4 та 0-2-1-4, 0-1-2-3-5-4.
Якщо шлях не має повторів вершин - це простий шлях (Simple Path). Приклад шляху від 0 до 2 з повторами - 0-5-3-4-5-0-2.
Шлях буде замкненим, якщо він починається та закінчується в одній вершині. Наприклад, 0-1-2-3-4-5-0.
Графи зазвичай представляють двома способами:
Матриця суміжності – це двовимірний (2D) масив АV×V вершин. Кожний рядок і стовпець представляють певну вершину. Якщо значення будь-якого елемента Аij дорівнює 1, це означає, що існує ребро, що з'єднує вершину i вершину j.

вершині, а стовпець - ребру. Якщо значення будь-якого елемента Вij дорівнює 1, це означає, що ребро j інцидентне вершині i.

Список суміжності - представлення графу масивом зв’язного списку. Індекс масиву відповідає номеру вершини, а кожний елемент – це голова зв’язного списку із суміжних її вершин.

шляху від однієї вершини до іншої;
знаходження оптимального шляху.

Матриця ваг - це двовимірний (2D) масив СV×V, в якому кожний елемент Сij дорівнює вазі ребра (дузі), що з’єднує вершину i з вершиною j (виходить з вершини i та заходить у вершину j).

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

Граф, у якого кожному ребру (дузі) поставлено у відповідність певне число (вага) називається зваженим.