グラフィティ（プログラム）

Graffitiは、数学、特にグラフ理論[ 1 ]と化学における予想を立てるコンピュータプログラムですが、他の分野にも応用可能です。1984年から1985年にかけてヒューストン大学のSiemion Fajtlowiczによって開発され、後にErmelinda DeLaViñaも貢献しました。Graffitiによって生成された予想に関する研究は、約80本の論文[ 2 ]にまとめられており、Paul Erdős、Béla Bollobás、Fan Chung、László Lovászといった数学者による貢献も受けています。[ 3 ]

歴史

Graffitiは、1980年代初頭にFajtlowiczと大学院生Shui-Tain Chenによって開発された「Little Paul」と呼ばれる以前のプログラムから発展したものです。[ 3 ]このプログラムは1986年のSoutheastern Combinatorics and Graph Theory Conferenceで初めて公開され、最初の18個の予想が発表されました。当初はPascalで書かれていましたが、ヒューストン大学のDECステーションで動作し、1990年にVMS/VAXシステム、 1995年にUnixに移行しました。[ 3 ]

2001年にDeLaViñaによって開発されたGraffiti.pcは、学部教育に重点を置いたPCプラットフォーム向けにプログラムを適応させました。[ 4 ] 2017年にRandy Davilaによって作成されたTxGraffitiは、機械学習を統合したPythonで書かれた最新の後継プログラムです。[ 5 ]

方法論

Graffitiは、グラフのデータベースを維持し、それぞれのグラフの数値特性（不変量）を計算することで動作します。このプログラムは、不変量間の関係（独立数や彩色数など）を表す候補仮説を生成し、データベース内のすべてのグラフに当てはまる候補仮説を保持します。[ 3 ]

重要な革新は、1990年代にファジトロヴィッチによって導入された「ダルメシアン・ヒューリスティック」であり、これは真実だけでなく情報量や重要性に基づいて推測をフィルタリングするものである。[ 6 ]推測は、既存の推測よりも少なくとも1つのグラフに対してより鋭い境界を提供する場合にのみ保持され、研究者が「魔法使いの弟子問題」と呼ぶ、真実だが些細な陳述に圧倒される問題を解決している。

注目すべき推測

グラフィティの最も引用されている成果の一つは、剰余独立数予想である。これは、任意のグラフGに対して、剰余R ( G ) は最大でも独立数α( G ) であるというものである。[ 7 ]これは 1991 年にファヴァロン、マヘオ、サクレによって証明された。[ 8 ]その他の注目すべき成果としては、1988 年にファン・チュンによって証明された平均距離の限界がある。[ 9 ]

グラフィティ予想のマスターコレクションである「Written on the Wall」文書には、数百の番号付き予想が含まれています。グラフ理論以外にも、このプログラムは数理化学にも貢献し、フラーレンやベンゼノイド分子に関する予想を生み出しました。[ 3 ]

参考文献

  1. ^コラタ、ジーナ（1989年6月18日）「数学者とコンピュータ化されたアイデアの出会い」ニューヨーク・タイムズ。
  2. ^コルトン、サイモン（2001年1月26日）「その数字を見てください」タイムズ・ハイアー・エデュケーション。
  3. ^ a b c d e DeLaViña、Ermelinda (2003 年 1 月)、グラフィティの発展の歴史(PDF)、ヒューストン大学ダウンタウン校。
  4. ^ DeLaViña、Ermelinda、Graffiti.pc: A Variant of Graffiti (PDF)、ヒューストン大学ダウンタウン校。
  5. ^ Davila, Randy (2024). 「TxGraffitiを用いた数学における自動推測」. arXiv : 2409.19379 [ math.CO ].。
  6. ^ Larson, CE; Van Cleemput, N. (2016-02-01). 「自動推測 I：Fajtlowicz の Dalmatian heuristic の再考」 .人工知能. 231 : 17–38 . doi : 10.1016/j.artint.2015.10.002 . ISSN 0004-3702 . 
  7. ^ Caro, Yair; Davila, Randy; Henning, Michael; Pepper, Ryan (2021-04-02). 「TxGraffitiの予想：独立性、支配性、そしてマッチング」. arXiv : 2104.01092 [ math.CO ].
  8. ^ Favaron, O.; Mahéo, M.; Saclé, J.-F. (1991-01-02). 「グラフの剰余について」 . Journal of Graph Theory . 15 (1): 39– 64. doi : 10.1002/jgt.3190150107 . ISSN 0364-9024 . 
  9. ^ 「グラフィティの推測について」cms.dt.uh.edu . 2025年12月10日閲覧。
スタブアイコン

数学ソフトウェアに関するこの記事はスタブです。不足している情報を追加してWikipediaに貢献してください。

スタブアイコン

化学ソフトウェアに関するこの記事はスタブです。不足している情報を追加してWikipediaに貢献してください。

「 https://en.wikipedia.org/w/index.php?title=Graffiti_(program)&oldid=1336129070」より取得