非対称グラフ

数学の一分野であるグラフ理論では、無向グラフが非自明な対称性を持たない場合、その無向グラフは非対称グラフと呼ばれます。

正式には、グラフの自己同型とは 、任意の 2 つの頂点 u と v が隣接するのは、p ( u ) と p ( v ) が隣接する場合のみであるという性質を持つ、グラフの頂点の順列pです。グラフの恒等写像は常に自己同型 であり、グラフの自明な自己同型と呼ばれます 。非対称グラフは、他の自己同型が存在しないグラフです。

「非対称グラフ」という用語は「対称グラフ」という用語の否定ではないことに注意してください。後者は、非自明な対称性を持つことよりも強い条件を指します。

最小の非対称非自明グラフは6頂点を持つ。^[1]最小の非対称正則グラフは10頂点を持つ。4正則と5正則の10頂点非対称グラフも存在する。^{[2] [3]}最小の5つの非対称立方グラフ^[4]の1つは、 1939年に発見された12頂点のフルヒトグラフである。 ^[5]フルヒトの定理の強化版によれば、非対称立方グラフは無限に存在する。

非対称グラフのクラスは補グラフに関して閉じている。つまり、グラフGが非対称なのは、その補グラフが非対称な場合のみである。^[1] n頂点の非対称グラフは、最大でn /2 + o( n ) 個の辺を追加または削除することで対称にすることができる。^[1]

n頂点のグラフのうち、非自明な自己同型性を持つものの割合は、 n が大きくなるにつれて 0 に近づく。これは非公式には「ほぼすべての有限グラフは非対称である」と表現される。対照的に、やはり非公式には「ほぼすべての無限グラフは非自明な対称性を持つ」。より具体的には、エルデシュ・レーニイ モデルの可算無限ランダム グラフは、確率 1で、高度に対称なラド グラフと同型である。^[1]

最小の非対称木には7つの頂点があり、長さ1、2、3の3つのパスが共通の端点で結ばれています。^[6]グラフの場合とは対照的に、ほとんどすべての木は対称的です。特に、n個のラベル付きノード上のすべての木の中から一様にランダムに木を選択した場合、nが増加するにつれて確率が1に近づくにつれて、木には同じノードに隣接する2つの葉が含まれ、これら2つの葉を交換する対称性があります。^[1]

ウィキメディア・コモンズには、非対称グラフに関連するメディアがあります。