格子グラフ

グラフ理論において、格子グラフ、メッシュグラフ、またはグリッドグラフとは、あるユークリッド空間に埋め込まれた描画が$\displaystyle \mathbb {R} ^{n}}$⁠、正則なタイル張りを形成する。これは、グラフをそれ自身に写像する全単射変換の群が群論的な意味での格子であることを意味する。

通常、グラフ理論におけるより抽象的な意味でのグラフと、空間（多くの場合、平面または3次元空間）におけるその描画との間に明確な区別は設けられません。この種のグラフは、より簡潔に格子、メッシュ、またはグリッドと呼ばれることがあります。さらに、これらの用語は、「8×8の正方形グリッド」のように、無限グラフの有限部分を表す場合にもよく用いられます。

格子グラフという用語は、文献では、完全グラフの直積など、規則的な構造を持つ他のさまざまな種類のグラフにも用いられています。^{[ 1 ]}

格子グラフ（グリッドグラフや正方形グリッドグラフなど、さまざまな名前で知られています）の一般的なタイプは、頂点が平面上の整数座標を持つ点に対応するグラフです。x座標は1, ..., n、y座標は1, ..., mの範囲にあり、対応する点間の距離が1の場合に2つの頂点が辺で接続されます。言い換えれば、軸に平行な辺を持つ長方形内の整数点の単位距離グラフです。 ^{[ 2 ]}

三角形格子グラフとは、三角形格子に対応するグラフのことである。

平面上の有限個の点の集合に対するハナン格子グラフは、その集合の各点を通るすべての垂直線と水平線の交点によって得られる格子によって生成される。

ルークのグラフ（チェス盤上のルークの駒のすべての合法的な動きを表すグラフ）は、格子グラフとも呼ばれますが、このグラフは、1つの行または列のすべての点が隣接しているため、ここで説明する格子グラフとは異なります。妖精の駒であるワジールの有効な動きは、正方形の格子グラフを形成します。

• 格子経路
• ピックの定理
• 2次元格子における整数三角形
• 通常のグラフ