Buntownik z wyboru i zadanie

W filmie Buntownik z wyboru główny bohater rozwiązuje pewne zadanie zlecone przez profesora MIT. Brzmi ono tak:

Narysuj homeomorficzne nieskracalne drzewa wielkości n=10.

Drzewo to ze sobą połączone kreski, które nie tworzą pętli (czyli koniec jednego odcinka nie łączy się z końcem innego odcinka), homeomorficzne i 10, czyli ma być 10 wierzchołków i wszystkie kombinacje tych dziesięciu wierzchołków i łączących je odcinków. Najwazniejszym elementem jest tutaj nieskracalność (tłumaczę bezpośrednio z angielskiego), które ustanawia nam dodatkowy (oprócz braku pętli) warunek, który musimy spełnić: żadną kropkę nie mogą łączyć dwie linie.

Można sobie najpierw dla przećwiczenia i odnalezienia preferowanego sposobu rozwiązania, tudzież algorytmu zrobić to zadanie dla n<10.

Rozwiązanie:

homeoirrtreesnleq12parti1

Ja to rozwiązałam tak, że najpierw sprawdziłam jaki może powstać najdłuższy łańcuch poprzez to, że krańce drzewa muszą mieć dodatkowe 2 kropki minimum (widełki). Każdy kolejny etap był również oczywiście rozpoznany (jedna kropka w centrum, reszta odnogi; dwie kropki połączone, reszta odnogi, w tym jedne widełki, itp.). Dla 10 wierzchołków jest tylko jedno drzewo, które jest długie na 4 kropki (odnóg/widełek nie zaliczam do długości).

Jak się to zrobi to można dla każdej długości potem rozrysować różne możliwości ułożenia kropek. Da się to zrobić  między innymi poprzez dodawanie ich tam, gdzie więcej kropek już odjąć nie można.

Jest to tylko jeden sposób rozwiązania oraz należy pamiętać, że drzewa wcale nie muszą być narysowane, jak na powyższym rysunku:

g6

W filmie zadanie pokazane jest, jako niesamowicie trudne, ale prawda jest taka, że każdy je może rozwiązać.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s