Характеристики графа

Определение 1. Граф G(X,T) называется полным, если любые две различные вершины соединены одним, и только одним ребром.

Пример 1. Граф

является полным.

В полном графе каждая вершина принадлежит одному и тому же числу ребер, так как она соединена со всеми остальными вершинами. Для задания полного графа достаточно знать число его вершин. Граф, являющийся неполным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра.

Определение 2. Дополнением графа G(X,T) называется граф с теми же вершинами, что и граф G(X,T), и теми ребрами, которые необходимо добавить к графу G(X,T), чтобы получился полный граф.

Пример 2.

G(X,T) Полный граф

Определение 3. Степенью вершины x_i графа G(X,T) называется число d_i, равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень - четное (нечетное) число.

Теорема 1. Если конечный граф G(X,T) (без петель) имеет n вершин и m ребер, то

. (1)

Доказательство. Рассмотрим граф

Очевидно, что d ₁=3, d ₂ =2, d ₃ =2, d ₄ =3. Сложим эти числа:
d ₁ + d ₂ + d ₃ + d ₄=10. В этой сумме каждое ребро участвует дважды: 10:5=2.

Рассмотрим произвольный граф G(X,T). Каждая вершина графа x_i инцидентна d_i ребрам. Если сложить эти величины по всем вершинам, то в полученной сумме каждое ребро будет участвовать дважды, т.е. эта сумма будет равна 2 m.

Теорема 2. Число нечетных вершин любого графа четно.

Доказательство. Так как левая часть равенства (1) является четным числом, то нечетных вершин должно быть четное число.

Теорема 3. Во всяком графе с n вершинами (n >2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

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

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