2色グラフ

有向グラフであって頂点が2種類あり、辺も2種類あるものを考えます。つまり(V1,V2,E1,E2,s,t) なる5つの組を考えます。 そして E1 の辺は V1の頂点を始点としV2の頂点を終点とするものとし、E2の頂点は逆にV2の頂点を始点としV1の頂点を終点とするものとします。数学的に書けば

e1E1 ならば s(e1) V1 かつ t(e1)V2
e2E2 ならば s(e2)V2 かつ t(e2)V1
ここで V1 V2= E1E2= とする。

すると( (V1V2,E1E2,s,t) は通常の有向グラフになります。
ところで上のような (V1,V2,E1,E2,s,t) を2色グラフといいます。それは頂点が2色に塗られていると考えるからです(例えばV1の頂点は赤、V2の頂点は白)。あるいは下の図のようにV1の頂点をで、V2の頂点をで表すこともできます。

このようなグラフで表されるものはたくさんあります。例えば論理回路でがAND回路、がOR回路と表すと考えてもいいのです。