Loading article…
グラフ理論において、パリティグラフとは、同じ2つの頂点間の2つの誘導パスがすべて同じパリティを持つグラフである。つまり、両方のパスの長さが奇数か、両方とも偶数である。[1]このクラスのグラフは、Burlet & Uhry (1984) によって命名され、初めて研究された。[2]
関連するグラフのクラス
パリティ グラフには、同じ 2 つの頂点間のすべての 2 つの誘導パスが同じ長さである距離遺伝グラフが含まれます。また、同じ 2 つの頂点間のすべての 2 つのパス (必ずしも誘導パスではない) が同じパリティを持つグラフとして類似の特徴付けられる二部グラフや、二部グラフの一般化であるライン パーフェクト グラフも含まれます。すべてのパリティ グラフはメイニエル グラフであり、長さ 5 以上のすべての奇数サイクルに 2 つの弦があるグラフです。パリティ グラフでは、任意の長い奇数サイクルを異なるパリティの 2 つのパスに分割することができ、どちらも単一のエッジではなく、これらが両方とも誘導パスにならないようにするには少なくとも 1 つの弦が必要です。次に、サイクルをこの最初の弦のエンドポイント間で 2 つのパスに分割すると、この 2 番目の分割の 2 つのパスが誘導されるのを防ぐために 2 番目の弦が必要になります。メイニエルグラフは完全グラフなので、パリティグラフも完全です。[1]それらは、単一の辺との直積が完全であるグラフです。 [3]
アルゴリズム
グラフがパリティグラフであるためには、その分割分解のすべての要素が完全グラフか二部グラフのいずれかである必要があります。[4] この特徴付けに基づいて、与えられたグラフがパリティグラフであるかどうかを線形時間でテストすることができます。同じ特徴付けにより、二部グラフからパリティグラフへのいくつかのグラフ最適化アルゴリズムの一般化も可能になります。たとえば、分割分解を使用すると、パリティグラフの重み付き最大独立集合を多項式時間で見つけることができます。[5]
参考文献
- ^ ab パリティグラフ、グラフクラスとその包含に関する情報システム、2016年9月25日閲覧。
- ^ Burlet, M.; Uhry, J.-P. (1984)、「パリティグラフ」、完全グラフに関するトピック、North-Holland Math. Stud.、vol. 88、North-Holland、アムステルダム、pp. 253–277、doi :10.1016/S0304-0208(08)72939-6、MR 0778766。
- ^ Jansen, Klaus (1998)、「パリティグラフの新しい特徴付けとコスト付きカラーリング問題」、LATIN'98: 理論情報学 (Campinas、1998)、Lecture Notes in Comput. Sci.、vol. 1380、Springer、ベルリン、pp. 249–260、doi :10.1007/BFb0054326、hdl : 11858/00-001M-0000-0014-7BE2-3、MR 1635464。
- ^ シセローネ、セラフィーノ; Di Stefano、Gabriele (1999)、「パリティ グラフへの二部構成の拡張について」、Discrete Appl.数学。、95 (1–3): 181–195、土井: 10.1016/S0166-218X(99)00074-8、S2CID 17260334。
- ^ Cicerone, Serafino; Di Stefano, Gabriele (1997)、「二部グラフとパリティグラフの基本問題における複雑さの同値性について」、Algorithms and computing (シンガポール、1997)、Lecture Notes in Comput. Sci.、vol. 1350、Springer、ベルリン、pp. 354–363、doi :10.1007/3-540-63890-3_38、MR 1651043。