周期グラフ（幾何学）

ユークリッドグラフ（あるユークリッド空間に埋め込まれたグラフ）は、そのユークリッド空間の基底が存在し、その基底の対応する平行移動がそのグラフの対称性を誘導する（つまり、ユークリッド空間に埋め込まれたグラフにそのような平行移動を適用してもグラフは変化しない）場合、周期的である。同様に、周期ユークリッドグラフは、有限グラフ上のアーベル被覆グラフの周期的実現である。^[1]^[2] ユークリッドグラフは、任意の2つの頂点間の距離が最小である場合、一様離散的である。周期グラフは、空間のモザイク化（またはハニカム）やその対称群の幾何学、したがって幾何学的群論、ならびに離散幾何学や多面体理論、および同様の分野と密接に関連している。

周期グラフに関する研究の多くは、自然科学や工学への応用、特に3次元結晶ネットの結晶工学、結晶予測（設計）、結晶挙動のモデリングに向けられています。周期グラフは、超大規模集積回路（VLSI）回路のモデリングでも研究されてきました。^[3]

基本的な処方

ユークリッドグラフは ( V、 E )のペアで、Vは点の集合 (頂点またはノードと呼ばれることもある)、Eは辺の集合 (結合と呼ばれることもある) であり、各辺は 2 つの頂点を結合する。 2 つの頂点uとv を接続する辺は通常、集合{ u、v } として解釈されるが、辺はu と v を接続する線分として解釈されることもあり、その結果の構造はCW 複合体となる。多面体および化学の文献では、幾何学的グラフをネット(多面体ネットとは対照的) と呼ぶ傾向があり、化学の文献での命名法はグラフ理論の命名法と異なる。^[4] 文献のほとんどは、 e > 0が存在し、任意の2 つの異なる頂点間の距離が | u – v | > eである点で一様離散的な周期グラフに焦点を当てている。

数学的な観点から見ると、ユークリッド周期グラフは有限グラフ上の無限倍アーベル被覆グラフの実現です。

周期性の獲得

結晶学的空間群の同定と分類には19世紀の大部分が費やされ、リストの完全性の確認はエフグラフ・フェドロフとアーサー・シェーンフリースの定理によって完了しました。^{[5]この問題は}ダヴィド・ヒルベルトの第18の問題で一般化され、フェドロフ・シェーンフリースの定理はルートヴィヒ・ビーバーバッハによって高次元に一般化されました。^[6]

フェドロフ・シェーンフライスの定理は、次のことを主張します。3次元空間に次の条件を満たすユークリッドグラフが与えられているとします。

これは一様離散的であり、 e > 0が存在し、任意の 2 つの異なる頂点間の距離が | u – v | > eであることを意味します。
3 次元空間内の任意の平面に対して、平面の両側にグラフの頂点が存在するという意味で、空間を埋めます。
各頂点は有限の次数または価数を持ちます。
幾何学的グラフの対称群の下には頂点の軌道が有限個存在します。

すると、ユークリッドグラフは、その対称群内の並進ベクトルが基礎となるユークリッド空間に広がるという点で周期的であり、その対称群は結晶学的空間群です。

科学と工学における解釈は、空間に広がる物質を表すユークリッドグラフは条件(1)、(2)、(3)を満たさなければならないため、準結晶からガラスまでの非結晶物質は条件(4)に違反しなければならないというものである。しかし、過去四半世紀の間に、準結晶は結晶と十分に多くの化学的および物理的特性を共有していることが認識され、準結晶を「結晶」として分類し、「結晶」の定義をそれに応じて調整する傾向がある。^[7]

数学と計算

周期グラフの理論的研究の多くは、周期グラフの生成と分類の問題に焦点を当ててきました。

分類の問題

