向圖的財產

Question

請幫我解決這個問題：

給弱連接的，簡單的，有向圖G.求證：S = SUM（ABS（degIn（U）-degOut（U）））是甚至。

非常感謝。

Answer 1

顯然，對於任何沒有邊的圖G來說，這種說法是正確的。

假設G是一個至少有一條邊的圖。假設e =（u，v）是G中的任意邊。假設G - e滿足該性質。現在檢查G.在G-e和G之間，對於除u和v以外的所有頂點，abs（degin（w） - degout（w））的值保持不變。u和v的值都改變了1，總的變化爲-2,0或2.因此，對於G，總和（abs（degin（w）-degout（w））是偶數。通過對G中邊數的歸納，所有圖G滿足財產。