混合グラフ

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

定義と表記法

隣接する頂点を考慮する $u,v\in V$ 有向エッジ（アークとも呼ばれる）は、方向を持つエッジであり、次のように表すことができる。 ${\overrightarrow {uv}}$ または $(u,v)$ （ご了承ください $u$ 尻尾と $v$ は弧の頭です）。^{[ 2 ]}また、無向辺、または辺は、向きのない辺であり、次のように表すことができます。 $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$ 彩色とは $、$ $[$ $k$ $]$ $:= {1, 2, \dots,$ $k$ $}$ である関数c $:$ $V \to [$ $k$ $]であり、$ $uv$ $\in$ $E$ の場合 $c$ $($ $u$ $) \neq$ $c$ $($ $v$ $)$ であり、v ≠ u の場合 $c$ $($ $u$ $) <$ $c$ $($ $v$ $)$ である。 ${\overrightarrow {uv}}\in A$ [ ¹^]

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

数える

$混合グラフには彩色が存在する場合と存在しない場合がある。混合グラフがk$ 彩色を持つためには、グラフに有向サイクルが含まれていてはならない。^{[ 2 ]} $このようなk$ 彩色が存在する場合、グラフを適切に彩色するために必要な最小の $kを$ 彩色数 $χ (G)$ と呼ぶ。^{[ 2 ]} $適切なk$ 彩色の数は $、$ グラフ $Gの$ 彩色多項式と呼ばれる $k$ の多項式関数であり(無向グラフの彩色多項式との類推による)、 $χG$ $($ $k$ $)$ と表すことができる。^[¹^]

弱彩色多項式の計算

削除縮約法は、混合グラフの弱彩色多項式を計算するために使用できます。この方法は、エッジまたはアークを削除（つまり除去）し、そのエッジまたはアークに接続する残りの頂点を結合して 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 ら^[⁴^]の命題から、混合グラフの彩色多項式を計算するための次の式が得られます。^[⁵^]

$\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 つのタスクが互換性がない (同時に実行できない) という制約をモデル化できます。有向エッジを使用して、あるタスクが別のタスクより先に実行されなければならないという先行制約をモデル化できます。このようにしてスケジューリング問題から定義されたグラフは、分離グラフと呼ばれます。混合グラフ彩色問題は、すべてのタスクを実行するための最小長のスケジュールを見つけるために使用できます。^{[ 2 ]}

ベイズ推論

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

街路網

街路や道路のシステムは、相互接続された混合エッジとノードによって表現することができ、有向エッジは一方通行の道路を、無向エッジは双方向の道路を表す。

参考文献

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。
Cowell, Robert G.; Dawid, A. Philip ; Lauritzen, Steffen L .; Spiegelhalter, David J. (1999), Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks , Springer-Verlag New York, p. 27, doi : 10.1007/0-387-22630-3 (2025年7月12日非アクティブ)、ISBN 0-387-98767-3{{citation}}: CS1メンテナンス: DOIは2025年7月現在非アクティブです（リンク）
Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique (1997)、「混合グラフ彩色」、Mathematical Methods of Operations Research、45 (1): 145–160、doi : 10.1007/BF01194253、MR 1435900 。
Ries, B. (2007)、「混合グラフのいくつかのクラスの彩色」、Discrete Applied Mathematics、155 (1): 1–6、doi : 10.1016/j.dam.2006.05.004、MR 2281351 。

外部リンク

ワイススタイン、エリック W. 「混合グラフ」 . MathWorld .

[BeckBladoCrawfordJeanLouisYoung-1] 1 2 3 4 Beck et al. (2013 、p. 1)

[Ries-2] 1 2 3 4 5リース（2007年、1ページ）

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

[BeckBladoCrawfordJeanLouisYoung_a-4] 1 2 Beck et al. (2013 、p. 4)

[BeckBladoCrawfordJeanLouisYoung_b-5] Beck et al. (2013 , p. 5)

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

[

[ 2 ]

[ 3 ]

[ 4 ]

[

[