Kombinatorika a grafy II - Hubička 30. 1. 2019

Vše co není uvedeno jinde

Kombinatorika a grafy II - Hubička 30. 1. 2019

Příspěvekod NeverNotBluu » 31. 1. 2019 14:38

1) Formulujte a dokažte Tutteovu větu.
2) Nechť G je 42-regulární graf se 123 vrcholy. Dokažte, že G má hranovou barevnost 43.

Řešení 2:
Kdyby měl barevnost 42, každá barva by z regularity musela tvořit hrany perfektního párování (snadné rozmyslet), které ale lichý graf nemůže mít. Z Vizingovy věty tedy musí mít barevnost 43.
NeverNotBluu
Matfyz(ák|ačka) level I
 
Příspěvky: 10
Registrován: 4. 6. 2018 18:43
Typ studia: Informatika Bc.

Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník