Matematické Fórum

serillan

Potrebujem urobiť tento dôkaz ale nejak nemôžem prísť na správne riešenie:
Pre každý vrchol U orientovaného grafu s vrcholmi $U_{1},U_{2},...,U_{n}$ označme $s_{+}(U)$ počet hrán, ktoré vchádzajú do vrcholu $U$ , a $s_{-}(U)$ počet hrán, ktoré z neho vychádzajú.
Dokážte že: $\sum_{i=1}^{n} |(s_{+}(U_{i})-s_{-}(U_{i})|$ je párne číslo.
Zatiaľ som došiel k tomu, že keby sme odstránili absolútne hodnoty, dostali by sme súčet 0.

standyk · 24. 12. 2012 21:53

↑ serillan:

Ahoj, skúsil by som to možno sporom.
Predpokladajme, že výsledok je nepárny. Potom ale tá suma musí obsahovať nepárny počet členov, pre ktore je tá absolútna hodnota nepárne číslo. Lenže $|(s_{+}(U_{i})-s_{-}(U_{i})|$ je nepárne číslo práve vtedy, ak aj $|(s_{+}(U_{i})+s_{-}(U_{i})|$ je nepárne číslo. Došiel si teda ku grafu, ktorý má nepárny počet vrcholov nepárneho stupňa. Čo je spor.

serillan · 25. 12. 2012 10:21

Ďakujem za dôkaz. Urobil som to už aj priamo:
Označme si celý výraz ako $S$ a vieme že $\sum _{s\in S} s = 0$ . $S$ môžeme rozdeliť na $S_+ = \{s\in S : s\geq 0\}$ a $S_- = \{s \in S : s < 0\}$ . Potom máme $\sum _{s\in S} s = \sum _{s\in S_+} s + \sum _{s\in S_-} s = \sum _{s\in S_+} |s| - \sum _{s\in S_-} |s| = 0 \$ Z toho vyplýva $\sum _{s\in S_+} |s| = \sum _{s\in S_-} |s|$ . Nakoniec $\sum _{s\in S} |s| = \sum _{s\in S_+} |s| + \sum _{s\in S_-} |s| = 2\sum _{s\in S_+} |s|$ .

Matematické Fórum

#1 24. 12. 2012 14:53 — Editoval serillan (24. 12. 2012 15:43)

Grafová úloha (dôkaz)

#2 24. 12. 2012 21:53

Re: Grafová úloha (dôkaz)

#3 25. 12. 2012 10:21

Re: Grafová úloha (dôkaz)

Zápatí