Matematické Fórum

Holography · 22. 11. 2008 21:14

Zdravím, chtěl bych vás požádat o pomoc s řešením následujících příkladu do diskrétní matematiky (teorie grafů):

1) Dokažte, že pro každé dva grafy G a H platí:

(Symbol $\overline{G}$ značí doplňek grafu G, symbol relaci izomorﬁsmu.)
2) Graf nazveme k-regulární, pokud stupeň každého vrcholu je právě k. Rozhodněte následující:
a) Je pravda, že každé dva (n − 1)-regulární grafy na n vrcholech jsou izomorfní?
b) Je pravda, že každé dva (n − 2)-regulární grafy na n vrcholech jsou izomorfní?
3) Existuje graf na n > 1 vrcholech, jehož všechny stupně jsou různé?

ad 1) nevím jak napsat důkaz tohoto tvrzení

ad 2a) myslím že ano, protože každé dva (n − 1)-regulární grafy na n vrcholech jsou jsou úplné a úplné grafy na n vrcholech jsou izomorfní, je to správně?

ad 2b) myslím že ne, pokud by to byla pravda znamenalo by to že neexistují dva (n-2)-regulární grafy , které nejsou izomorfní. Pro n=4 jsou dva grafy které jsou 2-regulární následující:
$V(G)\in\{{a},{b},{c},{d}\}$
$E(G)\in\{({a},{b}),({a},{c}),({b},{d}),({c},{d})\}$
${a}\Rightarrow{w},{b}\Rightarrow{x},{c}\Rightarrow{y},{d}\Rightarrow{z}$
$V(H)\in\{{w},{x},{y},{z}\}$
$E(H)\in\{({w},{y}),({w},{z}),({x},{y}),({x},{z})\}$
Oba tyto grafy jsou 2-regulární ale nejsou izomorfní, proto nemůže uvedení tvrzení platit a odpověď na otázku je tedy ne nejsou.

ad 3) myslím, že neexistuje, ale nevím jak to dokázat

Předem díky za pomoc

jarrro · 24. 11. 2008 08:20 — Editoval jarrro (24. 11. 2008 08:33)

neviem to vyriešiť teória grafov ma nezaujíma a neviem ju tak dobre ako by som možno mal vedieť,ale viem ,že ten príklad neizomorfných grafov je zlý,lebo sú izomorfné skús uvažovať zobrazenie $\phi$a$=x\nl\phi$b$=y\nl\phi$c$=z\nl\phi$d$=w$ napísanie množiny nemusí zachovávať poradie prvkov
edit: toto platí ak myslíme neorientované grafy ak orientované tak asi nie sú izomorfné
edit2: k tej 3 podľa mňa ak slučky nepovažujeme za hrany tak neexistuje ak považujeme tak existuje napr 3 vrcholový graf V(G)={1;2;3} E(G)={(1;2);(2;2);(2;3);(3;3)} pri ktorom deg(1)=1;deg(2)=3;deg(3)=2

Kondr · 24. 11. 2008 11:26

ad 3) stupeň vrcholu může být nejméně 0 a nejvýše n-1, všechny tyto stupně proto musí být využity. Vrchol stupně 0 není spojen s vrcholem stupně n-1, ten je tedy spojen jen s n-2 vrcholy, spor.

ad 1)Nechť H,G jsou grafy na n vrcholech a f je izomorfizmus z G do H. Chceme ukázat, že f je také izomorfizmem mezi jejich doplňky.
Pokud hrana (x,y) leží v doplňku G, pak (x,y) neleží v G, protože f je izomorfizmus tak (f(x),f(y)) neleží v H, takže (f(x),f(y)) leží v doplňku H.
Z definice doplňku a definice izomorfizmu plyne, že implikace v předchozí větě platí i obráceně, f je proto izomorfizmus doplňků.

ad 2b) Tvoje řešení není správné -- je potřeba buď dokázat, že každé dva takové grafy izomorfní jsou, nebo najít dvojici grafů takovou, že mezi nimi není žádný izomorfizmus. Ty jsi akorát ukázal, že a=>w, b=>x, ... není izomorfizmus.

V tomhle případě zkus dokázat, že izomorfní jsou a to pomocí tvrzení 1) -- popiš, jak vypadají jejich doplňky a ukaž, že jsou izomorfní.

Matematické Fórum

#1 22. 11. 2008 21:14

Teorie grafů - 3 úlohy

#2 24. 11. 2008 08:20 — Editoval jarrro (24. 11. 2008 08:33)

Re: Teorie grafů - 3 úlohy

#3 24. 11. 2008 11:26

Re: Teorie grafů - 3 úlohy

Zápatí