分類問題に関する研究のほとんどは 3 次元、特に結晶ネット、すなわち結晶内の原子または分子オブジェクトの配置の説明または設計として使用できる周期グラフの分類に焦点を当ててきました。結合はエッジで示されます。より一般的な分類基準の 1 つはグラフ同型性です。結晶同型性と混同しないでください。2 つの周期グラフは、必ずしもホモトピックである必要はありませんが、同型である場合に位相的に同等であると言われることがよくあります。グラフ同型性問題は結晶ネットの位相的同値性に多項式時間で還元可能ですが(位相的同値は、多項式時間で計算できないという意味で「計算上扱いにくい」候補になります)、結晶ネットは、位相的に同等なネットが知られていない場合に限り、一般に新しいものと見なされます。これにより、位相的不変量に注目が集まっています。

不変量の 1 つは、一般的な頂点の周りに配列され、シュレーフリ記号で表される最小サイクルの配列(化学の文献ではリングと呼ばれることが多い) です。結晶ネットのサイクルは、別の不変量である調整シーケンス(またはトポロジーのシェルマップ^{[9] ) と関連しています}^[8 ] 。調整シーケンスは次のように定義されます。まず、グラフ内の頂点vからの距離シーケンスはシーケンスn ₁、n ₂、n ₃、... です。ここで、n _{i は}vから距離iにある頂点の数です。調整シーケンスはシーケンスs ₁、s ₂、s ₃、... です。ここで、s _{i は}結晶ネット (の軌道) の頂点の距離シーケンスのi番目のエントリの加重平均であり、重みは各軌道の頂点の漸近比です。配位系列の累積和は位相密度と表され、最初の10項の合計（0番目の項には1を加えたもの）（TD10と表記されることが多い）は、クリスタルネットデータベースの標準的な検索用語である。単純ランダムウォークの大偏差特性と密接に関連する位相密度の数学的側面については、 ^[10]^{[11]を参照のこと。}

もう 1 つの不変量は、テッセレーションとユークリッドグラフの関係から生じます。テッセレーションを (多面体の場合もある) ソリッド領域、(多角形の場合もある) 面、(直線の場合もある) 曲線、および頂点の集合、つまりCW 複合体と見なすと、曲線と頂点はテッセレーションのユークリッドグラフ (または1 スケルトン) を形成します。(さらに、タイルの隣接グラフは別のユークリッドグラフを誘導します。) テッセレーションに有限個のプロトタイプがあり、テッセレーションが周期的である場合、結果として得られるユークリッドグラフも周期的になります。逆方向に進んで、1次元スケルトンが与えられた周期グラフ（位相的に同等）であるタイル分割のプロトタイプには別の不変量があり、この不変量はコンピュータプログラムTOPOSによって計算されます。^[12]

周期グラフの生成

周期グラフ列挙アルゴリズムには、既存のネットを修正して新しいネットを生成するものなど、いくつか存在するが^[13]、列挙子には2つの主要なクラスがあるようだ。

現存する主要な体系的な結晶ネット列挙アルゴリズムの1 つ^{[14] は、}ボリス・ドロネーとアンドレアス・ドレスによるシュレーフリ記号の一般化によるテッセレーションの表現に基づいており、これにより、任意のテッセレーション (任意の次元) を有限構造で表現できます^{[15] 。これを}ドレス・デラニー記号と呼びます。ドレス・デラニー記号の有効な列挙子は、テッセレーションに対応する周期ネットを効果的に列挙できます。デルガド・フリードリヒスらによる 3 次元のドレス・デラニー記号列挙子は、後に合成されたいくつかの新しい結晶ネットを予測しました。^{[16]一方、}ジャイロイド、ダイヤモンド、プリミティブなどの3 重周期極小面を外科的に解剖して巻き付ける 2 次元の双曲空間の網目構造を生成する 2 次元のドレス・デラニー列挙子は、多くの新しい結晶ネットを生成しました。^[17]^[18]

