最小の頂点次数との関係
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/24 09:59 UTC 版)
「k-辺連結グラフ」の記事における「最小の頂点次数との関係」の解説
最小の頂点次数は、辺連結度の自明な上界である。すなわち、グラフ G = (E,V) が k-辺連結であるなら、必ず k ≤ δ(G) が成り立つ。但し、δ(G) は任意の頂点 v ∈ V の中での最小の次数を表す。明らかに、ある頂点 v に接続するすべての辺を取り除けば、v はそのグラフから離れて非連結となるであろう。
※この「最小の頂点次数との関係」の解説は、「k-辺連結グラフ」の解説の一部です。
「最小の頂点次数との関係」を含む「k-辺連結グラフ」の記事については、「k-辺連結グラフ」の概要を参照ください。
- 最小の頂点次数との関係のページへのリンク