グラフ理論において、高度に不規則なグラフとは、すべての頂点に対して、その頂点に隣接するすべての頂点が異なる次数を持つグラフのことです。
歴史
不規則グラフは、ユーセフ・アラヴィ、ゲイリー・チャートランド、ファン・チュン、ポール・エルデシュ、ロナルド・グラハム、オルトルート・オラーマンによって最初に特徴付けられました。[1]彼らは、規則グラフ の「反対」を定義しようとしたのですが、この概念は徹底的に研究され、よく理解されていました。
局所性と規則性
「不規則グラフ」の定義はすぐには明らかではありませんでした。k 正則グラフでは、すべての頂点の次数は kです。複数の頂点を持つグラフGでは、 G内の2つの頂点は同じ次数を持つ必要があります。したがって、すべての頂点の次数が異なるグラフを不規則グラフと定義することはできません。そこで、2つの頂点を除いてすべての頂点の次数が異なるグラフを不規則グラフと定義したくなるかもしれませんが、このようなグラフもよく理解されているため、興味深いものではありません。[2]
グラフ理論家たちは、局所正則性の問題に着目した。グラフが頂点vにおいて局所正則であるとは、 vに隣接するすべての頂点の次数がrであることを意味する。したがって、グラフGの各頂点vについて、 vの隣接する頂点の次数がそれぞれ異なる場合、グラフは局所不規則であるといえ、これらのグラフは高度に不規則なグラフと呼ばれる。[1]
不規則グラフの性質
Alaviらが概説した高度に不規則なグラフに関するいくつかの事実: [3]
- 高度に不規則なグラフHにおいて、vが最大次数dの頂点である場合、 vは次数1、2、…、 dのちょうど1つの頂点に隣接している。[3]
- 高度に不規則なグラフの最大次数は、頂点数の半分以下である。[3]
- Hが最大次数dの高度不規則グラフである場合、 Hのコピーを2つ取り、次数dの2つの頂点間に辺を追加する ことで、次数d +1の高度不規則グラフを構築することができます。[3]
- H ( n )/ G ( n )はnが指数関数的に急速に無限大に近づくにつれて0に近づく。ここでH ( n )はn頂点を持つ（非同型）高度に不規則なグラフの数であり、G ( n )はn頂点を持つグラフの総数である。[3]
- あらゆるグラフGに対して、 Gを誘導部分グラフとして含む非常に不規則なグラフHが存在する。[3]
この最後の観察は、デーネス・ケーニヒの結果と類似していると考えることができる。それは、Hが最大次数rのグラフである 場合、 r正則でHを誘導部分グラフとして含むグラフGが存在するというものである。[3]
不規則性の応用
不規則性の定義は、生物学、生態学、技術、経済など、多岐にわたるネットワークに影響を及ぼすネットワークの異質性の研究において重要となっています。[4]グラフ統計については様々なものが提案されており、その多くはグラフの頂点数とその次数に基づいています。高度に不規則なグラフの特性評価も異質性の問題に適用されてきましたが、いずれも現実世界の状況を十分に解明できていません。ネットワークの異質性を定量化する適切な方法を見つけるための努力は続けられています。[4]
参考文献
- ^ ab Chartrand, Gary; Erdös, Paul; Oellermann, Ortrud R. (1988). 「不規則グラフの定義方法」. The College Mathematics Journal . 19 (1). Informa UK Limited: 36– 42. doi :10.1080/07468342.1988.11973088. ISSN 0746-8342.
- ^ Behzad, Mehdi; Chartrand, Gary (1967). 「完璧なグラフなど存在しない」. The American Mathematical Monthly . 74 (8). JSTOR: 962. doi :10.2307/2315277. ISSN 0002-9890. JSTOR 2315277.
- ^ abcdefg Alavi, Yousef; Chartrand, Gary; Chung, FRK; Erdös, Paul; Graham, RL; Oellermann, Ortrud R. (1987). 「高度に不規則なグラフ」(PDF) . Journal of Graph Theory . 11 (2). Wiley: 235– 249. doi :10.1002/jgt.3190110214. ISSN 0364-9024.
- ^ ab Estrada, Ernesto (2010-12-02). 「ネットワークの異質性の定量化」. Physical Review E. 82 ( 6) 066102. アメリカ物理学会 (APS). Bibcode :2010PhRvE..82f6102E. doi :10.1103/physreve.82.066102. ISSN 1539-3755. PMID 21230700.
