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