Теория:

Наглядным средством представления состава и структуры системы является граф.
 
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.
 
Основы теории графов как математической науки заложил в \(1736\) г. Леонард Эйлер, рассматривая задачу о Kёнигсбергских мостах. Сегодня эта задача стала классической.
 
1.png
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Обрати внимание!
Точки называются вершинами графа, а соединяющие линии — рёбрами.
2.png
Количество рёбер, выходящих из вершины графа, называется степенью вершины.
Обрати внимание!
Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.
3.png
Изолированная вершина — вершина, степень которой равна \(0\).
 
Конечная вершина графа — вершина, степень которой равна \(1\).
 
Направленная линия (со стрелкой) называется дугой.
 
Линия ненаправленная (без стрелки) называется ребром.
 
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй.
4.png
 
Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двухсторонним, поэтому вершины соединены линиями без стрелок.
 
5.png
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
 
Граф называется неориентированным, если его вершины соединены ребрами.
 
Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.
 
Цикл — цепь, начальная и конечная вершины которой совпадают.
 
Граф с циклом называют сетью.
 
Ориентированный граф — граф, рёбрам которого присвоено направление.
С помощью таких графов могут быть представлены схемы односторонних отношений.
 
6.png
 
Если все вершины графа чётные, то можно одним росчерком пера начертить граф. При этом начать движение можно с любой вершины и закончить в той же вершине.

Граф с двумя нечётными вершинами также можно начертить одним росчерком. Начинать движение надо с одной нечётной вершины, а заканчивать в другой.
Граф с большим количеством нечётных вершин невозможно начертить таким образом.