モンテディック2次論理ではオイラーパス(またはオイラー周期)が定義可能ですか?

オイラー・パス(またはオイラー・サイクル)がある場合にのみグラフによって満たされるモナディック2次論理式が存在しますか?

私は多項式時間テスト可能ですが、MSOで定義することはできませんグラフのプロパティを探しています。私はCS理論の群衆ではなくCS(エンジニアリング)の群衆のためのものであるため、標準的な教科書からのプロパティの例にもっと傾いています。

ベストアンサー

パリティはMSOLで表現できません(例: http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf
)、接続性はい。代わりに$ C_2 $
MSOLを使用することで、同等の特性を使用してオイラー周期の存在を表現することができます。接続され、すべての頂点に度合いがあります。

返信を残す

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