\input /home/pasky/school/fastex/lib.tex

\subchapter{Věta o sudosti (princip sudosti)}{

	$$ \forall G = (V,E):\ \sum_{v\in V} \deg_{G}(v) = 2|E| $$

\proof{
	Vlevo každá hrana přispěje $2\times$.
	\qed
}

\scpart{Důsledek:}{
	$\forall G$: počet vrcholů lichého stupně je sudý.
}

\note{
	Neplatí pro nekonečné grafy ({\tt o-o-o-o-$\cdots$}).
}

}


\asciiart{
    o
  /   \
o ----- o ----- o ----- o
}


\subchapter{Skóre grafu}{

	$$ G = (\{v_{1}, \ldots, v_{n}\}, E), \textbox{\bf skóre grafu G} = D(G) = (\deg_{G}(v_{1}), \ldots, \deg_{G}(v_{n})) $$

	Dvě skóre považujeme za stejná, pokud se liší pouze pořadím prvků.

\scpart{Příklad:}{

	\asciiart{
    o
  /   \
o ----- o ----- o ----- o
}
	má skóre $(1,2,2,2,3)$.

	\asciiart{
    o
  /   \
o - o - o - o
}
	k němu není izomorfní.
}

\scpart{Věta o skóre:}{

	$$ D = (d_{1}, \ldots, d_{n},\ 0 \le d_{1} \le \cdots \le d_{n}) $$

	$D$ je skóre nějakého grafu, právě když
	$$D'=(d_{1}, \ldots, d_{n-d_{n}-1}, d_{n-d_{n}} - 1, \ldots, d_{n-2}-1, d_{n-1}-1)$$
	je skóre nějakého grafu.

\scpart{Příklady použití:}{
	Je $(1,2,3,3,3,4,4)$ skóre nějakého grafu?

	$(1,2,2,2,2,3)$ skóre nějakého grafu?

	$$(1,2,1,1,1)$$
	$$(1,1,1,1,2)$$
	$$(1,1,0,0) \Leftrightarrow (0,0,1,1)$$
	$$(0,0,0)$$\nobreak je skóre grafu.

	Je $(1,1,1,2)$?
	$$(1,0,0)$$
	$$(0,0,1)$$
	$$(0,-1)$$\nobreak není.

	Je $(0,1,2,3,4,4)$?
	$$(0,0,1,2,3)$$
	$$(0,-1,0,1)$$
}

\proof{
	\proofleftimpl{

	$G'$ má skóre $D'$. Přidáme ke $G'$ nový vrchol $v_{n}$ a spojíme ho
	hranou s vrcholy $v_{n-1}$, $v_{n-2}$, $\ldots$, $v_{n-d_{n}}$. Dostáváme tak
	graf se skóre $D$.

	}


	\proofrightimpl{

	Předpokládáme, že $G=(\{v_{1}, \ldots, v_{n}\}, E)$ má skóre $D$.
	Označme $d = d_{n} = \deg v_{n}$.

	{\bf První případ:} Z $v_{n}$ vedou hrany do vrcholů $v_{n-1},v_{n-2},\ldots,v_{n-d}$.
	Odstraněním $v_{n}$ pak z těchto hran dostaneme graf se skóre $D'$.

	{\bf Druhý případ:} Neplatí první případ, tedy potom je vrchol $v_{n}$ propojen
	s jinými vrcholy, než je posledních $d_{n}$, neboli:
	$$ i < n-d \le j:\ \{v_{i}, v_{n}\} \in E,\ \{v_{j}, v_{n}\} \nin E $$

	Ale protože $\deg v_{i}$ $(= d_{i})$ $\le \deg v_{j}$ $(= d_{j})$, existuje
	$v_{k}$ $(k \not= i,j)$ takový, že $\{v_j, v_k\} \in E$, $\{v_i, v_k\} \nin E$
	(tedy existuje zase nějaký vrchol $v_k$ takový, který je spojený s $v_j$,
	ale ne $v_k$ a tím se stupeň kompenzuje).

	Přidáme do $E$ hrany $\{v_i,v_k\}, \{v_j, v_n\}$, odebereme z $E$ hrany
	$\{v_i, v_n\}, \{v_j, v_k\}$. Skóre tak zůstává $D$, ale zmizela neposedná
	hrana mimo posledních $d_n$ prvků (vrcholy $v_i, v_j$ jsme místo přes $v_n$
	spojili přes $v_k$). Převedli jsme tedy situaci na první případ.

	}

	\qed

}

}

}

\bend