グラフ理論の基礎フラッシュカード

Question 1

グラフ $G=(V,E)$ とは何ですか？

Accepted Answer

グラフとは、順序対 $G=(V,E)$ のことで、$V$ は頂点（ノード）の集合、$E$ は辺の集合であり、各辺は2つの頂点を結びます（無向グラフでは、辺は順序を持たない対 $\{u,v\}$ です）。

Question 2

ウォーク、パス（道）、サイクル（閉路）の違いは何ですか？

Accepted Answer

ウォークは頂点/辺の重複を許します。パス（道）は頂点を重複しないウォークです。サイクル（閉路）は閉じたパス（開始=終了）で、最初/最後以外は頂点を重複しません。

Question 3

グラフが平面グラフであるとはどういう意味ですか？また、連結な平面グラフに対するオイラーの公式は何ですか？

Accepted Answer

平面グラフとは、平面上で辺が交差しない（頂点で交わる場合を除く）ように描けることを意味します。連結な平面埋め込みでは、$$V-E+F=2,$$ ただし $F$ は面の数（外側の面を含む）です。

AIで数学をマスター