度の合計 $\sum_{v\in V} id(v)$ とアウトディグリー $\sum_{v\in V} od(v)$ 常に等しいですか？
Dec 02 2020
私はラルフ・P・グリマルディの離散および組み合わせ数学、応用入門、第5版のセクション11.3の問題＃24に取り組んでいます。
質問：
しましょう $G=(V,E)$ 有向グラフである、ここで $|V|=n$ そして $|E|=e$。の値は何ですか$\sum_{v\in V} id(v)$ そして $\sum_{v\in V} od(v)$？
$id(v)$ そして $od(v)$ インディグリーとアウトディグリーです。
インとアウトの程度はセクション11.3の終わりに通過する際に言及されているので、この質問に答えるのは自分で任されています。
私はについて必要な事実を推測しようとしました $\sum_{v\in V} id(v)$ そして $\sum_{v\in V} od(v)$ そして、私の論理が正しいかどうか知りたいです：
有限数の頂点が与えられた $n$ 追加するすべての「有向」エッジに対して、追加します $1$ に $\sum_{v\in V} id(v)$ そして $\sum_{v\in V} od(v)$ それぞれ、そしてそれらは常に等しくなければなりませんか？
もしそうなら、 $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$
回答
1 user21820 Dec 06 2020 at 20:43
アイデアを厳密にするには、誘導を使用する必要があります。しましょう$Q(k)$ すべての有向グラフが正確に $k$エッジは目的の主張を満たします。次に、誘導を使用します$Q$。その際、あなたがないように注意してくださいない場合」のような何かを$Q(k)$ 本当なら、 $G$ 有向グラフである $k$エッジを追加してエッジを追加します...」！この誘導の説明を読んで、誘導が正しく行われていることを確認してください。