格子グラフ

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

通常、グラフ理論のより抽象的な意味でのグラフと、空間（多くの場合、平面または 3D 空間）でのグラフの描画との間には明確な区別はありません。このタイプのグラフは、より簡潔に、単に格子、メッシュ、またはグリッドと呼ばれることもあります。さらに、これらの用語は、「8 × 8 の正方形グリッド」のように、無限グラフの有限セクションを指す場合にもよく使用されます。

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

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

正方格子グラフはグラフの直積、すなわちn  − 1 とm  − 1 の辺を持つ2つのパスグラフの直積である。 ^[2]パスグラフはメディアングラフなので、後者の事実は正方格子グラフもメディアングラフであることを意味する。すべての正方格子グラフは二部グラフであり、これは頂点を市松模様のように色付けできることから簡単に検証できる。

パスグラフはグリッド上のグリッドグラフです。グリッドグラフは4サイクルです。^[2]${\displaystyle 1\times n}$${\displaystyle 2\times 2}$

任意の平面グラフ Hはh  ×  hグリッドのマイナーグラフであり、ここで である。^[3]${\displaystyle h=2|V(H)|+4|E(H)|}$

グリッドグラフは、グリッド排他定理によりグラフマイナー理論における基本的なオブジェクトであり、二次元性理論において重要な役割を果たします。

三角グリッドグラフは、三角グリッドに対応するグラフです。

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

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

• ラティスパス
• ピックの定理
• 2D格子内の整数三角形
• 通常のグラフ