パスの色分け

グラフ理論では、パスの色付けは通常、次の 2 つの問題のいずれかを指します。

• グラフ におけるパスの（多重）集合を、において辺を共有する任意の2つのパスが異なる色で表示されるように彩色する問題。入力として集合とグラフが与えられる。この定式化は、集合 の競合グラフ、すなわち頂点集合 と、に関して辺素でないすべてのパスのペアを接続する辺を持つグラフ の頂点彩色と等価である。 ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle G}$
• における任意の選択された（多重） パス集合を（上記の定義に従って）彩色する問題。この場合、 からのパスの端点のペアの集合は、リクエスト集合と呼ばれる集合または多重集合 に等しい。入力として集合とグラフが与えられる。この問題は、コールスケジューリングと呼ばれる、より一般的なグラフルーティング問題の特殊なケースである。${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle G}$

上記のどちらの問題も、通常、色付けに使用する色の数を最小化することが目標となります。パス色付けのバリエーションによっては、単純なグラフ、有向グラフ、または多重グラフが使用される場合があります。 ${\displaystyle G}$

参考文献

• パスカラーリングとコールスケジューリングの複雑性（Thomas ErlebachとKlaus Jansen著）
• Viggo Kann による NP 最適化問題集 (問題: 最小パス彩色)