現存する別の列挙器は現在、ゼオライトの妥当な結晶ネットの生成に焦点を当てています。対称群を 3 次元空間に拡張すると、3 次元空間の基本ドメイン(または領域)の特徴付けが可能になり、ネットとの交差によってサブグラフが誘導されます。このサブグラフは、一般的な位置では、頂点の各軌道から 1 つの頂点を持ちます。このサブグラフは接続されている場合とそうでない場合があり、頂点が回転軸またはネットの対称性のその他の固定点にある場合、頂点は必然的に任意の基本領域の境界上にある可能性があります。この場合、ネットは、基本領域内のサブグラフに対称群を適用することによって生成できます。^[19] 同様に、初期フラグメントのコピーを生成し、それらを周期グラフに貼り付ける他のプログラムも開発されています^[20]

参照

設計のための結晶モデルとしての周期グラフ。

参考文献

^ 砂田孝文(2012)、「トポロジカル結晶学講義」、日本数学会誌、7 :1–39、doi :10.1007/s11537-012-1144-4、S2CID 255312584
^ 砂田孝 (2012)、「離散幾何学解析に向けたトポロジカル結晶学」、応用数学科学の調査とチュートリアル、第 6 巻、Springer
^ Cohen, E. ; Megiddo, N. (1991)、「周期グラフの特性の認識」、応用幾何学と離散数学: Victor Klee Festschrift (PDF)、DIMACS 離散数学と理論計算機科学シリーズ、第 4 巻、pp. 135–146、doi :10.1090/dimacs/004/10、ISBN 9780821865934、 2010年8月15日閲覧
^ Delgado-Friedrichs, O.; O'Keeffe, M. (2005)、「グラフとしての結晶ネット：用語と定義」、Journal of Solid State Chemistry、178 (8): 2480–2485、Bibcode :2005JSSCh.178.2480D、doi :10.1016/j.jssc.2005.06.011
^ Senechal, M. (1990)、「幾何学的結晶学の簡潔な歴史」、Lima-de-Faria, J. (編)、結晶学の歴史地図、Kluwer、pp. 43–59
^ Vinberg, EB; Shvartsman, OV (1993)、「定曲率空間の運動の離散群」、Vinberg, EB (編)、幾何学 II: 定曲率空間、Springer-Verlag
^ Senechal, M. (1995)、準結晶と幾何学、ケンブリッジ大学出版、p. 27
^ Eon, JG (2004)、「ネットのトポロジカル密度：直接計算」、Acta Crystallogr. A、60（Pt 1）：7–18、Bibcode：2004AcCrA..60....7E、doi：10.1107/s0108767303022037、PMID 14691323。
^ Aste, T. (1999)、「The Shell Map」、Sadoc, JF; Rivier, N. (eds.)、THE SHELL MAP: 動的マップによる泡の構造、Foams and Emulsions、Kluwer、pp. 497–510、arXiv : cond-mat/9803183、Bibcode :1998cond.mat..3183A
^ M. Kotani およびT. Sunada「結晶格子上のランダムウォークの大偏差の幾何学的側面」『微小局所解析と複素フーリエ解析』（T. Kawai および K. Fujita 編）World Scientific、2002 年、215 ～ 237 ページ。
^ 小谷正之; 砂田剛志 (2006)、「結晶格子の大きな偏差と無限大接線円錐」、Math. Z.、254 (4): 837–870、doi :10.1007/s00209-006-0951-9、S2CID 122531716
^ Blatov, VA; Proserpio, DM, TOPOS 結晶構造のトポロジカル解析プログラムパッケージ、 2010年8月15日取得
^ Earl, DJ; Deem, MW (2006)、「仮説的ゼオライト構造のデータベースに向けて」、Ind. Eng. Chem. Res.、45 (16): 5449–5454、doi :10.1021/ie0510728、S2CID 40620797
^ デルガド・フリードリッヒス、O.ドレス、AWM;ヒューソン、DH;クリノフスキー、J. Mackay、アラバマ州 (1999 年 8 月 12 日)、「結晶ネットワークの系統的列挙」、Nature、400 (6745): 644–647、Bibcode :1999Natur.400..644D、doi :10.1038/23210、S2CID 4388277。
^ Dress, A.; Delgado Friedrichs, O.; Huson, D. (1995)、「An algorithmic approach to tilings」、Charles J.、Colbourn ; Ebadollah S.、Mahmoodian (編)、Combinatorics Advances: Papers from the Twenty-fifth Annual Iranian Mathematics Conference (AIMC25) held at Sharif University of Technology, Tehran, March 28–31, 1994、Mathematics and its Applications、vol. 329、Kluwer、pp. 111–119、doi :10.1007/978-1-4613-3554-2_7
^ Nouar, Farid; Eubank, Jarrod F.; Bousquet, Till; Wojtas, Lukasz; Zaworotko, Michael J.; Eddaoudi, Mohamed (2008)、「高多孔質金属有機構造体の設計と合成のための超分子ビルディングブロック (SBB)」、Journal of the American Chemical Society、130 (6): 1833–1835、doi :10.1021/ja710123s、PMID 18205363
^ Ramsden, SJ; Robins, V. ; Hyde, S. (2009)、「2D 双曲タイルからの 3D ユークリッドネット: 万華鏡のような例」、Acta Crystallogr. A、65 (Pt 2): 81–108、Bibcode :2009AcCrA..65...81R、doi : 10.1107/S0108767308040592、PMID 19225190。
^ EPINET: 非ユークリッドタイルにおけるユークリッドパターン、2013年1月30日閲覧
^ Treacy, MMJ; Rivin, I.; Balkovsky, E.; Randall, KH; Foster, MD (2004)、「周期的四面体フレームワークの列挙。II. 多節グラフ」(PDF)、Microporous and Mesoporous Materials、74 (1–3): 121–132、doi :10.1016/j.micromeso.2004.06.013 、 2010年8月15日閲覧。
^ LeBail, A. (2005)、「GRINSP による無機構造予測」、J. Appl. Crystallogr.、38 (2): 389–395、doi : 10.1107/S0021889805002384

