Матриця шляхів
Для зв'язкового графа, вершини якого перенумеровані, можна побудувати матрицю колій (або ланцюгів)Рнаступним чином: рядки матриці повинні відповідати коліям з першої вершини в останню, а стовпці – ребрам графа. Отже, елемент матриці приймає значення 1 або 0 залежно від того, належить це ребро даному шляху чи ні. Наприклад, граф, зображений на рис. 11, має матрицю шляхів між вершинамиv1іv5:
Рис.11. Граф для ілюстрації матриці шляхів
Подання графів у вигляді списків
Можна зв'язати списокLvз кожною вершиноюvV. Таким чином,Lv- це список вершин, суміжних зv(наприклад, рис.12).
Можливе інше уявлення графів за допомогою списку зв'язків. Вибір уявлення залежить від алгоритмів.
а) б)
Мал. 12. Повний граф (а) та його списки суміжності (б)
Упорядковані графи
ПоданняLvвершин, суміжних зv,у вигляді списку зв'язків визначає «порядок» ребер, що виходять зv(рис. 13 ).
Мал. 13. Приклад упорядкованого графа
Для того щоб структури, що розглядаються, були графами, необхідно накласти деякі умови на спискиLv:
Граф, зображений на рис. 13 може бути представлений у термінах упорядкованого графа наступним чином:
Упорядкований граф визначає єдиний невпорядкований граф. Зворотне твердження неправильне, оскільки у випадку можливо багато способів упорядкування графа.
Завдання знаходження шляхів у графах
Рефлексивним і транзитивним замиканням графаGназивається графG*, який містить те ж безліч вузлів, що іG, але в якому зvуwйде ребро тоді і тільки тоді, коли вGіснує шлях (довжини 0 або більше) зvдоw.
Із завданням знаходження транзитивного замикання тісно пов'язана задача про найкоротший шлях.
Поставимо у відповідність кожному ребруeграфаG = (V, E)невід'ємну вартістьc(e).Вартість шляху визначається як сума вартості ребер, що утворюють цей шлях . Завдання про найкоротший шлях полягає в знаходженні для кожної пари вузлів(v,w)шляхи найменшої вартості серед усіх шляхів зvдоw.
Поруч із поняттям вартості шляху застосовується поняття мітки шляху. Визначимо мітку шляху як добуток міток ребер, що становлять цей шлях. Причому мітки беруться у порядку проходження ребер. Зокрема, мітка шляху нульової довжини дорівнює 1. Для кожної пари вузлів(v, w)визначимоc(v,w)як суму міток усіх шляхів міжvтаw. Назвемоc(v,w)вартістю проходження зvуw.
Наприклад, розглянемо орієнтований граф, у якому кожне ребро позначено елементом півкільцяS1 = (, +, , 0, 1)(рис. 14).