この用語はまだ監査を通っていません（未確認）。
平面グラフ
へいめんぐらふ ／ 平面的グラフ 1対1で対応planar graph
名詞 ・書き言葉・答案
式と読み方
v minus e plus f equals two
定義
辺どうしが交わらないように平面上にかくことのできるグラフのこと。交差してかかれていても、かき直して交差をなくせれば平面グラフである。
A graph that can be drawn in the plane so that no two edges cross. A drawing with crossings does not rule it out, as long as some other drawing has none.
例文
話し言葉 It looks like these edges cross, but you can redraw it with no crossings at all, so it's a planar graph. 辺が交差しているように見えるけれど、交差がないようにかき直せるから、これは平面グラフだ。
書き言葉・答案 Explain why K₅, the complete graph on 5 vertices, is not a planar graph. 5 頂点の完全グラフ K₅ が平面グラフでない理由を説明せよ。
言い間違えやすいところ
- 日本語の本によっては、交差なくかけるグラフを「平面的グラフ」、交差なくかいた図そのものを「平面グラフ」と呼び分ける。英語では前者が planar graph、後者が plane graph。
- 連結な平面グラフでは v − e + f = 2（頂点・辺・面の数。外側の領域も 1 つの面と数える）が成り立つ。K₅ と K₃,₃ は平面グラフでない。
- 用例コーパスでは書き言葉はすべて MIT の講義ノートで、話し言葉には出てこない。Levin の本では 53 件（2.3 Planar Graphs 43 ほか）。