さらに読む

コンウェイ、JH ; バーギエル、H.; グッドマン・ストラウス、C. (2008) 『物事の対称性』、AK ピーターズ
小谷正之; 砂田孝之 (2000)、「アルバネーゼ写像と熱核の非対角長時間漸近線」、Comm. Math. Phys.、209 (3): 633–670、Bibcode :2000CMaPh.209..633K、doi :10.1007/s002200050033、S2CID 121065949
小谷正之; 砂田剛志 (2003)、「結晶格子のスペクトル幾何学」、現代数学、現代数学、338 :271–305、doi : 10.1090/conm/338/06077、ISBN 9780821833834

風見剛志; 内山功 (2008)、「周期グラフ上のランダムウォーク」、アメリカ数学会誌、360 (11): 6065–6087、doi : 10.1090/S0002-9947-08-04451-6。

[1] 砂田孝文(2012)、「トポロジカル結晶学講義」、日本数学会誌、7 :1–39、doi :10.1007/s11537-012-1144-4、S2CID 255312584

[2] 砂田孝 (2012)、「離散幾何学解析に向けたトポロジカル結晶学」、応用数学科学の調査とチュートリアル、第 6 巻、Springer

[3] Cohen, E. ; Megiddo, N. (1991)、「周期グラフの特性の認識」、応用幾何学と離散数学: Victor Klee Festschrift (PDF)、DIMACS 離散数学と理論計算機科学シリーズ、第 4 巻、pp. 135–146、doi :10.1090/dimacs/004/10、ISBN 9780821865934、 2010年8月15日閲覧

[4] Delgado-Friedrichs, O.; O'Keeffe, M. (2005)、「グラフとしての結晶ネット：用語と定義」、Journal of Solid State Chemistry、178 (8): 2480–2485、Bibcode :2005JSSCh.178.2480D、doi :10.1016/j.jssc.2005.06.011

[5] Senechal, M. (1990)、「幾何学的結晶学の簡潔な歴史」、Lima-de-Faria, J. (編)、結晶学の歴史地図、Kluwer、pp. 43–59

