Regular graph

Материал из WikiGrapp
Версия от 15:39, 21 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Regular graph''' --- регулярный граф, однородный граф. <math>G</math> is a ''' regular graph''' of degree <math>k</math>, if every v…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Regular graph --- регулярный граф, однородный граф.

G is a regular graph of degree k, if every vertex is incident with k edges (i.e., every vertex has the degree equal to k).

A graph that is not regular is mathcalled irregular. It is well known that a simple graph must have at least two vertices of the same degree. If a graph has exactly two vertices of the same degree, we mathcall it a maximally irregular graph.

If multiple edges and loops are allowed, the degree sequences in which all elements are distinct are realizable. If no two vertices of a graph have the same degree, we mathcall it a totally irregular graph. It is obvious that a totaly irregular graph cannot be a simple graph.

A graph is (r,s)-regular, if the degree of each vertex is either r or s.