混合グラフ

グラフ理論において、混合グラフ $G = (V, E, A)$ は、頂点の集合 $V 、（無向）$ 辺の集合 $E$ 、有向辺（または弧）の集合 $Aからなる$ グラフである。^[1]

定義と表記

隣接する頂点を考えてみましょう。有向辺は弧と呼ばれ、向きのある辺であり、またはと表記されます（は弧の末尾、は弧の先頭であることに注意してください）。^[2]また、無向辺、つまり辺は向きのない辺であり、またはと表記されます。^[2] $u,v\in V$ ${\overrightarrow {uv}}$ $(u,v)$ $u$ $v$ $uv$ $[u,v]$

この例では、混合グラフのループや複数のエッジは考慮しません。

混合グラフのウォークは、すべてのインデックスに対して、がグラフのエッジであるか、がグラフのアークであるような、頂点とエッジ/アークのシーケンスです。このウォークは、最初と最後の頂点を除いて、エッジ、アーク、または頂点を繰り返さない場合、パスです。ウォークの最初と最後の頂点が同じである場合、ウォークは閉じており、閉じたパスはサイクルです。混合グラフは、サイクルを含まない場合、 非循環です。 $v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}$ $i$ $c_{i}=v_{i}v_{i+1}$ $c_{i}={\overrightarrow {v_{i}v_{i+1}}}$

着色

$混合グラフの色付けは、混合グラフの頂点にk 個$ の異なる色（ $k$ は正の整数）をラベル付けまたは割り当てることと考えることができます。 ^[3]辺で接続された頂点には異なる色を割り当てる必要があります。色は $1から$ $k$ までの数字で表すことができ、有向弧の場合、弧の末尾は弧の先頭よりも小さい数字で色付けする必要があります。^[3]

例

たとえば、右の図を考えてみましょう。混合グラフに色を付けるときに使用できる $k色は$ ${1、2、3} です。$ $u$ と $v は$ 辺でつながっているので、異なる色またはラベルを付ける必要があります ( $u$ と $v にはそれぞれ 1 と 2 のラベルが付けられます)。また、$ $vから$ $w$ への弧もあります。方向によって順序が割り当てられるので、弧の先端 ( $w$ )よりも小さい色 (またはセットの整数) で尾 ( $v ) にラベルを付ける必要があります。$

強い色と弱い色

混合グラフの（強い）適切な $k$ 色付けは関数 $c : V \to [k] （$ $[k] := {1, 2, \dots, k}）$ であり、 $uv$ $\in$ $E$ の場合には $c (u) \neq c (v)$ であり、の場合には $c$ $($ $u$ $) <$ $c$ $($ $v$ $)$ である。^[1] ${\overrightarrow {uv}}\in A$

より弱い条件を弧に適用して、混合グラフの弱い適切な $k$ 色付けを関数 $c : V \to [k]$ と考えることができます。ここで $[k] := {1, 2, \dots, k}は、$ $uv$ $\in$ $E$ の場合は $c (u) \neq c (v)$ であり、の場合は $c$ $($ $u$ $) \leq$ $c$ $($ $v$ $)$ です。^{[1]例に戻ると、これは} $($ $v$ $,$ $w$ $)$ の先頭と末尾の両方に正の整数 2 のラベルを付けることができることを意味します。 ${\overrightarrow {uv}}\in A$

カウント

混合グラフには、色付けが存在する場合と存在しない場合があります。混合グラフが $k$ 色付けを持つためには、グラフに有向閉路が含まれていてはなりません。^[2]このような $k$ 色付けが存在する場合、グラフを適切に色付けするために必要な最小の $k を$ 彩色数と呼び、 $χ (G)$ と表記します。^[2]適切な $k$ 色の数は、 $k$ の多項式関数であり、グラフ $Gの$ 彩色多項式と呼ばれ(無向グラフの彩色多項式との類推)、 $χ$ $G$ $($ $k$ $)$ と表記できます。^[1]

弱彩色多項式の計算

