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
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
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.matweb.cz/upload3/img/2019-11/95903_1.jpg

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

//forum.matweb.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: 3867
Reputace:   91 
 

Re: Pomoc s izomorfismem grafů

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


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Offline

 

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

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

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.matweb.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: 2292
Škola: MFF UK, FJFI CVUT
Reputace:   193 
 

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