szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 lip 2016, o 21:06 
Użytkownik

Posty: 1
Lokalizacja: Wrocław
Witam,
Potrzebuje pomocy z zadaniem z teorii grafów. Nie mam pojęcia jak je rozwiązać i będę niesamowicie wdzięczny za pomoc i wyjaśnienie.

Treść:

Ile jest wszystkich drzew rozpiętych na zbiorze wierzchołków \{1,2,3,...n\}, n > 12 w których wierzchołek 1 ma stopień 12, a wierzchołek 2 ma stopień n-12? Odpowiedź należy wyczerpująco uzasadnić.

Z góry dziękuję.

Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 8 lip 2016, o 12:52 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
Należy zadać sobie pytanie.. Czy może istnieć drzewo o takich własnościach, w którym nie istnieje krawędź pomiędzy wierzchołkiem 1 i 2.. Otóż zauważyć należy, że jeśli istnieje krawędź między tymi wierzchołkami i do wierzchołka 1 przyłączymy jeszcze 11 innych wierzchołków to pozostanie nam n-13 wierzchołków do dyspozycji.. Zauważmy, że wierzchołek 2 ma w tej chwili stopień 1 ponieważ nie może istnieć żadna krawędź między nim a którymś z 11 wierzchołków przyłączonych do wierzchołka 1(powstałby cykl).. Wszystkie pozostałe wierzchołki, należy przyłączyć zatem do wierzchołka 2, aby spełnić założenie o stopniu tegoż wierzchołka..
Czy może istnieć drzewo o takich własnościach bez krawędzi (1,2)? Otóż jeśli do 1 przyłączymy 12 wierzchołków i nie będzie wśród nich 2 to oprócz 2 pozostanie nam jeszcze n-14 wierzchołków.. Jeśli przyłączymy 2 do któregoś z wierzchołków przyłączonych do 1 to i tak zabraknie nam wierzchołków na spełnienie założenia odnośnie stopnia wierzchołka 2
Odpowiedź zatem brzmi: Nie istnieje drzewo rozpięte na n wierzchołkach w którym wierzchołek 1 ma stopień 12, wierzchołek 2 ma stopień n-12 i nie istnieje krawędź między wierzchołkami 1 i 2.
Zauważmy również, że nie może być również krawędzi między żadnymi dwoma z dwunastu wierzchołków przyłączonych do 1(powstałby cykl), ani krawędzi między żadnymi dwoma wierzchołkami przyłączonymi do 2.
Zauważmy zatem, że wybór tych 11 wierzchołków przyłączonych do 1 utworzy nam cały graf..
Drzew o zadanych własnościach jest zatem {n \choose 11}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 Dany jest zbiór A={a,b,c,d}  Nanu  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl