19 Степень вершины ПРИМЕР 1. Одноклассники Андрей, Борис, Вадим, Григорий, Дмитрий и Евгений устрои- ли турнир по настольному теннису и решили играть каждый с каждым. Турнир ещё не за- кончен. Ребра графа (рис. 24) показывают, кто с кем сыграл к этому моменту. Больше всех партий сыграли Евгений и Григорий - по три партии. Вадим пока не сыграл ни одной партии, а Андрей, Борис и Дмитрий сыграли по две. Можно сказать, что в графе на рисунке 24 степень вершины В равна 0, степени вершин А, Б, Д равны 2, а степени вершин Ги Е равны 3. Степень вершины в графе это количество исходящих из степень вершины называют валентностью вершины. Иногда приходится рассматривать граф с петлей, то есть ребром, которое исходит из вершины С равна 4. вершины и входит в неё же, то есть соединяет вершину саму с собой. При подсчёте степени вершины такое ребро считается дважды. На рисунке 25 показан граф с петлёй. Степень В п. 18 вы узнали, как доказать, что два графа одинаковы: нужно показать, что в них поровну вершин и ребра в одном графе соеди-