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

?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba trójkątów i liczba rozwiązań  placky  8
 n-cyfrowa liczba  FoxOtRoxx  6
 Liczba funkcji monotonicznych - zadanie 2  neecos  2
 liczba znajomych  noob  1
 Liczba drzew  pytajnik_jest_zajety  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl