Drzewo o n wierzchołkach

adamjunior · Post autor: **adamjunior** » 10 kwie 2012, o 17:58

Udowodnij, że każde drzewo o n wierzchołkach ma dokładnie \(\displaystyle{ n - 1}\) krawędzi. Czy ktoś wie w jaki sposób można to udowodnić ?

Qń · Post autor: Qń » 11 kwie 2012, o 10:57

Indukcyjnie po liczbie wierzchołków.

Q.

adamjunior · Post autor: **adamjunior** » 11 kwie 2012, o 11:57

Mógłbyś pokazać jak.

kriegor · Post autor: **kriegor** » 11 kwie 2012, o 12:25

pewnie tak ze dla n=1 drzewo ma zero krawedzi
a konstruujac drzewo mamy na uwadze to ze jest to graf bez cykli a wiec dodajemy wierzcholek wtedy i tylko wtedy gdy dodajemy krawedz koniec dowodu

adamjunior · Post autor: **adamjunior** » 11 kwie 2012, o 12:51

To troszkę za prosto, wydaje mi się .

kriegor · Post autor: **kriegor** » 11 kwie 2012, o 12:59

slaby argument na obalenie dowodu
proste dowody sa najfajniejsze (celowo uzylem niematematycznego okreslenia)

-- 11 kwi 2012, o 12:59 --

jak wpadnie Qń to miejmy nadzieje ze rozstrzygnie to

-- 11 kwi 2012, o 13:00 --

ale jestem pewien ze w ten sposob skonstruuje kazde drzewo n wierzcholkowe czyli dziala-- 11 kwi 2012, o 13:01 --poza tym to prosty fakt wiec dowod nie moze byc trudny

Qń · Post autor: Qń » 11 kwie 2012, o 13:51

Idea jest właśnie taka: dodając wierzchołek, dodajemy krawędź.

Ale formalny argument to indukcja: zakładamy, że dla każdego drzewa o \(\displaystyle{ n}\) wierzchołkach liczba jego krawędzi to \(\displaystyle{ n-1}\) i pokazujemy, że dla dowolnego drzewa o \(\displaystyle{ n+1}\) wierzchołkach liczba jego krawędzi to \(\displaystyle{ n}\). W tym celu bierzemy na tapetę dowolne drzewo o \(\displaystyle{ n+1}\) wierzchołkach, usuwamy dowolny liść, korzystamy z założenia indukcyjnego i z powrotem dołączamy usunięty liść. Po policzeniu krawędzi powinno wyjść tyle ile trzeba.

Q.