Jumlah dalam derajat $\sum_{v\in V} id(v)$ dan derajat keluar $\sum_{v\in V} od(v)$ selalu sama?

Question

Saya sedang mengerjakan Soal # 24 dari bagian 11.3 Matematika Diskrit dan Kombinatorial Ralph P. Grimaldi, Pengantar Terapan, edisi kelima.

Pertanyaan:

Membiarkan $G=(V,E)$ menjadi grafik terarah, di mana $|V|=n$ dan $|E|=e$. Untuk apa nilainya$\sum_{v\in V} id(v)$ dan $\sum_{v\in V} od(v)$?

$id(v)$ dan $od(v)$ adalah derajat masuk dan derajat keluar.

Derajat masuk dan keluar disebutkan secara sepintas di akhir bagian 11.3, jadi seseorang dibiarkan sendiri untuk menjawab pertanyaan ini.

Saya mencoba menyimpulkan fakta yang diperlukan tentang $\sum_{v\in V} id(v)$ dan $\sum_{v\in V} od(v)$ dan saya ingin tahu apakah logika saya benar:

Diberikan jumlah simpul yang terbatas $n$ untuk setiap tepi 'diarahkan' yang Anda tambahkan yang Anda tambahkan $1$ untuk $\sum_{v\in V} id(v)$ dan $\sum_{v\in V} od(v)$ masing-masing, dan mereka harus selalu sama?

Jika demikian, maka $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Untuk membuat ide Anda kuat, Anda perlu menggunakan induksi. Membiarkan$Q(k)$ menjadi pernyataan bahwa setiap grafik diarahkan dengan tepat $k$tepi memenuhi klaim yang diinginkan. Kemudian gunakan induksi$Q$. Saat melakukannya, berhati-hatilah agar Anda tidak melakukan hal seperti "Jika$Q(k)$ benar, lalu biarkan $G$ menjadi grafik berarah dengan $k$tepi dan tambahkan tepi ... "! Baca penjelasan induksi ini untuk memastikan Anda melakukan induksi dengan benar.