szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 wrz 2015, o 18:57 
Użytkownik

Posty: 94
Lokalizacja: Krk
Jaka jest maksymalna liczba regionów w grafie planarnym o n wierzchołkach?

Wiadomo, że dla każdego grafu planarnego o k krawędziach i p wierzchołkach:

k \le 3p - 6

Ponadto, dla każdego grafu planarnego o f regionach:

f = k - p + 2 (wzór Eulera)

Podstawiając mamy:

f  \le 3p - 6 - p + 2 = 2p - 4

Czyli odpowiedź to:

2n-4

?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba możliwych delegacji.  kugelsicher  2
 liczba grafów  tece  0
 Liczba sposobów rozmieszczenia osób w wagonach kolejowych  zimnydran  1
 Liczba zbiorow z conajwyzej jedna czara kula  wolk  5
 Liczba ciągów  klaudiak  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl