世界を席巻する集団

グラフ理論では、グローバル支配集合は支配集合である${\displaystyle S}$グラフの${\displaystyle G}$それは補グラフの支配集合でもある${\displaystyle {\bar {G}}}$世界支配数${\displaystyle \gamma _{g}(G)}$は、グローバル支配集合の最小濃度です。${\displaystyle G}$この概念は1989年にE.サンパスクマールによって提唱された。^{[ 1 ]}

させて${\displaystyle G=(V,E)}$頂点集合を持つグラフである${\displaystyle V}$エッジセット${\displaystyle E}$セット${\displaystyle S\subseteq V}$支配的な集合は${\displaystyle G}$すべての頂点が${\displaystyle VS}$少なくとも１つの頂点に隣接している${\displaystyle S}$圧倒的なセット${\displaystyle S}$がグローバル支配集合（またはgd集合）と呼ばれるのは、${\displaystyle S}$補集合の支配集合でもある${\displaystyle {\bar {G}}}$[ ^{1 ]​}

同等に、支配集合${\displaystyle S}$の${\displaystyle G}$がグローバル支配集合であるのは、各頂点に対して が成り立つ場合のみである。${\displaystyle v\in VS}$頂点が存在する${\displaystyle u\in S}$そのため${\displaystyle u}$隣接していません${\displaystyle v}$で${\displaystyle G}$[ ^{1 ]​}

以下の性質は任意のグラフに当てはまります。${\displaystyle G}$: ^{[ 1 ]}

• ${\displaystyle \gamma _{g}(G)=\gamma _{g}({\bar {G}})}$
• ${\displaystyle \gamma (G)\leq \gamma _{g}(G)}$、 どこ${\displaystyle \gamma (G)}$は、​${\displaystyle G}$
• ${\displaystyle {\bar {\gamma }}(G)\leq \gamma _{g}(G)}$、 どこ${\displaystyle {\bar {\gamma }}(G)=\gamma ({\bar {G}})}$
• ${\displaystyle {\frac {\gamma (G)+{\bar {\gamma }}(G)}{2}}\leq \gamma _{g}(G)\leq \gamma (G)+{\bar {\gamma }}(G)}$

グラフの場合${\displaystyle G}$順序の${\displaystyle p}$孤立した頂点がない場合: ^{[ 1 ]}

• ${\displaystyle \gamma (G)+\gamma _{g}(G)\leq p+1}$
• $\gamma _{g}(G)\leq \max\{\chi (G),\chi ({\bar {G}})\}}$、 どこ${\displaystyle \chi (G)}$は、​${\displaystyle G}$

グローバル支配数は、特定のグラフ操作の下で不変性を示します。たとえば、サイクルの場合、${\displaystyle C_{n}}$（と${\displaystyle n\neq 3,n\neq 5}$）、エッジ複製操作の下ではグローバル支配数は変化せず、ホイールについても同様である。${\displaystyle W_{n}}$[ ^{2 ]​}

特定のグラフのファミリーについては、グローバル支配数が決定されています: ^{[ 1 ] [ 2 ]}

• 完全なグラフについては${\displaystyle K_{p}}$またはその補数${\displaystyle {\bar {K}}_{p}}$:${\displaystyle \gamma _{g}(G)=p}$
• 完全二部グラフの場合${\displaystyle K_{m,n}}$と${\displaystyle 2\leq m\leq n}$:${\displaystyle \gamma _{g}(K_{m,n})=n}$
• サイクルごとに${\displaystyle C_{n}}$と${\displaystyle n\neq 3}$そして${\displaystyle n\neq 5}$:${\displaystyle \gamma _{g}(C_{n})=\lceil n/3\rceil }$
• パスの場合${\displaystyle P_{n}}$と${\displaystyle n\geq 4}$:${\displaystyle \gamma _{g}(P_{n})=\lceil n/3\rceil }$
• ホイール用${\displaystyle W_{n}}$:${\displaystyle \gamma _{g}(W_{n})=4}$もし${\displaystyle n=4}$、 そして${\displaystyle \gamma _{g}(W_{n})=3}$さもないと

グローバル国内番号${\displaystyle d_{g}(G)}$は頂点集合の分割の最大次数である。${\displaystyle V}$グローバル支配集合に。支配数とドマティック数の関係と同様に、${\displaystyle d_{g}(G)=d_{g}({\bar {G}})}$そして${\displaystyle d_{g}(G)\leq d(G)\leq \delta (G)+1}$、 どこ${\displaystyle d(G)}$はドマティックナンバーであり、${\displaystyle \delta (G)}$は最小の度数です${\displaystyle G}$[ ^{1 ]​}

最小グローバル支配集合を見つける問題はNP困難である。これは、NP困難であることが知られている支配集合問題からの還元によって、ブリガムとダットン（1990）によって確立された。 ^{[ 3 ] [ 4 ]}

平面グラフや分割グラフなどの制限されたグラフクラスでも、この問題はNP困難のままです。分割グラフの場合、任意のグローバル支配集合は、グラフの支配集合、または独立集合からの頂点を追加した支配集合のいずれかによって形成されます。^{[ 3 ]}

グローバル支配問題に対しては、厳密アルゴリズムとヒューリスティックアルゴリズムの両方が開発されている。^{[ 3 ]}

正確なアルゴリズム：

• 整数線形計画法（ILP）の定式化${\displaystyle 2n}$両方において支配を保証するための制約${\displaystyle G}$そして${\displaystyle {\bar {G}}}$
• 下限と上限によって誘導される、実行可能な解のサイズに対する二分探索を用いた暗黙的列挙アルゴリズム

ヒューリスティックアルゴリズム：

• グラフとその補グラフの両方において、新たに支配される頂点の数を最大化するように頂点を反復的に選択する貪欲アルゴリズム
• 支配性を維持しながら冗長な頂点を除去することで、グローバル支配集合のサイズを縮小する精製手順。

グローバル支配集合は、ネットワーク信頼性のコンテキストで自然に発生します。さまざまな場所を結ぶ道路のネットワークを表すグラフを考えてみましょう。一部の場所には供給ステーションがあります。プライマリリンク（エッジ）が${\displaystyle G}$供給が途絶える可能性があるので、供給を維持するには、駅が代替リンク（${\displaystyle {\bar {G}}}$) グローバル支配集合は、どのネットワーク (プライマリまたはバックアップ) が稼働しているかに関わらず、サービスを維持するために必要な最小限の供給ステーションの集合を表します。^{[ 1 ]}

ソーシャルネットワーク分析において、特定の社会的行動をとる個人をモデル化する場合、標準的な支配集合は影響力のある個人を特定しますが、影響力関係の潜在的な変化を考慮していません。グローバル支配集合は、影響力ネットワークがその補集合に変化した場合でも網羅性を確保し、動的なネットワーク変化に対する回復力を提供します。^{[ 3 ]}

• ハリス、エリザベス・マリー（2012年8月）。グローバル支配安定グラフ（修士論文）。イーストテネシー州立大学。