Решение.

Задача.

Пример.

Пример.

Пример.

Определение 11 . Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется нечетной, если ее степень – нечетное число. Вершина называется четной, если ее степень число четное.

Замечание. Степень каждой вершины полного графа на единицу меньше числа его вершин.

Рассмотрим задачу: Как можно пройти по ребрам графа, изображенного на рисунке, из вершины А₁ в вершину А₅?

Решение.

Определение 12. МаршрутомотА₁ до А_n в графе называется чередующаяся последовательность вершин и инцидентных им ребер, т.е. такая последовательность ребер, ведущая отА₁ до А_n, в которой каждые два соседние ребра имеют общую вершину.

Определение 13. Маршрут называется путем или цепью, если все его ребра различны, т.е. никакое ребро не встречается более одного раза.

В примере все даны маршруты, при этом 1) и 2) – пути, а 3) и 4) – не пути.

Определение 14. Путь называется простой цепью или простым путем, если все его вершины (за исключением, может быть, первой и последней) различны. (Т.е. путь не проходит ни через одну из вершин графа более одного раза).

Определение 15. Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Если при этом цепь – простая, то она называется простым циклом.

В примере acbdeba – цикл, но не простой; acdeba – простой цикл.

Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

Каждого из компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком.

Из рассматриваемой компании нельзя выделить ни четырехугольник, ни треугольник, поскольку тогда условие задачи будет нарушено, т.е. схема единственна.

Данный граф – цикл.

Определение 16. Если все вершины графа имеют одну и ту же степень r, то граф называется однородным графом степени r.

Например, простой цикл является однородным графом степени 2.

Теорема 1.( Первая теорема теории графов. Доказана Эйлером.)

Сумма степеней вершин(p, q) – графа равна удвоенному числу его ребер: .

Определение 17. Длиной маршрута называется число ребер в нем, при этом каждое ребро считается столько раз, сколько оно встречается в данном пути. Длиной пути называется число ребер пути. Длиной цикла называется число ребер цикла.

Определение 18. Две вершины графа А и В называются связными, если существует путь с концами А и В.

Определение 19. Граф называется связным, если каждые две вершины его связные, иначе, если любая пара его вершин соединяется цепью. Граф называется несвязным, если хотя бы две вершины несвязные.

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

Определение 20. Максимально возможный связный подграф графа G называется компонентой графа G.

Несвязный граф имеет по крайней мере две компоненты.

Определение 21. Ребро (А,В) называется мостом графа G, если в графе, полученном после удаления из графа G ребра (А,В) вершины А и В оказываются несвязными.