Дискретная математика

Способы задания графов

• Часть 1
• | 2
• | 3
• | 4
• | 5
• | 6

В этом можно убедиться на примере табл.3.1. 

Утверждение 3.  Сумма элементов    i - ой   строки матрицы инцидентности графа равна степени     i - ой   вершины 

                                             deg v =                                                  (3.3) 

В этом можно убедиться на примере табл.3.3. 

Утверждение 4. Для любого орграфа выполняется следующее равенство: 

                                                                       (3.4)  

Доказательство (3.4) очевидно

Утверждение 5. Сумма элементов  i - ой строки матрицы смежности ориенти-рованного мультиграфа равна полустепени исхода вершины   v , а сумма элементов

 i – го   столбца – полустепени захода  вершины   v 

degv =  ,              degv =  .                                              (3.5) 

Утверждение 6. (Теорема Эйлера о рукопожатиях). В любом конечном графе число вершин нечетной степени четно или равно нулю ( см. рис.3.1 ). 

предыдущаяследующая