Matematické Fórum

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
! 2.11.2020 (L) Vykreslete si svůj první matematický výraz přes MathJax!
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 30. 11. 2019 11:49

Alesekk
Zelenáč
Příspěvky: 6
Pozice: student
Reputace:   
 

(n-2)-regulární grafy jsou isomorfní

Dobrý den,
dostal jsem úkol dokázat, že všechny (n-2)-regulární grafy na n vrcholech jsou regulární.
Vypracoval jsem řešení a moje otázka je, jestli je toto řešení korektní nebo, jeslti musím brát v ohled nějaké jiné argumenty. Děkuji

Pokud jsou dva grafy isomorfní, jsou isomorfní i jejich doplňky. Stačí tedy dokázat, že jsou isomorfní doplňky (n-2)-regulárních grafů.
Doplňky (n-2) regulárních grafů na n vrcholech jsou 1-regulární grafy, protože úplný graf na n vrcholech je je (n-1)-regulární. Aby takový graf existoval, musí být n sudé, protože jeho 1-regulární grafy mají všechny stupně 1, takže ke každému bodu musí vést právě jedna hrana, hrana je tvořena právě dvěma body, tudíž počet vrcholů je roven |V(G)|=2|E(G)|. 1-regulární graf je vždycky isomorfní, protože kromě isomorfních variant neexistují žádné jiné 1-regulární grafy. Z toho vyplývá, že i (n-2)-regulární graf je isomorfní.

Offline

  • (téma jako vyřešené označil(a) Alesekk)

#2 30. 11. 2019 12:01

laszky
Příspěvky: 1928
Škola: MFF UK, FJFI CVUT
Reputace:   161 
 

Re: (n-2)-regulární grafy jsou isomorfní

↑ Alesekk:

Ahoj, precti si to po sobe :)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson