Matematické Fórum

BMTH · 26. 11. 2013 15:51

Dobrý den,
chtěl bych se zeptat na příklad:
Nechť m a n jsou libovolná přirozená čísla. Kolik existuje kompletních bipartitních grafů $K{m,n}$ , které mají jako indukovaný podgraf cestu délky 5?

Zkoušel jsem si nejprve kreslit kompletní bipartitní graf o malém počtu vrcholů a poté jsem chtěl výsledek zobecnit pro m a n, avšak nemůžu přijít na žádný, který by zadání splňoval. Pochopil jsem, že indukovaný podgraf vznikne, když odeberu některé vrcholy a pouze ty hrany, které jsou s některým odebraným vrcholem incidentní. Zde mi však stále buď nějaká hrana, aby vznikl indukovaný podgraf cesta délky pět, překáží, nebo naopak chybí. Proto bych prosím potřeboval poradit, co dělám špatně, protože jiný postup mě nenapadá.
Předem děkuji za odpověď.

petrkovar · 28. 11. 2013 09:39

↑ BMTH:Doplním: jedná se o projekt číslo 7.

A uměl byste ukázat, že v každém grafu $K_{m,n}$ bude nějaká hrana přebývat nebo scházet?

BMTH · 29. 11. 2013 17:00 — Editoval BMTH (29. 11. 2013 17:56)

Aha, děkuji. Zkusil bych to takhle, že i když odeberu z kompletního bipartitního grafu jakýkoliv vrchol, pokaždé dostanu znovu kompletní bipartitní graf, jen se sníženým m či n. Ten má vždy všech m*n hran a tudíž cestu mohu dostat jen u grafu $K_{1,2}$ a to délky 2.

petrkovar · 30. 11. 2013 21:42

↑ BMTH:Když vynecháte některé vrcholy, tak hran už nebude m*n. A když budeme pečliví, tak si všimneme, že nemusí nutně vzniknout bipartitní graf.

Matematické Fórum

#1 26. 11. 2013 15:51

Kompletní bipartitní graf a indukovaný podgraf

#2 28. 11. 2013 09:39

Re: Kompletní bipartitní graf a indukovaný podgraf

#3 29. 11. 2013 17:00 — Editoval BMTH (29. 11. 2013 17:56)

Re: Kompletní bipartitní graf a indukovaný podgraf

#4 30. 11. 2013 21:42

Re: Kompletní bipartitní graf a indukovaný podgraf

Zápatí