[quote="matko-matkovic"]Jel bi mogo netko objasnit kako se rjesava ovaj zadatak?
8. Dokazite da ako je graf G nepovezan, onda je njegov komplement Gc
povezan. Vrijedi li obrat?
ne cini se tesko, nesto mi je promaklo.
Thx![/quote]
Uzmi bilo koja dva vrha A i B. Dokazujem da postoji put od A do B u grafu Gc.
Ako brid A--B ne pripada G, onda pripada Gc pa je to trazeni put.
Ako pak brid A--B pripada G, onda uzmimo neki C koji nije povezan sa A i B u grafu G. Sad je A--C--B trazeni put u Gc.
Obrat ne vrijedi jer G i Gc mogu oba biti povezani. Uzmi npr V = {a, b, c, d}, G sadrzi bridove {ab, bc, cd}, Gc sadrzi bridove {ad, ac, bd}.
matko-matkovic (napisa): | Jel bi mogo netko objasnit kako se rjesava ovaj zadatak?
8. Dokazite da ako je graf G nepovezan, onda je njegov komplement Gc
povezan. Vrijedi li obrat?
ne cini se tesko, nesto mi je promaklo.
Thx! |
Uzmi bilo koja dva vrha A i B. Dokazujem da postoji put od A do B u grafu Gc.
Ako brid A–B ne pripada G, onda pripada Gc pa je to trazeni put.
Ako pak brid A–B pripada G, onda uzmimo neki C koji nije povezan sa A i B u grafu G. Sad je A–C--B trazeni put u Gc.
Obrat ne vrijedi jer G i Gc mogu oba biti povezani. Uzmi npr V = {a, b, c, d}, G sadrzi bridove {ab, bc, cd}, Gc sadrzi bridove {ad, ac, bd}.
|