Loading article…
| ティーツェのグラフ | |
|---|---|
 ティーツェグラフ | |
| 頂点 | 12 |
| エッジ | 18 |
| 半径 | 3 |
| 直径 | 3 |
| 周囲 | 3 |
| 自己同型写像 | 12 ( D 6 ) |
| 彩色数 | 3 |
| 色度指数 | 4 |
| 物件 | キュービック・スナーク |
| グラフとパラメータの表 | |
グラフ理論の数学分野において、ティーツェのグラフは、 12個の頂点と18個の辺を持つ無向立方グラフです。これは、1910年にメビウスの帯が互いに接する6つの領域（帯の境界に沿った3つと中心線に沿った3つ）に分割できることを示し、したがってメビウスの帯に埋め込まれるグラフには6色が必要になる可能性があることを示したハインリヒ・フランツ・フリードリヒ・ティーツェにちなんで名付けられました。[ 1 ]ティーツェの分割領域の境界セグメント（メビウスの帯自体の境界に沿ったセグメントを含む）は、ティーツェのグラフの埋め込みを形成します。
ティーツェのグラフは、ピーターセンのグラフの頂点の 1 つを三角形に置き換えることによって形成できます。 [ 2 ] [ 3 ] ティーツェのグラフと同様に、ピーターセンのグラフは互いに接する 6 つの領域の境界を形成しますが、メビウスの帯上ではなく射影平面上にあります。射影平面のこの分割から、単一の頂点を囲む穴を切り取ると、囲まれた頂点は穴の周りの領域境界の三角形に置き換えられ、前述のティーツェのグラフの構成が得られます。
ティーツェのグラフとピーターセンのグラフはどちらも最大非ハミルトングラフです。ハミルトン閉路はありませんが、隣接していない任意の2つの頂点はハミルトン路で接続できます。[ 2 ]ティーツェのグラフとピーターセンのグラフは、頂点数が12以下の2頂点連結の3次非ハミルトングラフです。[ 4 ]
ピーターセングラフとは異なり、ティーツェのグラフは準ハミルトングラフではない。3つの三角形の頂点のうち1つを取り除くと、より小さなグラフが形成されるが、それでも非ハミルトングラフのままである。
ティーツェのグラフの辺彩色には4色が必要です。つまり、彩色指数は4です。言い換えれば、ティーツェのグラフの辺は4つのマッチングに分割できますが、それより少ないマッチングには分割できません。
ティーツェのグラフは、スナークの定義の一部に合致する。すなわち、3辺彩色できない3次ブリッジレスグラフである。しかし、ほとんどの著者はスナークを3サイクルを持たないグラフに限定しているため、ティーツェのグラフは一般的にスナークとはみなされていない。それにもかかわらず、ティーツェのグラフは、 1975年にR.アイザックスによって導入された無限族のフラワースナークの一部であるグラフJ3と同型である。 [ 5 ]
ピーターセングラフとは異なり、ティーツェグラフは4つの完全マッチングで覆うことができる。この性質は、グラフが4つの完全マッチングで覆えるかどうかをテストすることがNP完全であることを証明する際に重要な役割を果たす。[ 6 ]
ティーツェのグラフは、彩色数3、彩色指数4、周長3、直径3です。独立数は5です。その自己同型群の位数は12で、正六角形の対称群（回転と鏡映の両方を含む）である二面体群D6と同型です。この群は頂点上にサイズ3の軌道が2つとサイズ6の軌道が1つあるため、このグラフは頂点推移的ではありません。
