Специальные графы

Граф называется r‑валентным или r‑однородным, если любая его вершина имеет степень, равную r.

Например, цикл является 2-валентным графом. На рисунке 32 (а) изображен 3-валентный граф Петерсона, графы Платоновых тел: (б)–куба, (в)‑тетраэдра, (г)–додекаэдра, (д)–4-валентный граф октаэдра и (е)–5-валентный граф икосаэдра.

Л юбой полный граф К_n, где n – число вершин, является (n‑1)‑регулярным.

Граф G=(V, E) называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V₁ и V₂, что каждое ребро графа имеет одну концевую вершину в V₁, а вторую в V₂. См. рис.33 слева. При этом не обязательно, чтобы каждая пара вершин из V₁ и V₂ была соединена ребром. Если же это так, то граф называется полным двудольным графом и обозначается обычно K_m,n, где m и n – число вершин в V₁ и V₂ соответственно. См. рис.33 справа.

В полном двудольном графе число вершин равно m+n, а число ребер mn. Полный двудольный граф вида K_1,n называется звездным.

Граф G=(V, E) называется k‑дольным, если множество его вершин V можно разбить на k попарно непересекающихся подмножеств V₁, V₂,, V_k, что любое ребро имеет одну концевую вершину в V_i, а вторую в V_j, где ij. Полным k‑дольным графом называется такой k‑дольный граф, что любая вершина V_i смежна с любой вершиной из V_j, где ij и i, j=1,2,,k.

Объединение звездного графа K_1,n‑1 и цикла C_n‑1 называется колесом и обозначается W_n.