Matematické Fórum

Olin · 21. 07. 2010 20:47

Zdravím kolegy,

mám tady jednu snad poměrně snadnou úlohu. Je známo, že pro každý orientovaný graf $G = (V,E)$ platí
$\sum_{v \in V} d_{\rm{in}}(v) = \sum_{v \in V} d_{\rm{out}}(v)$ ,
kde $d_{\rm{in}}(v)$ , resp. $d_{\rm{out}}(v)$ označuje počet orientovaných hran, které do vrcholu $v$ vedou, resp. z něj vedou.

Dokažte, že pokud je $G$ nějakou orientací úplného grafu, pak platí také
$\sum_{v \in V} d_{\rm{in}}^2(v) = \sum_{v \in V} d_{\rm{out}}^2(v)$
(orientací "běžného" grafu rozumíme orientovaný graf, který z tohoto grafu vznikne nahrazením každé neorientované hrany právě jednou orientovanou hranou o libovolné orientaci).

check_drummer · 21. 07. 2010 22:37

Postupoval jsem takto:

Autor skryl část textu. Zobrazit/skrýt!

petrkovar

Můžeme postupovat i přímo.
Protože $\sum_{v \in V} d_{\rm{in}}(v) = \sum_{v \in V} d_{\rm{out}}(v) = h = n(n-1)/2$ ( $h$ je počet hran) a protože v kompletním grafu je $d_{\rm{in}}(v) = (n-1) - d_{\rm{out}}(v)$ , tak úpravou $\sum_{v \in V} d_{\rm{out}}^2(v) = \sum_{v \in V} (n-1-d_{\rm{in}}(v))^2$ dostaneme $n(n-1)^2-(n-1)2\sum_{v \in V} d_{\rm{in}}(v) + \sum_{v \in V} d_{\rm{in}}^2(v) = 0 + \sum_{v \in V} d_{\rm{in}}^2(v)$ .
V úpravě jsme nevyužili, že graf je kompletní, ale jen že je pravidelný.

Matematické Fórum

#1 21. 07. 2010 20:47

Orientace úplného grafu

#2 21. 07. 2010 22:37

Re: Orientace úplného grafu

#3 23. 07. 2010 11:03 — Editoval petrkovar (23. 07. 2010 11:06)

Re: Orientace úplného grafu

Zápatí