szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 cze 2017, o 23:43 
Użytkownik
Avatar użytkownika

Posty: 329
Lokalizacja: Poznań
Ile najmniej i najwięcej składowych spójności może mieć graf prosty:
a) o 15 wierzchołkach i 55 krawędziach
b) o 100 wierzchołkach i 54 krawędziach

\omega- liczba spójności
\nu- liczba wierzchołków
\epsilon - liczba krawędzi
Korzystam z zależności
\nu - \omega  \le \epsilon  \le  {\nu - \omega + 1 \choose 2}

Rozwiązując \nu - \omega  \le \epsilon
Otrzymuję \omega  \ge 40
Rozwiązując \epsilon  \le  {\nu - \omega + 1 \choose 2 }
otrzymuję równania \omega^2 -31*\omega +130  \ge 0
Otrzymuję wyniki \left( \infty ,5 \right\rangle  \cup \left\langle 26, \infty  \right)

I nie jestem pewien czy to poprawny wynik. Jakby ktoś mógł podpowiedzieć jak podejść do tego typu zadania będę wdzięczny
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2017, o 01:51 
Użytkownik
Avatar użytkownika

Posty: 1229
Tego nie trzeba pałować jakimiś tam wzorami. Kiedy jest najwięcej składowych? Jak istnieją wierzchołki dużych stopni, a kiedy najmniej? Jak wierzchołki mają małe stopnie. Trzeba po prostu to policzyć.
Góra
Mężczyzna Offline
PostNapisane: 10 cze 2017, o 11:17 
Użytkownik
Avatar użytkownika

Posty: 329
Lokalizacja: Poznań
Po prostu czyli jak? Podpowiesz?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 graf spójny, czy k-regularny?  JakubCh  0
 liczba uczestników - zadanie 2  AndrzejK  1
 Liczba odcinków - zadanie 2  Michas1415  5
 Liczba 9-cyfrowa z trójkami, czwórkami, bez zer  zanstaszek9  1
 problem chińskiego listonosza graf  chelm20  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl