Теория:

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