単純グラフとマルチグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)
「双対グラフ」の記事における「単純グラフとマルチグラフ」の解説
閉路グラフの双対の例から明らかなように、単純グラフの双対は単純であるとは限らず、自己ループ（両方の端点が同じ頂点にある辺）や同じ2つの頂点を結ぶ複数の辺がある場合がる。カット-サイクルの双対性の特別な場合として、平面グラフの橋はその双対グラフの自己ループと一対一に対応している。同じ理由で、双対多重グラフ内の一対の平行な辺（つまり、長さ2のサイクル）は、主グラフ内の2辺のカットセット（削除されるとグラフが切断される一対の辺）に対応する。したがって、平面グラフが単純である条件はその双対が1辺または2辺のカットセットを持たない場合に限る。つまり、3辺接続となる。単純平面グラフの双対が単純な場合、これは3辺連結単純グラフとなる。このクラスのグラフは、3頂点結合単純平面グラフを含むが、必ずしもそうではなく、たとえば、自己双対グラフを示す図は3辺接続だが（したがって、その双対は単純である）が、3頂点接続ではない。
※この「単純グラフとマルチグラフ」の解説は、「双対グラフ」の解説の一部です。
「単純グラフとマルチグラフ」を含む「双対グラフ」の記事については、「双対グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「単純グラフとマルチグラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 単純グラフとマルチグラフのページへのリンク