[6] Vinberg, EB; Shvartsman, OV (1993)、「定曲率空間の運動の離散群」、Vinberg, EB (編)、幾何学 II: 定曲率空間、Springer-Verlag

[7] Senechal, M. (1995)、準結晶と幾何学、ケンブリッジ大学出版、p. 27

[8] Eon, JG (2004)、「ネットのトポロジカル密度：直接計算」、Acta Crystallogr. A、60（Pt 1）：7–18、Bibcode：2004AcCrA..60....7E、doi：10.1107/s0108767303022037、PMID 14691323。

[9] Aste, T. (1999)、「The Shell Map」、Sadoc, JF; Rivier, N. (eds.)、THE SHELL MAP: 動的マップによる泡の構造、Foams and Emulsions、Kluwer、pp. 497–510、arXiv : cond-mat/9803183、Bibcode :1998cond.mat..3183A

[10] M. Kotani およびT. Sunada「結晶格子上のランダムウォークの大偏差の幾何学的側面」『微小局所解析と複素フーリエ解析』（T. Kawai および K. Fujita 編）World Scientific、2002 年、215 ～ 237 ページ。

[11] 小谷正之; 砂田剛志 (2006)、「結晶格子の大きな偏差と無限大接線円錐」、Math. Z.、254 (4): 837–870、doi :10.1007/s00209-006-0951-9、S2CID 122531716

[12] Blatov, VA; Proserpio, DM, TOPOS 結晶構造のトポロジカル解析プログラムパッケージ、 2010年8月15日取得

[13] Earl, DJ; Deem, MW (2006)、「仮説的ゼオライト構造のデータベースに向けて」、Ind. Eng. Chem. Res.、45 (16): 5449–5454、doi :10.1021/ie0510728、S2CID 40620797

[14] デルガド・フリードリッヒス、O.ドレス、AWM;ヒューソン、DH;クリノフスキー、J. Mackay、アラバマ州 (1999 年 8 月 12 日)、「結晶ネットワークの系統的列挙」、Nature、400 (6745): 644–647、Bibcode :1999Natur.400..644D、doi :10.1038/23210、S2CID 4388277。

[15] Dress, A.; Delgado Friedrichs, O.; Huson, D. (1995)、「An algorithmic approach to tilings」、Charles J.、Colbourn ; Ebadollah S.、Mahmoodian (編)、Combinatorics Advances: Papers from the Twenty-fifth Annual Iranian Mathematics Conference (AIMC25) held at Sharif University of Technology, Tehran, March 28–31, 1994、Mathematics and its Applications、vol. 329、Kluwer、pp. 111–119、doi :10.1007/978-1-4613-3554-2_7

[16] Nouar, Farid; Eubank, Jarrod F.; Bousquet, Till; Wojtas, Lukasz; Zaworotko, Michael J.; Eddaoudi, Mohamed (2008)、「高多孔質金属有機構造体の設計と合成のための超分子ビルディングブロック (SBB)」、Journal of the American Chemical Society、130 (6): 1833–1835、doi :10.1021/ja710123s、PMID 18205363

[17] Ramsden, SJ; Robins, V. ; Hyde, S. (2009)、「2D 双曲タイルからの 3D ユークリッドネット: 万華鏡のような例」、Acta Crystallogr. A、65 (Pt 2): 81–108、Bibcode :2009AcCrA..65...81R、doi : 10.1107/S0108767308040592、PMID 19225190。

[18] EPINET: 非ユークリッドタイルにおけるユークリッドパターン、2013年1月30日閲覧

[19] Treacy, MMJ; Rivin, I.; Balkovsky, E.; Randall, KH; Foster, MD (2004)、「周期的四面体フレームワークの列挙。II. 多節グラフ」(PDF)、Microporous and Mesoporous Materials、74 (1–3): 121–132、doi :10.1016/j.micromeso.2004.06.013 、 2010年8月15日閲覧。

[20] LeBail, A. (2005)、「GRINSP による無機構造予測」、J. Appl. Crystallogr.、38 (2): 389–395、doi : 10.1107/S0021889805002384