Matematické Fórum

Ryco · 25. 01. 2012 22:20

Zadání: Nalezněte alespoň 2 neizomorfní grafy se stupňovou posloupností (5,5,4,4,3,2,2,1). Zdúvodněte, proč jsou neizomorfní.

Řešení:
Pomocí věty HH si zjistím jestli je tato posloupnost grafová
$(5,5,4,4,3,2,2,1)=(4,3,3,2,2,1,1)=(2,2,1,1,1,1)=(1,1,1,1,0)=(1,1,0,0)=(0,0,0)$

Potom si nakreslím jeden graf s touto posloupnosti (5,5,4,4,3,2,2,1):

Jenže tady sem skončil, protože nvm jak nakreslit graf jiný jestli můžu použít třeba posloupnost (4,3,3,2,2,1,1) nebo mám zase použit tu samou (5,5,4,4,3,2,2,1) a jen z přeházet body na jiné místa.

Jak potom dokázat ten izomorfismus bych už věděl (pomocí délky cest a cyklů)

Gerlige · 25. 01. 2012 22:33

Ten druhý graf musí mít stejnou stupňovou posloupnost, skóre. Totiž úpravou skóre pomocí zmíněné věty dostáváš skóre jiného grafu, tato skóre se rozhodně nerovnají.

Doporučuji použít stejnou množinu vrcholů jako u grafu, který už jsi nakreslil a jen "vyměnit" některé hrany. Doufám, že je zřejmé, co mám na mysli.

Ryco · 25. 01. 2012 22:36 — Editoval Ryco (25. 01. 2012 22:48)

↑ Gerlige:
jj prostě nakreslit to samé z posloupnosti (5,5,4,4,3,2,2,1) ale trosku jinak

EDIT:
stačí,provést jen takováto malá změna?

Gerlige

↑ Ryco: Určitě, tyto grafy už nejsou isomorfní.

Jednoduše se můžeme podívat třeba na vrchol stupně jedna, ten je v grafu pouze jeden, tudíž se musí zobrazit na sebe. Tady je ale v každém grafu spojen hranou s vrcholem jiného stupně, proto mezi těmito grafy neexistuje zobrazení zachovávající strukturu grafu, tudíž nejsou isomorfní.

Ryco · 25. 01. 2012 22:56

jj každý ma jinou délku nejdelšího cyklu. díky za spolupráci:-)

Matematické Fórum

#1 25. 01. 2012 22:20

Izomorfismus grafu

#2 25. 01. 2012 22:33

Re: Izomorfismus grafu

#3 25. 01. 2012 22:36 — Editoval Ryco (25. 01. 2012 22:48)

Re: Izomorfismus grafu

#4 25. 01. 2012 22:52 — Editoval Gerlige (25. 01. 2012 22:55)

Re: Izomorfismus grafu

#5 25. 01. 2012 22:56

Re: Izomorfismus grafu

Zápatí