Matematické Fórum

SweetNelli · 09. 12. 2009 17:54

1)Dokažte, že každé dva n - 1 regulární grafy na "n" vrcholech jsou izomorfní.
2)Dokažte, že každé dva n - 2 regulární grafy na "n" vrcholech jsou izomorfní.

Mohla bych se zeptat jak toto dokázat?

check_drummer · 09. 12. 2009 18:45

Co je n-1 regulární graf?

petrkovar · 09. 12. 2009 21:10

Formálně se vevmou dva takové grafy a zkonstruuje se isomorfismus, což bijekce mezi množinami vrcholů, která zachová sousednoust mezi každou dvojicí vrcholů.
Nejjednodušší argumentace je přes doplněk grafu. Nevím ale, zda jste doplněk brali.

FabulousDeniska · 09. 12. 2009 21:11

↑ petrkovar:

ano brali, ukázal bys mi tedy jak to přes ten doplněk ukázat?

petrkovar · 09. 12. 2009 21:24

↑ FabulousDeniska:Jen naťuknu: co je doplněk (n-1)-regulárního grafu na n vrcholech? Kolika regulární je doplněk? Existují DVA grafy takové jako je doplněk?
Pro (n-2)-regulární graf ro je mírně komplikovanější. Takový graf existuje jen pro n sudé (proč?) A zdůvodní se, že doplněk (n-2)-regulárního grafu je vždy graf 1-regulární a ten je zase až na isomorfismus jediný.

Kondr · 09. 12. 2009 21:46

↑ SweetNelli:Tato úloha už se tu jednou řešila: http://forum.matweb.cz/viewtopic.php?id=4968

SweetNelli · 10. 12. 2009 18:55

↑ Kondr:

ano to máš pravdu, návod je tam sepsán , ale po pravdě se ty příklady vůbec nedořešili, což je škoda, když člověk netuší jak to ukázat správně

Kondr · 10. 12. 2009 19:44

↑ SweetNelli: Jo, vím. Ale návod zde ↑ petrkovar: mi připadá velmi snadno uchopitelný, v odkazovaném tématu považuju za relevantní akorát rozepsání důkazu toho, že izomarofizmus grafů znamená izomorfizmus doplňků.

Matematické Fórum

#1 09. 12. 2009 17:54

izomorfní grafy

#2 09. 12. 2009 18:45

Re: izomorfní grafy

#3 09. 12. 2009 21:10

Re: izomorfní grafy

#4 09. 12. 2009 21:11

Re: izomorfní grafy

#5 09. 12. 2009 21:24

Re: izomorfní grafy

#6 09. 12. 2009 21:46

Re: izomorfní grafy

#7 10. 12. 2009 18:55

Re: izomorfní grafy

#8 10. 12. 2009 19:44

Re: izomorfní grafy

Zápatí