グラフ理論において、ハリスグラフはオイラーグラフ、タフグラフ、非ハミルトングラフとして定義されます。[1] [2]ハリスグラフは2013年にミシガン大学のハリス・スパンゲンが、タフかつオイラーグラフであるグラフは十分にハミルトングラフであると予想したことで導入されました。しかし、ダグラス・ショーはこの予想を反証し、位数9、サイズ14の反例を発見しました。 [1]現在、241,375個のハリスグラフが知られています。[2] [3]最小のハリスグラフであるヒロタカグラフは、位数7、サイズ12です。[1] [2]
ハリスグラフは、フジツボを追加したり、小さなハリスグラフを接ぎ木したりすることで構築でき、グラフの特性を維持しながらより大きなグラフを作成できます。注目すべきグラフの種類には、最小のヒロタカグラフ、フジツボのないロペスグラフ、ショーグラフなどがあり、それぞれがグラフ理論における独自の構造的特徴を示しています。ハリスグラフは、その発見と検証のための分かりやすい方法のため、グラフ理論の教育に役立ちます。バランスの取れた課題を提供し、生徒が協力して解決策を探求する中で、創造性、チームワーク、そして問題解決能力を育みます。
歴史
2013年にハリス・スパンゲンが予想を唱えた後、[4]ダグ・ショーはすぐに反例となるハリスグラフを発見しました。ジェイナ・フィッシュマンとエリザベス・ペトリーは同年にさらに2つのハリスグラフを発見しました。その後数年間でさらに3つのハリスグラフが発見され、2018年に米田宏高が極小ハリスグラフと考えられるグラフを発見しました。[1]
2023年には、シュブラ・ミシュラとマルコ・トロパーによって書かれたコードによって、ヒロタカグラフが一意であることが証明されました。[2] n頂点のハリスグラフの数もOEISシーケンスになりました。[3]
工事
ハリスグラフの開花
k-フジツボは、パス上のすべてのノードの次数が 2 である2つのノード間の長さが k のパスです。 フラワーリングは、2 つの奇数次ノード間の最短パス上の 2 つのノード間に 2-フジツボを追加するプロセスです。
奇数次数のノードが偶数個ある、非ハミルトン的でタフなグラフをフラワーリングすると、ハリスグラフが生成されます。 [2]グラフに2-フジツボを追加すると、そのタフさは維持されますが、ハミルトン的であることはより困難になります。さらに、グラフは奇数次数の頂点を奇数個持つことはできないため、フラワーリングのプロセスによって、非ハミルトン的でタフなグラフをオイラーグラフに変換することもできます。
2つのハリスグラフを1つに接ぎ木する
5輪グラフは、あるハリスグラフの1つの辺と別のハリスグラフの別の辺の間に追加され、それぞれの5輪グラフから、元のグラフには接続されていなかった2つのノードが相互に接続される。接続と5輪グラフを追加しても、グラフがハミルトングラフ、非オイラーグラフ、またはタフグラフではないグラフになることはない（これらの条件が既に満たされている場合）。そのため、結果は1つのハリスグラフとなる。[2]
エッジをフジツボに置き換える
既存のハリスグラフの辺を2-フジツボに置き換えると、ハリスグラフが作成されます。これは、以前の次数がすべて保持されるためです。一方、フジツボは定義上次数が2であるため、グラフは依然としてオイラーグラフです。グラフがハミルトングラフになることはさらに困難になり、グラフの頑強性は変わらないため、どこにでもフジツボを追加しても、グラフはオイラーグラフ、頑強グラフ、非ハミルトングラフのままです。[2]
種類
ヒロタカグラフは、7次元でサイズが12であり、最小の位数を持つハリスグラフである。[1] [2]このグラフが初めて登場したのは、非ハミルトングラフでタフなグラフの例としてであった。[5]ダグラス・ショーは、位数6以下のすべてのオイラーグラフがハミルトングラフでタフではないことを示して、このグラフが最小であることを証明した。シュブラ・ミシュラとマルコ・トロパーによって書かれたJavaコードは、このグラフが唯一であることを証明した。 [2]
最初に発見されたハリスグラフは、次数9、サイズ14のショーグラフでした。[1] [2] [4]このグラフは、2013年のハリス・スパンゲンの予想に対する反例として機能しました。
最小のフジツボフリーハリスグラフ、またはロペスグラフは、次数13、サイズ33です。これは、フジツボフリーハリスグラフは存在しないという仮説を解決するために構築されました。 [2]
アプリケーション
ハリスグラフは、理解しやすい特性と、その発見・検証方法を備えているため、グラフ理論の教育において特に有用です。[1] [2]ハリスグラフは、難易度とアクセスしやすさの理想的なバランスを実現しており、様々なレベルの学生にとって魅力的な問題となっています。[4]
ハリスグラフを用いることで、生徒は様々な概念や解決策を試すようになり、創造性と数学的思考力が育まれます。このプロセスは、生徒同士が協力して潜在的な解決策を検証する中で、学習意欲を高め、チームワークと集団的な問題解決能力を高めます。[4]
参考文献
- ^ abcdefg Mishra, Shubhra. 「Harris Graph Repository」. sites.google.com . 2024年7月5日閲覧。
- ^ abcdefghijkl ガンディーニ、フランチェスカ;ミシュラ、シュブラ。ショー、ダグラス（2023年12月18日）。 「ハリス・グラフスの家族」。arXiv : 2312.10936 [math.CO]。
- ^ ab Sloane, N. J. A. (編). 「数列A366315 (n頂点のハリスグラフの数)」.オンライン整数数列百科事典. OEIS財団.
- ^ abcd Shaw, Douglas (2018年11月16日). 「ハリスグラフ—学生と教員のためのグラフ理論アクティビティ」 . The College Mathematics Journal . 49 (5): 323– 326. doi :10.1080/07468342.2018.1507382 – tandfonline経由.
- ^ Chvátal, V. (1973年7月1日). 「タフグラフとハミルトン回路」 .離散数学. 5 (3): 215– 228. doi :10.1016/0012-365X(73)90138-6. ISSN 0012-365X.
