1

私はグラフ理論にかなり慣れていないので、グラフの強結合コンポーネントに関して非常に基本的な疑問を持っています。両方のノードから相互にパスが存在する場合、2 つ以上のノードが強く接続されていると言います。では、このグラフがサイクルを含む循環グラフと見なされるかどうかは?

4

1 に答える 1

2

はい、強く接続されたグラフは循環的です。このようなグラフでは、任意の 2 つの頂点、たとえばuとが強く接続されているため、有向辺で構成されるからへのパスと からへvのパスが存在します。パスとパスが切り離されている場合は、それらを連結するとサイクルができます。エッジを共有している場合は、そこから開始してパスをたどります。2 つのパスが共有する最初のエッジに到達したら、に戻るまでパスをたどります。uvvuu->vv->uuu->vv->uu

于 2012-07-31T22:21:36.357 に答える