Степени неориентированных графов

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

Пусть G(X) – неориентированный граф. Степенью m(х) графа G(X) в вершине х называется число ребер, инцидентных вершине х. Если все числа m(х) для х Î X конечны, то граф называется ло­кально конечным. Петли можно считать одинарным или двойным ребром в зависимости от конкретной задачи.

Обозначим m(х_i, x_j) = m(x_j, х_i) – число ребер, соеди­няющих вершины х_i и x_j. Если в графе G(X) нет кратных ребер, то m(х_i, x_j) = 0 или m(х_i, x_j) = l.

Очевидно, что

m(х_i) =

Поскольку каждое ребро учитывается в двух вершинах х_i и x_j, то общее число ребер m графа G(X):

. (7)

Это выражение справедливо и для графов с петлями, если пет­лю считать двойным ребром.

Так как – четное число, то можно сделать вывод о том, что в конечном графе число вершин с нечетной степе­нью четно. Это следует из того, что если из суммы вычесть все слагаемые, соответствующие вершинам с четной степенью, она останется чет­ной.

Граф, степени всех вершин в котором равны, называется одно­родным, т.е. m(x_i) = m_n " x_i Î X.

Конечные однородные графы могут быть представлены в виде правильных многогранников: тетраэдра, куба, октаэдра, додекаэдра, икосаэдра и т.д. Примеры бесконечных одно­родных графов изображены на рис. 3.27.

Из (7) следует, что в однородном графе степени m_n, число ребер равно где n - число вершин.

Рис. 3.27. Бесконечные однородные графы