削除-縮小法は、混合グラフの弱い彩色多項式を計算するために使用できます。この方法では、辺または弧を削除し (つまり、除去し)、その辺または弧に接する残りの頂点を結合して 1 つの頂点を形成します。^[4]混合グラフ $G$ $= ($ $V$ $,$ $E$ $,$ $A$ $)から辺$ $e を$ 削除すると、混合グラフ $($ $V$ $,$ $E$ $-$ $e$ $,$ $A$ $)$ が得られます。この辺 $eの削除を$ $G$ $-$ $e$ で表します。同様に、混合グラフから弧 $a を削除すると、$ $($ $V$ $,$ $E$ $,$ $A$ $-$ $a$ $)が得られます。ここで、$ $a$ の削除を $G$ $-$ $a$ で表します。また、 $e$ と $a$ の縮小をそれぞれ $G$ $/$ $e$ と $G$ $/$ $a$ で表します。Beck ら^[4]で与えられた命題から、混合グラフの彩色多項式を計算するための次の式が得られます。^[5]

$\chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)$ 、
$\chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)$ 。

アプリケーション

スケジュールの問題

混合グラフは、特定のタイミング制約の下で一連のタスクを実行するジョブショップスケジューリング問題をモデル化するために使用できます。この種の問題では、無向エッジを使用して、2 つのタスクが互換性がない (同時に実行できない) という制約をモデル化できます。有向エッジは、1 つのタスクを別のタスクよりも先に実行する必要があるという優先順位制約をモデル化するために使用できます。スケジューリング問題からこのように定義されたグラフは、分離グラフと呼ばれます。混合グラフの色付け問題は、すべてのタスクを実行するための最小の長さのスケジュールを見つけるために使用できます。^[2]

ベイズ推論

混合グラフは、ベイズ推論のグラフィカルモデルとしても使用されます。この文脈では、非循環混合グラフ（有向辺の循環がないグラフ）は、チェーングラフとも呼ばれます。これらのグラフの有向辺は、2 つのイベント間の因果関係を示すために使用されます。この場合、最初のイベントの結果は、2 番目のイベントの確率に影響します。一方、無向辺は、2 つのイベント間の因果関係のない相関関係を示します。チェーングラフの無向サブグラフの接続コンポーネントは、チェーンと呼ばれます。チェーングラフは、モラルグラフを構築することで無向グラフに変換できます。モラルグラフは、同じチェーンに出ているエッジを持つ頂点のペアの間に無向辺を追加し、有向辺の方向を忘れることで、チェーングラフから形成された無向グラフです。^[6]

注記

^ abcd Beck et al. (2013, p. 1)
^ abcde Ries (2007, p. 1)
^ ab ハンセン、クプリンスキー、デ・ヴェラ (1997、p. 1)
^ ab Beck et al. (2013, p. 4)
^ ベック他 (2013, p. 5)
^ Cowell et al. (1999).

参考文献

Beck, M.; Blado, D.; Crawford, J.; Jean-Louis, T.; Young, M. (2013)、「混合グラフの弱彩色多項式について」、Graphs and Combinatorics、31 : 91–98、arXiv : 1210.4634、doi :10.1007/s00373-013-1381-1。
コーウェル、ロバート G.フィリップ・デイヴィッド;ラウリッツェン、ステフェン L. ; Spiegelhalter、David J. (1999)、確率的ネットワークとエキスパートシステム: ベイジアンネットワークの正確な計算方法、Springer-Verlag New York、p. 27、土井：10.1007/0-387-22630-3 (2024 年 11 月 1 日に非アクティブ)、ISBN 0-387-98767-3{{citation}}: CS1 メンテナンス: DOI は 2024 年 11 月時点で非アクティブです (リンク)
ハンセン、ピエール、クプリンスキー、ジュリオ、ドミニク・デ・ヴェラ（1997）、「混合グラフカラーリング」、オペレーションズ・リサーチの数学的手法、45（1）：145–160、doi：10.1007/BF01194253、MR 1435900。
Ries, B. (2007)、「混合グラフのいくつかのクラスの色付け」、離散応用数学、155 (1): 1–6、doi : 10.1016/j.dam.2006.05.004、MR 2281351。

外部リンク

Weisstein、Eric W.「混合グラフ」。MathWorld。

[BeckBladoCrawfordJeanLouisYoung-1] Beck et al. (2013, p. 1)

[Ries-2] Ries (2007, p. 1)

[HansenKuplinskydeWerra-3] ハンセン、クプリンスキー、デ・ヴェラ (1997、p. 1)

[BeckBladoCrawfordJeanLouisYoung_a-4] Beck et al. (2013, p. 4)

[BeckBladoCrawfordJeanLouisYoung_b-5] ベック他 (2013, p. 5)

[FOOTNOTECowellDawidLauritzenSpiegelhalter1999-6] Cowell et al. (1999).