Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Hezký novoroční večer :),
chtěla bych dokázat, že kartézským součinem dvou bipartitních grafů vznikne opět bipartitní graf.
Řekněme, že mám dva bipartitní grafy a , kde a . S tím, že množina je množina vrcholů 1. barvy a množina je množina vrcholů 2. barvy. Obdobně u množin a .
Množina vrcholů kartézského součinu: .
Vrcholy z množiny mohou sousedit s vrcholy z množin a , jednou "zafixuji" první souřadnici, v dalším případě druhou souřadnici.
Takto zjistím, že mezi množinami a neexistuje hrana, tedy je mohu obarvit první barvou. Obdobně mezi množinami a neexistuje hrana, tedy je mohu obarvit druhou barevnou.
Je to takhle korektní :)?
Offline
no je spravne to co tvrdis, t.j. ze ten graf mozes rozdelit na a ale to tvoje zdovodnenie je tak trochu nezrozumitelne - ja by som ako vyucujuci vyzadoval trochu formalnejsi sposob vyjadrovania; napr. takto:
predpokladajme, ze 2 rozne vrcholy v su susedne t.j. bud
a) susedi s - potom ale by platilo bud alebo lenze ani jedno nemoze nastat
alebo
b) susedi s - potom bud a susedi s - co znova nemoze nastat, lebo je jedna z "polovic" bipartitnrho grafu; alebo a susedi s - co nemoze nastat s obdobneho dovodu
alebo
c) susedi s - co nemoze nastat analogicky ako pre pripad b)
teda ziadne 2 vrcholy v nemozu byt susedne a rovnaky argumen je aj pre to, ze ziadne 2 vrcholy v nemozu byt susedne. QED.
Offline
Stránky: 1