Матрица на пътя
За свързан граф, чиито върхове са преномерирани, е възможно да се построи матрица от пътища (или вериги)Pкакто следва: редовете на матрицата трябва да съответстват на пътищата от първия връх до последния, а колоните - на ръбовете на графиката. Следователно матричният елемент приема стойност 1 или 0 в зависимост от това дали даденото ребро принадлежи на дадения път или не. Например графиката, показана на фиг. 11 има матрица на пътя между върховеv1иv5:
Фиг.11. Графика за илюстриране на матрицата на пътя
Представяне на графики като списъци
Можете да свържете списъкаLvкъм всеки връхvV. По този начинLvе списък от върхове, съседни наv(например Фиг.12).
Друго представяне на графики е възможно с помощта на списък с връзки. Изборът на представяне зависи от използваните алгоритми.
а) б)
Ориз. 12. Попълнете графика (a) и нейните списъци със съседства (b)
Подредени графики
Представянето на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).