グラフ理論「サイクル」に関する問題について

グラフ理論「サイクルと強連結成分」に関する以下の問題について私の考えが正しいかどうかをご教授お願い致します。

問題
有効グラフGは，ｎ個の点からなり，かつ，長さn-1の有効パスv1→v2→…→vnをもつとする．さら
に，「Gにおいてvxからv1への有効パスが存在する」という条件を満たす番号ⅹの最大値がｋであるとする．このとき，Gにおける点v1を含む強連結成分の点集合を求めよ．

私の考え
条件からv1からvnへの有効パスが存在し，1≦k≦nを満たすkについて，vkからv1への有効パスが存在するので，｛v1，v2，…，vk｝が強連結成分だと思うのですが正しいでしょうか？

No.1 回答者： varietyknowledge 回答日時： 2018/12/13 22:42

まず、有効グラフではなく「有向グラフ」です。

以下有効⇒有向に置き換えて回答します。

質問に書かれている情報だけだと正直なんともいえません。

(1) 長さn-1の有向パスではなく、有向パス数がn-1本ではないですか？（グラフ理論では、パスの長さはあまり意味を持ちません）
(2) 有向グラフGはv1→v2→…→vnと数珠つなぎのツリーグラフ構造ですか？
(3) vxは複数の頂点の集合と捉えれば良いですか？

仮に(1)～(3)がすべてYESであれば、｛v1，v2，…，vk｝が強連結成分になります。
強連結成分分解は、有向グラフの構造がとても重要で、ここがはっきりしないと正しい答えが導けません。