Некоторые виды графов

Определение.Графтакой, что любые две его вершины смежны, называется полным графом. Полный граф с р вершинами обозначается . На рис. 6 показаны графы .

Рис. 6

Степень каждой вершины графа К_р равна . Следовательно, число ребер графа К_р равно.

Определение.Графназывается регулярным степени k, если все его вершины имеют одну и туже степень k. На рис. 7 приведены примеры регулярных графов степени 3. Всякий полный граф К_р – это регулярный граф степени .

 

 

Рис.7

Определение. Граф с пустым множеством ребер называется вполне несвязным графом. Вполне несвязный граф с р вершинами будем обозначать через N_p. Граф N₁, состоящий из единственной вершины, называется тривиальным графом.