Свойства вершин и рёбер

Основное свойство ребра – инцидентность (двум) вершинам, а вершины – инцидентность ребру. Следовательно, для каждой вершины определено понятие степени: это число инцидентных вершине ребер (т.е. исходящих или входящих). Если граф ориентирован, то следует различать входящие и исходящие линии: в этом случае говорят о полустепени захода и полустепени выхода.

Ø Вершина может иметь степени: 0,1,2…

Ø Степень 0: изолированная вершина:

Ø Степень 1: висячая вершина:

Ø Вершины смежные (инцидентные) = соединенные ребром. Множество Г (v) вершин, смежных с v.

Ø Рёбра могут быть:

Ø инцидентными вершине, т.е. выходящие/входящие из вершины;

Ø смежными, т.е. исходящими из одной вершины;

Ø кратными.

Ø Лемма о рукопожатиях: сумма степеней всех вершин чётна:

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

Теорема. Во всяком графе, имеющем не менее 2-х вершин, найдутся по крайней мер две вершины с одинаковыми степенями.

Предположим противное: пусть все степени вершин разные. Единственный вариант для графа с n вершинами: n-1, n-2, …, 0. Но если есть изолированная вершина, то не может быть вершины степени n-1.

Следствие. Задача о турнире: всегда найдутся команды, сыгравшие одинаковое количество игр.

Теорема. Если в графе в точности 2 вершины имеют одинаковую степень, то в этом графе всегда найдется в точности одна вершина, имеющая степень 0, или в точности одна вершина, имеющая степень n-1.

Из возможных значений степеней вершин: n-1, n-2, …, 0 две вершины имеют одинаковую степень – значит, на оставшиеся n-2 вершины приходится n-1 возможная степень, среди которых есть 0 и n-1. Отсюда следует, что хотя бы две из них будут иметь одинаковую степень. Осталось доказать, что две вершины не могут иметь одновременно степень 0 или n-1. Если 0 – останется граф с n-2-мя вершинами, в котором всегда найдутся 2 вершины с одинаковыми степенями. Для доказательства невозможности 2-х вершин степени n-1 следует перейти к дополнению графа и тем самым свести к случаю вершины степени 0.