グラフ (離散数学)
「2部グラフ (bipartite graph)」とは、頂点集合を U {\displaystyle U} と V {\displaystyle V} の2集合に分割し、 U {\displaystyle U} 内で任意の2頂点が辺を共有することがなく、 V {\displaystyle V} 内でも任意の2頂点が辺を共有することがないようにできる単純グラフのこと。言い換えるなら、彩色数2となるグラフ。
完全2部グラフにおいて、頂点集合は2つの素集合 U {\displaystyle U} と V {\displaystyle V} の合併 (union) であり、 U {\displaystyle U} 内にある全ての頂点が V {\displaystyle V} 内にある全ての頂点と隣接しているのだが、素集合の U {\displaystyle U} 内や V {\displaystyle V} 内で完結する辺がないものをいう。
「混合グラフ (mixed graph) 」とは、一部の辺が有向、一部の辺が無向であるグラフ。混合単純グラフは順序三つ組 G = (V, E, A) である。混合複合グラフは G = (V, E, A, φE, φA) の五つ組で、V, E (無向辺), A (有向辺), φE ,φA は上述にて定義したものである。有向グラフと無向グラフは混合グラフの特殊なケースである。
グラフ理論における定義はさまざまである。以下、グラフや関連する数学的構造の定義で基本的なものを幾つか挙げる。