Matematické Fórum

Vel3 · 06. 12. 2014 13:38

Zdravím,

ve škole probíráme grafy a já chyběl na část učiva kde se braly komponenty. Na netu i ve skriptech předmětu jsem sice našel co ta komponenta je, ale prostě nikde jsem nenašel nějaký rozumný příklad jak se to počítá.

Prosím vás, mohl by mi to někdo střučně vysvětlit bez těch matematických hatmatilek. Máme několik příkladů ve skriptech jako je třeba
1.Kolik komponent má 2-pravidelný graf na N vrcholech kde N je přirozené číslo

, podobný příklad pak

2.máme 4-pravidelný graf na 30 vrcholech
3.graf se 7 vrcholy a 15 hranami.

Opravdu mohl by mi to někdo nějak stručně vysvětlil na těchto příklad ať se mám aspoň jak odrazit k těm dalším co máme ve skriptech.

Děkuji budu moc vděčný Honza

petrkovar · 08. 12. 2014 21:23

↑ Vel3:Chápejme otázku položenou takto: "Kolik komponent může mít 2-pravidelný graf na N vrcholech kde N je přirozené číslo?". Je to otázka z aktuálního projektu.

Je nutno rozmyslet, jaký je nejmenší a jaký největší počet komponent takového grafu. A pak argumentovat, jak je to s grafy s počtem komponent mezi. Ideálně uvést příklady.
První krok: jak vypadá každá komponenta grafu, který je 2-pravidelný?

U otázek 2. není položena otázka. To je dost zásadní, protože si lze domyslet triviální i extrémně obtížné zadání.
U 3. je odpověď celkem triviální s využitím principu sudosti.

Matematické Fórum

#1 06. 12. 2014 13:38

Úvod do teorie grafů - Komponenty

#2 08. 12. 2014 21:23

Re: Úvod do teorie grafů - Komponenty

Zápatí