Графічне зображення графа та інші способи його представлення, відношення інцидентності. Дослідження оптимального шляху графа. Проведення синтезу графа, визначення ваги ребер та індексів вершин, що має задану структуру та заданий оптимальний шлях.
Аннотация к работе
Мета роботи - навчитися визначати оптимальний шлях (мінімальної довжини) у заданого графа, а також виконувати синтез графа (визначення ваги всіх ребер та індексів всіх вершин), що має задану структуру та заданий оптимальний шлях. Іншими словами, граф - це дві множини, що взаємно відповідають одна інший, - множина вершин та множина ребер (множина бінарних відношень вершин), кожне (ребро) з яких відповідає парі елементів (допускаються однакові елементи) з множини вершин. Граф називається скінченним, якщо множини його вершин та ребер є скінченими (надалі розглядаються лише такі графи). Якщо елемент e (ребро) сукупності E є парою елементів (вершин) v та w: e=(v, w), то кажуть: - вершини v та w суміжні; Ребро може зєднувати вершину саму з собою (рис.1, г), таке ребро називається петлею.