平面グラフのソースを表示

'''平面グラフ''' (plane graph) は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなる[[グラフ理論|グラフ]]のことである。平面グラフと[[同型グラフ|同型]]なグラフのことを'''平面的グラフ''' (planar graph) という。

平面的グラフは、球面などの[[種数]]0の曲面に描けるグラフと同値である。

極小な非平面的グラフは、[[2部グラフ|K<sub>3,3</sub>]]と[[完全グラフ|K<sub>5</sub>]]。

==性質==
*Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3。
*Gが単純グラフで平面的グラフならば、Gは、[[次数 (グラフ理論)|次数]]が5以下の頂点を持つ。
*種数gの曲面S上に描かれた連結グラフGが、Sをf個の領域に分割しているとする。このとき、|V(G)|-|E(G)|+f=2-2gが成り立つ。（'''オイラーの公式'''）
*グラフが非平面的であるのは、K<sub>3,3</sub>またはK<sub>5</sub>をマイナーとして含むとき、かつそのときに限る。（'''ワグナーの定理'''）
*平面的グラフの部分グラフは総て平面的グラフである。

[[category:グラフ理論|へいめんくらふ]]
[[Category:数学に関する記事|へいめんくらふ]]

<!--[[zh:平面圖]]-->