Теория:

Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в управлении производством, бизнесе, при построении путей транспортировки и доставки, решении задач.
 
Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.
 
Граф — это конечное множество точек, называемых вершинами, и линий, соединяющих некоторые из вершин, называемых ребрами или дугами в зависимости от вида графа.
Пример:
graff.jpg    мультиграф.png
Рис. \(1\).                                                                  Рис. \(2\).
Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными. Две различные вершины графа, соединенные ребром, называются смежными.
Ребро не всегда соединяет разные вершины. 
Петля это ребро, которое соединяет вершину саму с собой.
 Multi-pseudograph.png
Рис. \(3\).
 
На рисунке \(3\) изображен мультиграф со смежными ребрами (выделены черным цветом), кратными ребрами (выделены красным) и  петлями (выделены синим).  
Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины \(а\) будем как γ(а).
На рисунке \(4\) изображен граф с \(7\) вершинами.
 
61.png
Рис. \(4\).
 
Составим список степеней вершин этого графа: γ(a)=1,γ(b)=5,γ(c)=2,γ(d)=2,γ(e)=3,γ(f)=2,γ(g)=1.  
Свойства графов:
  1. В каждом графе есть как минимум две вершины, имеющие одинаковую степень.
  2. Для каждого графа количество вершин нечетной степени всегда будет четное.
  3. Сумма степеней всех вершин графа равна удвоенному числу его ребер.
Маршрут на графике — это последовательность ребер a1,a2,...,an, в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.
Для графа на рисунке 5  a1,a2,a3,a7,a1,a5 — маршрут, a6,a2,a5,a7 — циклический маршрут, а последовательность a7,a6,a2,a1,a4 — маршрутом не является.
  
61.png
Рис. 5.
Цепь — это маршрут, в котором каждое ребро содержится не более одного раза. Цикл — это цепь, являющаяся циклическим маршрутом.
Для графа на рисунке \(5\) a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.
Простая цепь проходит через каждую свою вершину ровно один раз.
Цикл можно назвать простым, если он является простой цепью.
Для графа на рисунке \(5\) a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.
Связанные вершины — это вершины \(a\) и \(b\), для которых существует цепь, начинающаяся в \(a\) и заканчивающаяся в \(b\).
Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).
Один граф может иметь разное графическое изображение. Графы на рисунке \(5\) и \(6\) одинаковые.
 
63.png
Рис. 6.