![](https://cdn-ak-scissors.b.st-hatena.com/image/square/b7fda7023c98a55c763809579734ab025d6aaaac/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9T3JlJUUzJTgxJUFFJUU1JUFFJTlBJUU3JTkwJTg2JUUzJTgxJUFFJUU4JUE4JUJDJUU2JTk4JThFJUUzJTgxJUFCJUU5JTk2JUEyJUUzJTgxJTk5JUUzJTgyJThCJUUzJTgzJUExJUUzJTgzJUEyJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz1iMmQ1NDY1YzExYzQxYzE2MTQ0MTcwMDA4ZmNlYzc3Zg%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwa291c2FrdWluLUEmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT0zMiZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPWQ2OTJmZWJmYTAxMTkyYjQ0NmFmMGE2OGU4YjI4MDg2%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D4266107883bc01ef172437f1a9020cb8)
エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Oreの定理の証明に関するメモ - Qiita
北大 井上先生の講義ノートを教科書としてグラフ理論を勉強中。 Oreの定理の証明がよくわからなかったの... 北大 井上先生の講義ノートを教科書としてグラフ理論を勉強中。 Oreの定理の証明がよくわからなかったので調べていたところ、motchy氏のわかりやすい証明を見つけたのだが、一箇所難しいところがあったのでメモを残す。 https://motchy99.blog.fc2.com/blog-entry-40.html 然るに定理の仮定から$n(A)+n(B) \ge n$であるので$A$と$B$は共通部分を持つ,すなわち、ある$i (0 \le i \le k-1)$が存在して$u_i$は$u_k$の隣接接点で、$u_{i+1}$は$u_0$の隣接接点である。 (太字強調は筆者による) に関しては、太字部分が仮に成立しないとすると、Bに含まれる点はAの点の隣には置けないので、$n(A)$個だけ候補となる点が減って、$n(B) \le k-n(A)$となる。一方で$n(A)+n(B) \ge n