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 nieparzysta, 6 różnych cyfr, 3 z nich przyste  Bang  1
 Liczba funkcji przyjmujących pieć wartości  Heniek1991  1
 Maksymalna liczba znaków w alfabecie Braille'a  Notrem  3
 Liczba wierzchołków stopnia 1 w drzewie  Hobbs  0
 ile dzielników dodatnich ma liczba 24480  ahhha  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl