data-structures - 非巡回接続無向グラフとは何ですか?

Question

最小全域木の講義を行っていましたが、無向グラフで接続された非巡回部分グラフグラフを見つけることになっていると書かれています。

私の質問は、接続された無向グラフがどのようにして非巡回になるかということです。接続されているため、任意の頂点から任意の頂点に移動できます。

誰が私が間違っているのか教えてもらえますか?

Answer 1

それは本当に単なる定義の問題です。http://en.wikipedia.org/wiki/Cycle_(graph_theory)を参照してください。あなたがサイクルと呼んでいるように見えるのは、この記事で閉じたウォークと呼ばれるものです。頂点からそれ自体への任意のパスです。あなたが言ったように、その定義を使用すると、接続された無向グラフにはサイクルが含まれます。ただし、2 番目から最後の頂点までのサブパスが単純なパス (したがって単純なサイクル) である必要がある場合、つまり頂点の繰り返しを含まないパスである場合、多くの接続された無向グラフが実際には循環していないことになります。実例。明らかに、パスには少なくとも 3 つのエッジも含まれている必要(A,B,A)があります。

次のグラフを検討してください

     A         A
1)  / \   2)  / \
   B   C     B - C

2)単純なサイクルのみを含むため1)、非環状です。