転置グラフ

グラフ理論の数学的およびアルゴリズム的研究では、有向グラフGの逆^{[1] 、} 転置[ ^2]または逆^[3]とは、同じ頂点セット上にある別の有向グラフで、 G内の対応する辺の向きと比較してすべての辺が逆になっているものである。つまり、Gに辺( u、v )が含まれる場合、 Gの逆 / 転置 / 逆は辺( v、u )を含み、その逆も同様である。

逆という名前は、矢印の反転が論理の含意の逆をとることに対応することから来ています。転置という名前は、転置有向グラフの隣接行列が元の有向グラフの隣接行列の 転置であるためです。

推奨される用語については一般的な合意はありません。

逆は、使用される用語と表記のソースとなる書籍または記事に応じて、 G'、G ^T、G ^{R 、またはその他の表記法で記号的に表されます。}

グラフとその転置の間に数学的な違いはほとんどありませんが、与えられたグラフがどのように表現されるかに応じて、コンピュータサイエンスでは違いが大きくなる可能性があります。たとえば、ウェブグラフの場合、頂点の出力リンクを特定するのは簡単ですが、入力リンクを特定するのは困難です。一方、このグラフの反転ではその逆が当てはまります。したがって、グラフアルゴリズムでは、グラフをそれに対して実行される操作に適した形式にするために、グラフの反転の明示的な表現を構築することが有用な場合があります。この例としては、強く連結された成分に対するKosaraju のアルゴリズムがあります。これは、深さ優先探索を2 回適用し、1 回は与えられたグラフに、2 回目はその反転に適用します。

歪対称グラフは、すべての頂点をペアにする特殊な同型性によって、自身の転置グラフと 同型となるグラフです。

二項関係の逆関係は、関連するオブジェクトの各ペアの順序を逆にする関係です。関係が有向グラフとして解釈される場合、これはグラフの転置と同じものです。特に、部分順序の双対順序は、推移的に閉じた有向非巡回グラフの転置としてこのように解釈できます。

• 逆関係 – 二項関係の要素の順序を逆にする