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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
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 nie izomorficzny regularny 3 stopnia z 9 wierzchołkami  winfast29  3
 Graf planarny bez trójkątów  lidka95  1
 kolorowanie grafu - graf planarny 3-kolorowalny  Algorytmistrz  2
 liczba sposobów na jakie osoby mogą wejść do autobusu  mala_mi  1
 Sprawdzenie czy graf jest planarny, hamiltonowski, planarny  Lyzka  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl