k-connectedグラフもk-1に接続されていますか?

だから私はk-connectedグラフについて読んでいます。私はそれらについて少し混乱しています。これは私が見た主な定義です:

グラフ内の任意の別個のx、y頂点についてのみ、グラフ内のxからyまでのk個の内部的に分離した経路が存在する

これは、k接続されたグラフがk-1接続されたグラフであると考えることができます。なぜなら、k接続されていればk個の内部に無関係なパスが存在しなければならないからです。
k-1接続)。 これは本当ですか?または私は何かを逃していますか?

ベストアンサー

はい、これは典型的な用語です。グラフがk接続されるように一意の最大kを参照したい場合は、それを接続と呼びます。したがって、k連結グラフは(k-1)連結であるが、連結性kを有するグラフは連結性k-1を有するとは言えない。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です