Deadline: 2021-11-30 23:59 (400 days ago)
Martin Koutecký — 2021-11-23 15:53 (408 days ago) — reply
### Nezávislá množina a vrcholové pokrytí **Definice:** Nechť je $G=(V,E)$ graf a $V' \subseteq V$. Řekneme, že $V'$ je *nezávislá množina*, pokud $\forall u,v \in V': uv \not\in E$, tedy mezi žádnými dvěma vrcholy $V'$ nevede hrana. Dokažte, že pro každý graf $G$ platí, že $U \subseteq V(G)$ je nezávislá množina právě tehdy, když $V(G) \setminus U$ (doplněk $U$) je vrcholové pokrytí. Množina $C \subseteq V(G)$ je vrcholové pokrytí grafu $G$ pokud pro každou hranu $uv \in E(G)$ platí, že $u \in C$ nebo $v \in C$
Santa Claus — 2021-11-25 18:05 (405 days ago) — edit — reply
$U$ je nezávislá množina $\iff \nexists xy \in E(G): x \in U \wedge y \in U\iff \forall xy \in E(G): x \notin U \vee y \notin U \iff \forall xy \in E(G): x \in \overline{U} \vee y \in \overline{U} \iff \overline{U}$ je vrcholové pokrytí