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

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


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczba rozwiązań równania - zadanie 40  waliant  5
 Liczba przedstawień liczby n w postaci sumy k liczb  Anonymous  2
 Liczba inwolucji z zbiorze permutacji zbioru n-elementowego.  kasieńka3  0
 liczba podzbiorów rodziny  JakubCh  0
 liczba podzbiorów - zadanie 3  celia11  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl