問題

提出解答

単純有向グラフ $D=(V,A)$ がある. ただし,

このとき, 以下の条件を満たすためには, $D$ に最小で何本の有向辺を追加しなければならないか?

$a,b,c \in V~(a \neq b, b \neq c, a \neq c)$ に対して, $\overrightarrow{ab}, \overrightarrow{bc} \in A$ ならば, $\overrightarrow{ac} \in A$ .

最終的な有向グラフ $D'=(V,A')$ は以下のようになる.

$a,b \in V~(a \neq b)$ に対して, $\overrightarrow{ab} \in A'$ であることと, $D$ において, $a$ から $b$ へ到達可能であることが同値になる.

実際, この $D'$ は条件を満たしている.

そして, $a \in V$ から到達可能な $b \in V$ において, $a$ から $b$ への有向パスを $a,p_1,p_2, \dots, p_{m-1}, b$ とする. このとき,

$\overrightarrow{ap_1}, \overrightarrow{p_1p_2} \in A$ なので, $\overrightarrow{ap_2} \in A'$ である.
$\overrightarrow{ap_2}, \overrightarrow{p_2p_3} \in A$ なので, $\overrightarrow{ap_3} \in A'$ である.
$\vdots$
$\overrightarrow{ap_{m-1}}, \overrightarrow{p_{m-1}b} \in A$ なので, $\overrightarrow{ab} \in A'$ である.