szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 wrz 2015, o 11:06 
Użytkownik

Posty: 86
Lokalizacja: Gdańsk
Witam.

Drzewa to są grafy spójne, niezawierające pętli i krawędzi wielokrotnych i niemające cykli. Las jest drzewem wtedy, kiedy jest spójny.

Załóżmy, że las ma 2015 wierzchołków i 2000 krawędzi. Aby określić z ilu się składa drzew należy odpowiedzieć na pytanie, ile grafów spójnych jest zawartych w grafie złożonym z 2015 wierzchołków i 2000 krawędzi. Tylko w jaki sposób można to zrobić?
Góra
Kobieta Offline
PostNapisane: 12 wrz 2015, o 11:36 
Użytkownik
Avatar użytkownika

Posty: 2505
Zauważ, że w każdym drzewie jest jeden wierzchołek więcej niż krawędzi. W Twoim lesie nadmiarowych wierzchołków jest piętnaście i tyle właśnie wynosi liczba drzew, której szukasz.
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
 Ciągi liczb wierchołków kolejnych stopni grafów?  Sonite  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl