Множество задач в математике можно решить с помощью графа.

Граф – это совокупность объектов со связями между ними. Объекты представляются вершинами, а связи – ребрами.

Таким образом, чтобы ввести граф требуется ввести вершины и ребра, то есть сказать - что в задаче обозначено за вершины, а что за ребра.

Степенью вершины называют количество ребер, исходящих из вершины. Вершина называется изолированной, если она имеет степень 0. Вершина называется висячей, если ее степень 1. Вершина графа, имеющая нечётную степень, называется нечётной, а имеющая чётную степень – чётной.

Лемма о рукопожатиях. В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Следствие. В любом графе число вершин нечетной степени четно.

Если в графе любые две вершины соединены последовательностью вершин и ребер, то такой граф называется связным.

Теорема. Граф с n вершинами, степень каждой из которых не менее (n-1)/2, связен.

Если граф не связен, то он распадается на компоненты связности, то есть связные подграфы.

свернуть