Loading article…
グラフ理論において、グラフGの商グラフ Qは、頂点がGの頂点の分割のブロックであるグラフであり、ブロックBがブロックCに隣接するのは、 Gの辺集合に関してブロックBの何らかの頂点がブロックCの何らかの頂点に隣接している場合である。[1]言い換えれば、Gに辺集合Eと頂点集合Vがあり、分割によって誘導される同値関係がRである場合、商グラフには頂点集合V / Rと辺集合 {([ u ] R , [ v ] R ) | ( u , v ) ∈ E ( G )}がある 。
より正式には、商グラフはグラフのカテゴリにおける商オブジェクトです。グラフのカテゴリは具体化可能であり、グラフをその頂点の集合にマッピングすると具体的なカテゴリになります。そのため、そのオブジェクトは「追加の構造を持つ集合」と見なすことができ、商グラフは、その頂点集合Vの商集合V / Rに誘導されるグラフに対応します。さらに、グラフから商グラフへのグラフ準同型(商写像)があり、各頂点または辺をそれが属する同値類に送ります。直感的には、これはグラフの頂点と辺を「接着する」(正式には「識別する」) ことに相当します。
例
グラフは、それ自体の商グラフであることは明らかであり（分割の各ブロックは単一の頂点である）、単一の点からなるグラフは、空でない任意のグラフの商グラフである（分割はすべての頂点の単一のブロックからなる）。最も単純な非自明な商グラフは、2 つの頂点を識別することによって得られるグラフである（頂点識別）。頂点が接続されている場合は、これを辺の縮約と呼ぶ。
特殊な商の種類
有向グラフの凝縮は、強く連結されたコンポーネントが分割のブロックを形成する商グラフです。この構成は、任意の有向グラフから有向非巡回グラフを導出するために使用できます。 [2]
無向グラフGにおける 1 つ以上の辺の縮約の結果はGの商であり、そのブロックは縮約された辺によって形成されるGのサブグラフの接続コンポーネントです。ただし、より一般的な商の場合、商を生成する分割のブロックは接続されたサブグラフを形成する必要はありません。
G が別のグラフHの被覆グラフである場合、H はGの商グラフである。対応する分割のブロックは、被覆写像の下でのHの頂点の逆像である。しかし、被覆写像には、商には一般的に当てはまらない、写像が局所同型であるという追加の要件がある。[3]
計算の複雑さ
n頂点の立方体グラフ Gとパラメータkが与えられたとき、 Gがn + k頂点の平面グラフの商として得られるかどうかを決定する計算量はNP完全である。[4]
参考文献
- ^ サンダース、ピーター、シュルツ、クリスチャン (2013)、「高品質グラフ分割」、グラフ分割とグラフクラスタリング、Contemp. Math.、vol. 588、Amer. Math. Soc.、プロビデンス、RI、pp. 1–17、doi :10.1090/conm/588/11700、MR 3074893。
- ^ Bloem, Roderick; Gabow, Harold N. ; Somenzi, Fabio (2006 年 1 月)、「 n log nシンボリックステップでの強連結成分分析アルゴリズム」、システム設計における形式手法、28 (1): 37–56、doi :10.1007/s10703-006-4341-z、S2CID 11747844。
- ^ ガーディナー、A. (1974)、「対蹠被覆グラフ」、組合せ理論ジャーナル、シリーズB、16 (3): 255–273、doi : 10.1016/0095-8956(74)90072-0、MR 0340090。
- ^ Faria, L.; de Figueiredo, CMH; Mendonça, CFX (2001)、「分割数は NP 完全である」、Discrete Applied Mathematics、108 (1–2): 65–83、doi :10.1016/S0166-218X(00)00220-1、MR 1804713。