組合せの性質
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:55 UTC 版)
ヒーウッドグラフは立方体であり、それに含まれるすべての閉路には六つ以上の辺がある。これよりも小さいすべての立方体グラフにはより短い閉路しか含まれないため、ヒーウッドグラフは 6-ケージの、内周 6 の最小の立方体グラフである。また、距離推移グラフ（フォスター調査を参照）でもあり、したがって距離正則（英語版）である。 ヒーウッドグラフには 24 の完全マッチングが存在する;各マッチングに対し、それに含まれない辺の集合はハミルトン閉路を形成する。例えば、ページ右上の図は、マッチングを形成する閉路からなる内部対角（internal diagonal）を備える閉路上の頂点を示しているグラフである。その閉路を二つのマッチングに分けることで、ヒーウッドグラフを三つの完全マッチング（すなわち、3辺彩色）に分ける方法が八通りある。どの二つの完全マッチングと、どの二つのハミルトン閉路も、グラフの対称性によってお互い交換することが出来る。 ヒーウッドグラフには 6-頂点の閉路が 28 含まれる。そのような 6-閉路は、必ず三つの他の 6-閉路と互いに素になっている;そのような三つの 6-閉路において、どの一つも必ず他の二つの対称差（symmetric difference）になっている。6-閉路に対して一つの頂点と、6-閉路の互いに素な各ペアに対して一つの辺を備えるグラフは、コクセターグラフ（英語版）である。
※この「組合せの性質」の解説は、「ヒーウッドグラフ」の解説の一部です。
「組合せの性質」を含む「ヒーウッドグラフ」の記事については、「ヒーウッドグラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「組合せの性質」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 組合せの性質のページへのリンク
