Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.

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

А В

С Д - не полный граф

А В

С Д - полный граф

Только для неориентированного графа существует дополнение:

Г

– дополнение

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

Степенью вершины называется количество ребер ей принадлежащих

В Д

Е

А С

Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0

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

Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер

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

где каждое

М – симметричная на главной диагонали – 0

М(Г)=