Способы задания графов
Геометрический (графический)
Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.
Теоретико-множественный
Матричный
А) Матрица инцидентности
n-число вершин, m – число дуг или ребер
Для неорграфа:
Б) Матрица смежности
Неорграф:
Орграф:
Маршруты, цепи, циклы
Маршрутом в графе называется {x1,r1,x2,r2,…xn}
чередующиеся последовательность вершин и ребер/дуг.
Неорграф:
Цепью ρ=(r1, … rn) называется упорядоченная последовательность ребер в которой у каждого ребра ri одна из граничных вершин является граничной вершиной ri-1, а другие ri+1. Если вершины и ребра в цепи различны, то маршрут называют простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь называется простым циклом.
Орграф:
Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур. Длина цепи – число ребер в цепи. Граф называется связным, если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xj называется расстоянием. 
Максимальное расстояние между вершинами графа называется диаметром графа. 
. Цепь (неорграф) называют составной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно 1 раз. В орграфе путь, проходящий через все вершины ровно 1 раз, называется гамильтоновым, если у него начальная и конечная вершина совпадают, то гамильтонов контур.
Алгоритм Дейкстры.
Пусть l (xi) – пометка вершины xi.
Шаг 1. Присвоение начальных значений. Положить l* (s) = 0 и считать эту пометку постоянной. Положить l (xi) = ∞ (бесконечность) для всех xi ¹ s и считать эти пометки временными. Положить р=s.
Шаг 2. Обновление пометок. Для всех вершин xi Î Г (р), имеющих временные пометки, изменить пометки в соответствии с выражением:
l (xi) = min{ l (xi), l (p) + c (p, xi)}. (2.3)
Шаг 3. Превращение пометки в постоянную. Среди всех вершин с временными пометками найти такую, для которой l* (xi) = min{ l (xi)}.
Шаг 4. Считать пометку вершины xi* постоянной и положить p = xi*.
Шаг 5. Если р=t, то l* (р) является длиной кратчайшего пути. Конец.
Если р ¹ t, перейти к шагу 2.
Как только длина кратчайшего пути от s до t будет найдена [она будет постоянной пометкой вершины l* (t)], сами пути можно получить с помощью рекурсивной процедуры. Так, для вершины xk, непосредственно предшествующей вершине t в кратчайшем пути от s к t, будет соблюдаться отношение: l* (xk) + c (xk, t) = l* (t).
Таким образом, для любой вершины xi можно найти предшествующую вершину xk, принадлежащую пути m (s, t), для которой справедливо:
l* (xk) + c (xk, xi) = l* (xi). (2.4)
Если существуют несколько кратчайших путей от s к t, то данное соотношение будет выполняться для нескольких вершин. В этом случае выбор пути может быть произвольным.
Метод Форда-Беллмана решения задачи о кратчайшем пути в графе.
Алгоритм Ф.Б. позволяет находить кратчайшие пути от источника S до любой вершины, при этом веса дуг могут быть как “+”, так и “-“.
Исходные данные: граф C помечен дугами, а результат помечен вершинами.
1) Присвоение начального значения меток
Установить номер итерации k=0, присвоить начальное значение меток следующим образом:
2) Обновление пометки вершин
Для каждой вершины Xj =Г(S) установить пометку следующим образом:
Где Tj = Г-1 множество вершины, которые входят в Xj и связан с вершиной X
3) Проверка условий окончания
Если k <= n-1 и Пк+1 (Xj)!= Пк (Xj) хотя бы для 1 вершины, то переход к шагу 4 если
Пк+1 (Xj) = Пк (Xj), то конец алгоритма.
4) Подготовка к следующей итерации
Определить множество S, как множество таких X, что
Пометки П (Xi) у всех вершин графа характеризуют расстояние от источника Х1 до данной вершины.
