Loading article…
数学の分野であるグラフ理論において、因数臨界グラフ（またはハイポマッチング可能グラフ[1] [2]）は、n頂点を持ち、 n − 1頂点のすべての誘導部分グラフが完全マッチングを持つグラフです。（グラフ内の完全マッチングとは、グラフの各頂点がその部分集合内のちょうど 1 つの辺の端点であるという性質を持つ、グラフの辺の部分集合です。）
グラフの 1 つの頂点を除くすべての頂点をカバーするマッチングは、ほぼ完全なマッチングと呼ばれます。したがって、因数臨界グラフとは、すべての可能性のある頂点を回避するほぼ完全なマッチングが存在するグラフのことです。
例
任意の奇数長サイクルグラフは因数臨界的であり、[1]奇数の頂点を持つ任意の完全グラフも同様である。 [3]より一般的には、奇数の頂点を持つすべてのハミルトングラフは因数臨界的である。友情グラフ（単一の共通頂点で三角形の集合を接続することによって形成されるグラフ）は、因数臨界的であるがハミルトンではないグラフの例である。
グラフGが因数臨界であれば、Gのミシェルスキアンも因数臨界です。例えば、5頂点サイクルグラフのミシェルスキアンであるグロッツグラフは因数臨界です。 [4]
2頂点接続で クローフリーで頂点数が奇数のグラフはすべて因数臨界である。例えば、正二十面体（回転長五角錐のグラフ）から頂点を1つ取り除いてできた11頂点グラフは2接続かつクローフリーなので因数臨界である。この結果は、頂点数が偶数の接続されたクローフリーグラフはすべて完全マッチングを持つというより基本的な定理から直接導かれる。[5]
特徴
因子臨界グラフは、各頂点の削除によって完全なマッチングが可能になるグラフとして定義される以外にも、いくつかの異なる方法で特徴付けることができます。
- ティボール・ガライは、グラフが因数臨界的であるためには、グラフが連結であり、グラフの各ノードvに対してv を含まない最大マッチングが存在する必要があることを証明した。これらの特性から、グラフには奇数の頂点が必要であり、すべての最大マッチングは1つの頂点を除くすべての頂点とマッチングする必要があることがわかる。[6]
- ラースロー・ロヴァースは、グラフが因数臨界的である場合、かつその場合のみグラフが奇数耳分解を持つことを証明した。奇数耳分解とは、グラフの辺を部分グラフの列に分割したもので、各部分グラフは奇数長のパスまたはサイクルで、列の最初のものはサイクルで、列の各パスは両端点を持つが前の部分グラフの頂点上には内部点がなく、列の最初のもの以外の各サイクルは前の部分グラフの頂点を 1 つだけ持つ。たとえば、図のグラフはこのように 5 つの辺のサイクルと 3 つの辺のパスに分割できる。因数臨界グラフのほぼ完全なマッチングも与えられている場合、各耳がマッチングした辺と一致しない辺を交互に持つように耳分解を選択できる。[7] [8]
- グラフが因子臨界的であるのは、奇数長のサイクルの縮約のシーケンスによって単一の頂点に縮小できる場合のみです。さらに、この特徴付けでは、シーケンス内の各サイクルを選択して、前のサイクルの縮約によって形成された頂点を含めることができます。[1]たとえば、耳分解の耳を、分解で指定された順序で縮約すると、各耳が縮約された時点で奇数サイクルが形成されるため、耳分解の特徴付けを使用して、縮約する奇数サイクルのシーケンスを見つけることができます。逆に、それぞれが前の縮約から形成された頂点を含む奇数サイクル縮約のシーケンスから、各ステップで縮約されたエッジの集合が耳である耳分解を形成できます。
- グラフG が、頂点vと、 v以外のすべての頂点をカバーするマッチングMの選択肢とともに与えられているとします。Gが因数臨界となるのは、 G内に、 v をG内の他の各頂点に接続する、マッチングされたエッジと一致しないエッジが交互に現れるパスの集合がある場合のみです。この特性に基づいて、与えられたほぼ完全なマッチングを持つグラフGが因数臨界であるかどうかを線形時間で判定することができます。[9]
プロパティ
因数臨界グラフは常に奇数の頂点を持ち、2辺連結でなければならない（つまり、橋を持つことはできない）。[10]しかし、必ずしも2頂点連結である必要はない。友情グラフは反例である。因数臨界グラフが二部グラフであるはずがない。なぜなら、ほぼ完全なマッチングを持つ二部グラフでは、完全にマッチング可能なグラフを生成するために削除できる頂点は、二分割の大きい側にある頂点だけであるからである。
m個の辺を持つ 2 頂点接続の因数臨界グラフには、少なくともm 個の異なるほぼ完全なマッチングが存在し、より一般的には、m個の辺とc 個のブロック (2 頂点接続コンポーネント) を持つすべての因数臨界グラフには、少なくともm − c + 1 個の異なるほぼ完全なマッチングが存在します。これらの境界が厳しいグラフは、特定の形式の奇数耳分解を持つことによって特徴付けられる場合があります。[3]
連結グラフは、十分な数の辺を縮約することで因数臨界グラフに変換できる 。与えられたグラフGを因数臨界にするために縮約する必要がある最小の辺集合はマトロイドの基底を形成し、これは貪欲アルゴリズムを使用して、グラフを因数臨界にするために縮約する最小の重みの辺集合を多項式時間で見つけることができることを意味する。[11]
アプリケーション
ブロッサムは、より大きなグラフの因子臨界サブグラフです。ブロッサムは、非二部グラフにおける最大マッチングと最小重みの完全マッチングのためのジャック・エドモンズのアルゴリズムで重要な役割を果たします。 [12]
多面体組合せ論では、因子臨界グラフは与えられたグラフの対応する多面体の面を記述する上で重要な役割を果たします。[1] [2]
一般化と関連概念
グラフがk因子臨界であるとは、 n − k個の頂点のすべての部分集合が完全マッチングを持つ場合を言う。この定義によれば、ハイポマッチング可能なグラフは 1 因子臨界である。 [13]さらに一般的には、グラフが( a , b )因子臨界であるとは、 n − k個の頂点のすべての部分集合がr因子を持つ場合、つまり、それが与えられたグラフのr正則部分グラフの頂点集合である場合を言う。
クリティカルグラフ（限定なし）は、通常、グラフの各頂点を削除するとグラフの色付けに必要な色の数が減るグラフを意味すると想定されています。 クリティカルの概念は、グラフ理論において、各可能な頂点を削除するとグラフの関連する特性が変化するか変化しないグラフを指すために、より一般的に使用されています。マッチングクリティカルグラフとは、任意の頂点を削除しても最大マッチングのサイズが変化しないグラフです。 ガライの特徴付けによると、マッチングクリティカルグラフは、すべての接続コンポーネントが因子クリティカルであるグラフです。[14]クリティカルグラフの補グラフは必然的にマッチングクリティカルであり、この事実はガライによってクリティカルグラフの頂点数の下限を証明するために使用されました。[15]
グラフ理論を超えて、因子臨界性の概念はマトロイドに拡張され、マトロイド上の耳分解の一種を定義し、すべての耳が奇数である耳分解を持つマトロイドを因子臨界であると定義しました。[16]
参考文献
- ^ abcd Pulleyblank, WR ; Edmonds, J. (1974)、「1 マッチング多面体のファセット」、Berge, C. ; Ray-Chaudhuri, DK (編)、Hypergraph Seminar、Lecture Notes in Mathematics、vol. 411、Springer-Verlag、pp. 214–242、doi :10.1007/BFb0066196、ISBN 978-3-540-06846-4。
- ^ ab Cornuéjols, G. ; Pulleyblank, WR (1983)、「巡回セールスマン問題に対する臨界グラフ、マッチング、ツアーまたは緩和の階層」、Combinatorica、3 (1): 35–52、doi :10.1007/BF02579340、MR 0716420、S2CID 35825797。
- ^ ab Liu, Yan; Hao, Jianxiu (2002)、「因子臨界グラフのほぼ完全なマッチングの列挙」、離散数学、243 (1–3): 259–266、doi :10.1016/S0012-365X(01)00204-7、MR 1874747。
- ^ Došlić, Tomislav (2005)、「Mycielskians とマッチング」、Discussiones Mathematicae Graph Theory、25 (3): 261–266、doi : 10.7151/dmgt.1279、MR 2232992。
- ^ Favaron, Odile ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997)、「DCT グラフにおける因子臨界性とマッチング拡張」、Discussiones Mathematicae Graph Theory、17 (2): 271–278、CiteSeerX 10.1.1.25.6314、doi :10.7151/dmgt.1054、MR 1627955 。
- ^ Galrai, T. (1963)、「Neuer Beweis eines Tutte'schen Satzes」、マジャール語。アカド。マット。クタト国際空港ケズル。、8 : 135–139、MR 0166777。フランク、アンドラスが引用したように。 Szegő、László (2002)、「パスマッチング式に関する注記」(PDF)、Journal of Graph Theory、41 (2): 110–119、CiteSeerX 10.1.1.20.7918、doi :10.1002/jgt.10055、MR 1926313、S2CID 206076722 。
- ^ Lovász、L. (1972)、「因子クリティカル グラフに関するメモ」、Studia Sci.数学。ハンガル。、7 : 279–280、MR 0335371 。
- ^ Korte, Bernhard H. ; Vygen, Jens (2008)、「10.4 因子臨界グラフの耳分解」、組み合わせ最適化: 理論とアルゴリズム、アルゴリズムと組み合わせ論、第 21 巻 (第 4 版)、Springer-Verlag、pp. 235–241、ISBN 978-3-540-71843-7。
- ^ Lou, Dingjun; Rao, Dongning (2004)、「因子臨界グラフの特徴付けとアルゴリズム」(PDF)、The Australasian Journal of Combinatorics、30 : 51–56、MR 2080453。
- ^ Seyffarth, Karen (1993)、「最大平面グラフのパッキングと完全パス二重被覆」、離散数学、117 (1–3): 183–195、doi : 10.1016/0012-365X(93)90334-P、MR 1226141。
- ^ Szigeti, Zoltán (1996)、「グラフの耳分解によって定義されるマトロイドについて」、Combinatorica、16 (2): 233–241、doi :10.1007/BF01844849、MR 1401896、S2CID 206806006. 因子臨界グラフに到達するために最小数の（重み付けされていない）エッジを縮小する以前のアルゴリズムについては、Frank, András (1993)、「グラフの保守的な重み付けと耳分解」、Combinatorica、13 (1): 65–81、doi :10.1007/BF01202790、MR 1221177、S2CID 10857300を参照してください。。
- ^ エドモンズ、ジャック（1965）、「道、木、花」、カナダ数学ジャーナル、17：449–467、doi：10.4153 / CJM-1965-045-4、MR 0177907、S2CID 18909734。
- ^ ファヴァロン、オディール(1996)、「k 因子臨界グラフについて」、Discussiones Mathematicae Graph Theory、16 (1): 41–51、doi : 10.7151/dmgt.1022、MR 1429805。
- ^ Erdős, P. ; Füredi, Z. ; Gould, RJ ; Gunderson, DS (1995)、「交差する三角形の極値グラフ」、Journal of Combinatorial Theory、シリーズ B、64 (1): 89–100、doi : 10.1006/jctb.1995.1026、MR 1328293。
- ^ Galrai、T. (1963b)、「Kritische Graphen II」、Publ.数学。研究所ハンガル。アカド。科学。、8 : 373–395Stehlík, Matěj (2003)「Critical graphs with connected complements」、Journal of Combinatorial Theory、Series B、89 (2): 189–194、doi :10.1016/S0095-8956(03)00069-8、MR 2017723より引用。
- ^ Szegedy, Balázs ; Szegedy, Christian (2006)、「シンプレクティック空間とマトロイドの耳分解」、Combinatorica、26 (3): 353–377、doi :10.1007/s00493-006-0020-3、MR 2246153、S2CID 11578490。