Cvičenia z Teórie Grafov
Kontakt:
Edita Máčajová, M 261, "priezvisko"@dcs.fmph.uniba.sk
cvičenia bývajú vo stredu o 9:00 v posluchárni II
Elektronické dokumenty:
Oznamy
- Body z domácich úloh nemôžem vyvesiť na stránku, lebo nemám vás písomný súhlas. Ak chcete vediet svoj počet bodov, poslite mi mail.
- Príklad z cvičení o usadení ľudí za okrúhly stôl, ktorý sa na cvičeniach nepodrilo dokončiť, nájdete tu.
Domáce úlohy
Domácu úlohu treba odovzdať vždy najneskor v uvedený deň o 9:00. Úlohy môžete
odovzdávať buď na začiatku cvičení alebo ich možete poslat mailom.
DU 1 (odovzdat do 15.10.) Dokážte, že pre ľubovoľný graf G s diam(G)>3 platí, že diam(G')<3.
// G' je graf komplementarny ku G, teda graf, ktory vznikne z G vynechaním tých hrán, ktoré tam boli a pridaním tých, ktoré tam neboli
DU 2 (odovzdat do 22.10.) Dokážte, že každý graf G obsahuje cestu dĺžky \delta(G).
// \delta(G) = minimálný stupeň grafu G
DU 3 (odovzdat do 29.10.)
Dokážte alebo vyvráťte nasledujúce tvrdenie.
Tvrdenie. Ak k>=2, potom pre každý vrcholovo k-súvislý graf platí,
že ľubovoľných k vrcholov leží na spoločnej kružnici.
DU 4 (odovzdat do 5.10.) Určte hodnotu hranovej súvislosti \lambda kompletného grafu K_n.
DU 5 (odovzdat do 12.11.)
Nech Pk oznacuje cestu dlzky k, t.j. cestu s
k hranami, k>=0, a nech # oznacuje karteziansky sucin
grafov. Pre ktore a, b, c je Pa # Pb #
Pc planarny
graf? Dokazte.
Uloha na 19.11. nebude.
DU 6 (odovzdat do 26.11.)
Dokážte, že súvislý graf s párnym počtom hrán sa dá rozložit na cesty dĺžky 2.
DU 7 (odovzdat do 3.12.)
Charakterizujte grafy, ktoré sa dajú hranovovo zafarbit dvoma farbami (nie nutne regulárne) tak, že v každom vrchole sú prítomné obe farby.
DU 8 (odovzdat do 10.12.)
Dokážte, že každý hamiltonovský graf má nikde nulový 4-tok.
DU 9 (odovzdat do 21.12. do 24:00)
Dokážte, že graf má nikde nulový k-tok práve vtedy, keď má nikde nulový Z_k-tok.