Граф – это геометрическая фигура, состоящая из точек и соединяющих их линий. Графы представляют объекты и связи между ними.
Точки называются вершинами, а линии – рёбрами.
Степенью вершины графа называется количество выходящих из нее рёбер.
Вершина, имеющая чётную степень, называется чётной вершиной, соответственно, вершина, имеющая нечётную степень, называется нечётной вершиной.
Теорема 1. В любом графе с n вершинами всегда найдутся по крайней мере две вершины одинаковой степени.
Теорема 2. В любом графе сумма степеней всех вершин равна удвоенному числу рёбер.
Теорема 3. В любом графе число вершин нечётной степени чётно.
Маршрутом в графе называется последовательность вершин и рёбер, начинающаяся и заканчивающаяся вершиной.
Маршрут, в котором все рёбра различны, называется цепью или путём.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если рёбра в нём не повторяются.
Если в графе любые две вершины соединены путём, то такой граф называется связным.
Длина пути – это количество рёбер в нём.
