Matematické Fórum

Jozef3 · 01. 02. 2012 11:27

Ahoj.
Připravuji se na zkoušku z diskrétní matematiky a nevím si rády s následujícím příkladem: "Kolik je vzájemně neisomorfních grafů s 11 vrcholy, jejichž každý vrchol má stupeň 0 nebo 2?"
Proč to není prostě $2^{11}$ ? Něco mi asi uniká, ale nevím co.
Moc děkuji za radu a případnou záchranu ke zkoušce!

Stýv · 01. 02. 2012 12:33

a proč by to mělo být 2^11?

Jozef3 · 01. 02. 2012 12:43

↑ Stýv:Protože každému z těch 11 vrcholů mohu přiřadit stupeň dvěma způsoby: buď stupeň 2, nebo stupeň 0. Tak bych řekl, že počet těchto grafů je stejný jako počet variací s opakováním 2. třídy z 11 prvků, tedy $2^{11}$ .

Stýv · 01. 02. 2012 14:15

tak si zkus nakreslit graf, který má stupně 20000000000. nebo dva neizomorfní grafy se stupni 22200000000

Jozef3 · 01. 02. 2012 14:58

↑ Stýv:To přeci nejde :-).

Stýv · 01. 02. 2012 15:08

↑ Jozef3: no tak vidíš

Jozef3 · 01. 02. 2012 15:12

↑ Stýv:Takže počet vrcholů, které mají stupeň 2 musí být sudý?

Jozef3 · 01. 02. 2012 15:28

↑ Jozef3:Aha, beru zpět. Graf se skóre 22000000000 taky nejde nakreslit. Tak nevím.

Stýv · 01. 02. 2012 15:56

ten graf se zřejmě bude skládat jenom z kružnic a samostatných vrcholů. stačí si nakreslit všechny možnosti, nemělo by jich být tak moc

Matematické Fórum

#1 01. 02. 2012 11:27

Počet grafů na n vrcholech

#2 01. 02. 2012 12:33

Re: Počet grafů na n vrcholech

#3 01. 02. 2012 12:43

Re: Počet grafů na n vrcholech

#4 01. 02. 2012 14:15

Re: Počet grafů na n vrcholech

#5 01. 02. 2012 14:58

Re: Počet grafů na n vrcholech

#6 01. 02. 2012 15:08

Re: Počet grafů na n vrcholech

#7 01. 02. 2012 15:12

Re: Počet grafů na n vrcholech

#8 01. 02. 2012 15:28

Re: Počet grafů na n vrcholech

#9 01. 02. 2012 15:56

Re: Počet grafů na n vrcholech

Zápatí