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 24. 11. 2019 12:47 — Editoval martin_a1 (24. 11. 2019 12:48)

martin_a1
Zelenáč
Příspěvky: 5
Reputace:   
 

Pomoc s izomorfismem grafů

Dobrý den,

snažím se udělat zadání, kdy máme nakreslit tři neizomorfní grafy podle věty Havel-Hakimi se stupňovou posloupností (6, 3, 3, 3, 3, 3, 3, 2) a pečlivě zdůvodnit, proč nejsou izomorfní.

Rád bych požádal o pomoc s tímto příkladem.

Již mám udělanou kompletní redukci a nějaké 3 grafy s touto posloupností, ale nevím, jak správně ověřit, jestli jsou izomorfní nebo ne, případně, opravit ty grafy tak, aby všechny 3 nebyli izomorfní a zdůvodnit, proč nejsou izomorfní.

Redukci mám takto:
(6, 3, 3, 3, 3, 3, 3, 2)
(2, 2, 2, 2, 2, 2, 2)    
(2, 2, 2, 2, 1, 1)
(2, 1, 1, 1, 1)
(1, 1, 0, 0)                
(0, 0, 0) - vím tedy, že je grafová tato posloupnost

Toto tedy jsou 3 nějaké grafy s touto posloupností, ale nevím, jestli se tím myslí to kreslit v samotné redukci a 3x neizomorfně nebo ve finální fázi. Můžeme mi prosím pomoci s tímto?

//forum.matematika.cz/upload3/img/2019-11/95903_1.jpg

//forum.matematika.cz/upload3/img/2019-11/95920_2.jpg

//forum.matematika.cz/upload3/img/2019-11/95933_3.jpg

Předem děkuji každému za pomoc.

Martin

Offline

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

#2 24. 11. 2019 19:51

check_drummer
Příspěvky: 3071
Reputace:   80 
 

Re: Pomoc s izomorfismem grafů

↑ martin_a1:
Ahoj, proč myslíš, že jsou ty grafy neizomorfní? Podle mě izomorfní jsou.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#3 24. 11. 2019 20:26 — Editoval laszky (24. 11. 2019 21:36)

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

Re: Pomoc s izomorfismem grafů

↑ martin_a1:

Ahoj, taky si myslim, ze vsechny ty tve grafy jsou izomorfni.

Navod, jak vytvorit dalsi 2 neizomorfni:

1) Vytvor graf, kde je 2 spojena s 6 a maji spolecneho "souseda"

2) Vytvor graf, kde je 2 spojena s 6 a nemaji spolecneho "souseda"

Offline

 

#4 24. 11. 2019 21:31

martin_a1
Zelenáč
Příspěvky: 5
Reputace:   
 

Re: Pomoc s izomorfismem grafů

Myslíte takto? Jsou nyní neizomorfní? Respektive, že už nejsou stejné? Zkusil jsem teda udělat ty dva tak, že vrchol stupně 2 je spojen s vrcholem stupně 6 a v jednom případě je společný soused 3 a v druhém ne. Je to nyní správně i, co se týče tohoto odůvodnění?

//forum.matematika.cz/upload3/img/2019-11/27441_n1.jpg

Předem opět děkuji každému za odpověď.

Offline

 

#5 24. 11. 2019 21:40

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

Re: Pomoc s izomorfismem grafů

↑ martin_a1:

Ano, presne takto ;-)

Offline

 

#6 24. 11. 2019 21:44

martin_a1
Zelenáč
Příspěvky: 5
Reputace:   
 

Re: Pomoc s izomorfismem grafů

↑ laszky:

Moc vám děkuji za pomoc s tímto příkladem.

Pěkný večer přeji. :)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson