Matematické Fórum

MartinF22

Dobrý deň, chcel by som sa niečo spýtať k izomorfizmu grafov.Ak mám dva grafy:

//forum.matweb.cz/upload3/img/2019-01/71574_izo1.jpg

Môže byť príslušný izomorfizmus
$2\rightarrow b\\ 5\rightarrow a\\ 4\rightarrow c\\ 1\rightarrow d\\ 3\rightarrow e$ ? Tento som našiel ja, ale zdroj uvádza výsledok

Tak sa chcem spýtať, či je ten môj nesprávny alebo sú oba OK.

Ďalej by som sa chcel spýtať: Ak mám trojicu grafov ako sú tieto:
//forum.matweb.cz/upload3/img/2019-01/71908_izo3.jpg

Ak sa nemýlim, tak všetky 3 majú 3 vrcholy stupňa 4, 2 vrcholy stupňa 3, 1 vrchol stupňa 2 a 10 hrán a myslím, že by mali byť izomorfné $G_1,G_2$ , $G_1,G_3$ a $G_2,G_3$ , ale vo výsledkoch je uvedené, že izomorfné sú len $G_1,G_2$ . Kde uvažujem nesprávne?

Ďakujem.

laszky · 06. 01. 2019 13:02

↑ MartinF22:

1) Oba su OK

2) U grafu G1 a G2 je vrchol stupne dva spojen s dvema vrcholy stupne 4,
kdezto u grafu G3 je vrchol stupne 2 spojen s vrcholy stupne 3 a 4.
Takze G3 nemuze byt izomorfni s G1 ani s G2.

MartinF22

↑ laszky:
Dobrý deň, ďakujem Vám za odpoveď.
Prosím Vás mohol by som sa ešte spýtať na tieto grafy:

Dá sa to pri tomto príklade ukázať podobne, že vrcholy stupňa 3 sú spojené s vrcholmi stupňov 4 v prvom a v druhom platí, že vrcholy stupňa 3 sú spojené s vrcholmi stupňov 4,4,3 a preto nie sú izomorfné?

//forum.matweb.cz/upload3/img/2019-01/81017_eizo.jpg

A ako to je prosím v tomto prípade? Podľa výsledkov by ani jeden nemal byť izomorfný, ale každý má 10 vrcholov stupňa 3 spojených s 3 vrcholmi stupňa 3. Môže to mať niečo spoločné s tým, že prvé 2 nie sú rovinné a tretí áno?

//forum.matweb.cz/upload3/img/2019-01/81154_gizo.jpg

Ďakujem.

laszky · 06. 01. 2019 14:45

↑ MartinF22:

Vysvetleni je mozmych vetsinou vzdy nekolik, me napada

e) graf G2 (narozdil od G1) neni rovinny, protoze jako podgraf obsahuje bipartitni graf $K_{3,3}$

g) tady je tezsi rozhodnout o tom, ze grafy G1 a G2 nejsou rovinne (to, ze jsou tak nakreslene neni dukaz),
ale lehci je spocitat u vsech grafu pocet kruznic delky 4

MartinF22 · 06. 01. 2019 17:25

↑ laszky:
Aha, pri tom e.) mi to ani nenapadlo podľa toho rozhodnúť. Prosím Vás ale bolo by správne aj to kritérium s tými susednými vrcholmi, čo som napísal v ↑ MartinF22: ? Ďakujem Vám.

laszky · 06. 01. 2019 17:31

↑ MartinF22:

Ano, i to je spravne. V druhem pripade jsou vrcholy stupne tri spojeny, v prvnim nejsou ;-)

MartinF22 · 07. 01. 2019 17:59

↑ laszky:
Ok, ďakujem Vám.

Matematické Fórum

#1 06. 01. 2019 11:53 — Editoval MartinF22 (06. 01. 2019 11:55)

Izomorfizmus grafov

#2 06. 01. 2019 13:02

Re: Izomorfizmus grafov

#3 06. 01. 2019 14:26 — Editoval MartinF22 (06. 01. 2019 14:26)

Re: Izomorfizmus grafov

#4 06. 01. 2019 14:45

Re: Izomorfizmus grafov

#5 06. 01. 2019 17:25

Re: Izomorfizmus grafov

#6 06. 01. 2019 17:31

Re: Izomorfizmus grafov

#7 07. 01. 2019 17:59

Re: Izomorfizmus grafov

Zápatí