Matematické Fórum

Merlí · 08. 03. 2010 23:36

Zdravím
Máme následující větu:
Ať T je strom na n vrcholech a di označuje počet vrcholů stupně i. Potom platí d1 = d3 + 2*d4 + ... + (n-2)*dn + 2.

Je jasné, že počet listů nebude záviset na počtu vrcholů stupně 2, protože ty ve stromě jen prodlužují cesty.
Předpokládám, že idea důkazu bude nějak souviset s větou o skóre.

Budu vděčný za každý nápad.

Stýv · 08. 03. 2010 23:50

Merlí napsal(a):
Je jasné, že počet listů nebude záviset na počtu vrcholů stupně 2, protože ty ve stromě jen prodlužují cesty..

a co když vrchol stupně 2 nahradíš vrcholem stupně n? přibude n-2 "větví", na konci každé jeden list;)

Olin · 09. 03. 2010 00:06 — Editoval Olin (09. 03. 2010 00:33)

Zkusil bych indukci podle největšího stupně vrcholu přítomného v grafu. Uvážil bych následující úpravu:

(odstranil jsem vrcholy s nejvyšším stupněm, v tomto případě 4).

Popřípadě by asi ještě šla rozjet dvojitá indukce, podle nejvyššího stupně a podle počtu přítomných vrcholů tohoto stupně.

!!EDIT: anebo úplně jednoduchou indukcí podle počtu vrcholů - odtrhneme list a probereme, co se stalo se stupněm vrcholu, na který byl napojen. Teď večer už mi to moc nemyslí, proto mi ty nápady přichází ve špatném pořadí.

Merlí · 09. 03. 2010 19:17

Jasně, indukce podle počtu vrcholů.
Pro n=1 a 2 se ověří snadno, a dokáže se pro n -> n+1. Řeknu, že tvrzení platí pro n vrcholů a dokážu, že platí i pro n+1 vrcholů. Proberu všechny případy - tedy přidaný vrchol může být stupně 1 (pěkně se to tam odečte) nebo stupně 2 (nemá na tvrzení vliv, pouze prodlužuje cesty).
Díky za nakopnutí ;-)

Matematické Fórum

#1 08. 03. 2010 23:36

Grafová úloha - důkaz věty

#2 08. 03. 2010 23:50

Re: Grafová úloha - důkaz věty

Merlí napsal(a):

#3 09. 03. 2010 00:06 — Editoval Olin (09. 03. 2010 00:33)

Re: Grafová úloha - důkaz věty

#4 09. 03. 2010 19:17

Re: Grafová úloha - důkaz věty

Zápatí