Grafy - Drzewo

michalsrodek · Post autor: **michalsrodek** » 6 wrz 2009, o 21:47

Na kolokwium z matematyki dyskretnej miałem takie zadanie:

Znajdz T(L) gdzie L = { 1; 3; 2; 2.5; 2.5; 1; 4; 2; 1; }

Czy ktoś domyśla się o co może chodzić? Podejrzewam, że to coś związane z grafami i rysowaniem drzewa ale reki nie dam sobie uciąć...

miodzio1988 · Post autor: **miodzio1988** » 6 wrz 2009, o 21:49

Co oznacza symbol \(\displaystyle{ T(L)}\) ? Bo co wykladowce to inne oznaczenia. Mam nadzieję, że CHOCIAŻ to wiesz. Bo bez tego adania nie ruszymy

Inkwizytor · Post autor: **Inkwizytor** » 6 wrz 2009, o 21:50

Na mój gust to jest chyba Kod Prufera, ale czy tam na pewno są "połówki" czy to raczej 5 powinno być.

michalsrodek · Post autor: **michalsrodek** » 6 wrz 2009, o 21:54

a) Nie mam pojęcia co oznacza T(L) (tak to jest jak się na wykłady nie chodzi :])
b) Połówki są na pewno bo mam zeskanowaną kartkę ;]

miodzio1988 · Post autor: **miodzio1988** » 6 wrz 2009, o 21:55

a) To bez definicji nic nie zrobimy. Trzeba bylo na wyklad chodzic.
b) Zostawiam Cie Inkwizycji w takim razie. Ja bez definicji (pewnej ) nic wolę nie robic.

Inkwizytor · Post autor: **Inkwizytor** » 6 wrz 2009, o 21:58

W grafach "połówki" mogą tylko wystąpić przy wagach krawędzi, więc jest to zbiór krawędzi, Załóżmy że szukamy drzewa T(L) ale potrzebne sa jakieś założenia dotyczące budowy, kształtu, grafu czy też zasad łączenia wierzchołków.
Proponuję zwrócić się do właściciela zeskanowanej kartki z prośbą o małe uzupełnienie.

Zeskanowana kartka to nie dowód, zwłaszcza jeśli się samemu nie było na zajęciach, bo ktoś (właściciel kartki) mógł źle przepisać

Gdyby jednak okazało się że to są "piątki" a nie "połówki" to sprawdź sobie algorytm rysowania drzewa na podstawie kodu Prufera (u "umlałt")

michalsrodek · Post autor: **michalsrodek** » 6 wrz 2009, o 22:30

Ok, dzięki za informacje .Sprawdzę ten kod Prufera. Kartka jest wydrukowana więc kolega nic nie przepisywał. To jest zadanie z kolokwium i brzmi ono identycznie jak przepisałem więc żadnych dodatkowych informacji nie ma.-- 9 wrz 2009, o 00:00 --Znalazłem . Jednak nie chodziło o drzewo a o kody optymalne Huffmana.

Tak czy inaczej dzięki za pomoc .