エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
中国人郵便配達問題 - Wikipedia
中国人郵便配達問題(ちゅうごくじんゆうびんはいたつもんだい、英: Guan's route problem)とは、グラ... 中国人郵便配達問題(ちゅうごくじんゆうびんはいたつもんだい、英: Guan's route problem)とは、グラフ理論における問題の一つであり、以下のように定義される[1][2]。 解法[編集] グラフ理論において、グラフ中のすべての辺を1度ずつ通るような閉路が存在するグラフを「オイラーグラフ」といい、その閉路を「オイラー路」という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことで、オイラーグラフが得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるため、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めることになる。 オイラーグラフの特徴として「すべての頂点の次数(頂点に接続する辺の数)は偶数である」ことが挙げられる。一般の(次数が奇数である頂点を持ちうる)グラフに対しては、以下の方法