algorithm - グラフ - 有向グラフの二乗

Question

はい、これは宿題になります (私は大学のためではなく独学です) 質問ですが、解決策を求めているわけではありません。代わりに、質問自体を明確にしたいと考えています。

CLRS第 3 版、593 ページ、物品税 22.1-5、

有向グラフ G = (V, E) の 2 乗はグラフ G ² = (V, E ² )であり、G がu の間に最大で 2 つのエッジを持つパスを含む場合にのみ、(u,v) ∈ E ²となります。と v。G の隣接リスト表現と隣接行列表現の両方について、G からG ²を計算するための効率的なアルゴリズムを説明してください。アルゴリズムの実行時間を解析してください。

ただし、CLRS の第 2 版 (本のリンクが見つかりません) の 530 ページでは、同じ演習ですが、説明が少し異なります。

有向グラフ G = (V, E) の 2 乗はグラフ G ² = (V, E ² ) であり、(u,w) ∈ E ²は、ある v ∈ V に対して両方の (u,v ) ∈ E および (v,w) ∈ E.つまり、Gが u と wの間にちょうど 2 つのエッジを持つパスを含むときはいつでも、G 2 は u と w の間にエッジを含み^ます。G の隣接リスト表現と隣接行列表現の両方について、G からG ²を計算するための効率的なアルゴリズムを説明してください。アルゴリズムの実行時間を解析してください。

「正確に2つのエッジ」を使用した古い演習については、理解して解決できます。たとえば、adjacency-list の場合、v->neighbour->neighbour.neighbour を実行し、(v, neighbour.neighbour) を新しい E ²に追加します。

しかし、「最大で 2 つのエッジ」を使用する新しい演習については、私は混乱しています。

「G に u と v の間に最大で 2 つのエッジがあるパスが含まれている場合のみ」とはどういう意味ですか?

1 つのエッジが「最大で 2 つのエッジ」という条件を満たすことができるため、u と v が 1 つのエッジのみを含むパスを 1 つしか持たない場合、E ²に (u, v) を追加する必要がありますか?

u と v に 2 つのエッジを持つパスがあり、3 つのエッジを持つ別のパスもある場合、 (u, v) を E ²に追加できますか?

Answer 1

はい、それはまさにそれが意味することです。との両方を含むように、を含むか、を含むE^2必要があります。(u,v)E(u,v)wVE(u,w)(w,v)

言い換えれば、新しい定義によると、古い定義E^2の結合Eとそれによるものです。E^2

あなたの最後の質問に関して：他にどのようなパスが存在するかは関係ありませんu（v存在する場合）。したがって、との間に2つのパスがuありv、1つは2つのエッジを持ち、もう1つは3つのエッジを持つ(u,v)場合、E^2（両方の定義に従って）にある必要があります。