szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 wrz 2015, o 17: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 drzew rozpiętych grafu  johnny1591  0
 liczba cykli długości 4 w grafie G  JakubCh  0
 Liczba kombinacji zespołu.  nesti32  1
 Liczba rozmieszczeń w szkatułkach  Fiszer  1
 Liczba całkowitoliczbowych rozwiązań równania  pinksaid  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl