Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Степени вершин графа

Степенью вершины графа называется количество инцидентных ей ребер (для петли степень подсчитывается дважды). Через а(х) будем обозначать степень вершины х. Для графа на рис. 4 вершины имеют следующие степени:

Ясно, что степень любой вершины конечного графа есть целое неотрицательное число. Вообще, определенное нами понятие степени имеет смысл лишь для вершин, инцидентных конечному числу ребер, при этом множество вершин и множество ребер графа могут быть бесконечными. Так, на рис. 6 представлен бесконечный граф, все вершины которого имеют степень 4 (кроме первой вершины, имеющей степень 2). Этот граф моделирует так называемые размножения».

процессы «гибели

Рис. 6

Вершина графа степени 0 называется изолированной. Если степень вершины равна 1, то она называется концевой или висячей вершиной. Вершина, степень которой больше или равна 2, называется промежуточной или проходной. Так, на рис. 4 вершина D - изолированная, вершина С - висячая, а остальные вершины - проходные.

Вершины графа называются четными или нечетными в зависимости от четности их степеней. Так, в графе на рис. 6 все вершины - четные. Граф на рис. 4 имеет две нечетные вершины (С и Н),а остальные вершины этого графа - четные.

Теорема 1. В любом конечном графе G(V, Е) количество нечетных вершин - четно.

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

Здесь через Е обозначено число элементов во множестве

Е, т.е. количество ребер графа G. Формула (1.4.1) показывает, что сумма степеней всех вершин графа есть четное число. Поэтому в эту сумму может входить лишь четное количество нечетных слагаемых, т.е. количество нечетных вершин графа G есть четное число.

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

Задачи и упражнения

  • 1. Докажите, что число перекрестков любого города, в которых встречается нечетное число улиц - четно.
  • 2. У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось. Докажите, что количество марсиан с нечетным числом рук четно.
  • 3. Докажите, что число зрителей, пришедших на стадион смотреть футбольный матч и имеющих нечетное число знакомых (среди того же множества зрителей) четно.
  • 4. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
  • 5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 5 друзей каждый, 11 - по 4 друга и 10 - по 3 друга?
  • 6. В офисе 15 телефонов. Можно ли их соединить между собой проводами так, чтобы каждый был соединен с 3 другими?
  • 7. Можно ли нарисовать на плоскости 11 отрезков так, чтобы каждый пересекался ровно с тремя другими?
  • 8. В государстве 100 городов, и из каждого из них выходит по 4 дороги. Сколько всего дорог в государстве?
  • 9. Может ли в государстве, в котором из каждого города выходит ровно по три дороги, быть 100 дорог?
  • 10. На радиостанции каждый радиоузел соединен ровно с 15 другими. Может ли быть число проводов на радиостанции равно 200?

Ответы и пояснения

Во всех задачах нужно смоделировать условия при помощи графов. Задачи 1-7 решаются при помощи теоремы 1, а при решении задач 8-10 нужно использовать следствие из этой теоремы.

Доказательство утверждений в задачах 1—4 дословно повторяет доказательство теоремы 1.

В задачах 5-7 ответ отрицательный, так как ситуации, соответствующие условиям каждой из этих задач, противоречат теореме 1.

  • 7. Нужно рассмотреть граф, вершины которого соответствуют отрезкам, а ребра соединяют вершины, которым соответствуют пересекающиеся отрезки.
  • 8. Рассмотрим граф G(V, Е), у которого множество вершин V состоит из 100 городов, а множество ребер Е состоит из всех дорог государства. По условию задачи каждая вершина этого графа имеет степень 4. Применяя формулу (1.4.1), получим, что 4100 = 2-|?|.

Следовательно, количество дорог |?| равно 200.

9. Моделируя условие задачи так же, как в задаче 8, и применяя следствие из теоремы 1, получим: 3-|f| = 2• 100. Так как количество вершин |f| должно

быть натуральным числом, то ответ на вопрос задачи - отрицательный.

10. Ответ к задаче - отрицательный. Ее решение аналогично решению задачи 9.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы