double arrow

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


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

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


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

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

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

Граф G=(V, E) называется k‑дольным, если множество его вершин V можно разбить на k попарно непересекающихся подмножеств V1, V2,¼, Vk, что любое ребро имеет одну концевую вершину в Vi, а вторую в Vj, где i¹j. Полным kдольным графом называется такой k‑дольный граф, что любая вершина Vi смежна с любой вершиной из Vj, где i¹j и i, j=1,2,¼,k.




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







Сейчас читают про: