Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
|
|
Граф Г называется полным, если каждые две его вершины соединены одним и только одним ребром.
А В
С Д - не полный граф
А В
С Д - полный граф
Только для неориентированного графа существует дополнение:
 |
Г
– дополнение
Дополнением графа Г называется новый граф , состоящий из всех тех же вершин, что и граф Г и тех и только тех ребер, которые надо добавить, чтобы граф Г стал полным.
Степенью вершины называется количество ребер ей принадлежащих
В Д
Е
А С
Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0
Степень каждой вершины полного графа на единицу меньше числа вершин.
Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер
При большом количестве вершин схема теряет свою наглядность и поэтому используют другой способ задания графов в виде матрицы смежностей.
где каждое 
М – симметричная на главной диагонали – 0
М(Г)=
|
|