szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 23 cze 2015, o 12:51 
Użytkownik

Posty: 167
Lokalizacja: Polska
Jak się za to zabrać?

Niech G będzie grafem planarnym mającym co najmniej 3 wierzchołki. Wykazać, że jeśli G nie ma cykli długości 3, to \left| E()G\right|  \le 2\left| V(G)\right|-4.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 28 cze 2015, o 14:57 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Dość trudne zadanie. Postaram się wytłumaczyć na tyle na ile umiem. Trzeba tutaj skorzystać
ze wzoru Eulera mówiącego o tym,że f=k-p +1 gdzie f to liczba regionów,k liczba krawędzi a p to liczba wierzchołków. Zachodzą również 2 nierówności dla grafów planarnych:
f\le \frac{2}{3}k
k \le 3p -6

Teraz wypadałoby je udowodnić tzn. najważniejsza będzie pierwsza. Może w skrócie:
każdy region jest ograniczony przez cykl,którego minimalna liczba krawędzi wynosi 3.
Jeśli przez r_{i} oznaczymy sobie liczbę krawędzi i-tego regionu to suma tych krawędzi na pewno będzie \ge 3f.
Następnie każda krawędź występuje w granicy co najwyżej 2 regionów. Więc suma naszych
r_{i}\le 2k Stąd mamy pierwszą nierówność. Teraz skoro każdy nasz cykl ma długość 4 trzeba podstawić ją zamiast 3 i wyprowadzić wzór,który będzie się trochę różnił od tej pierwszej
nierówności. Dalej używając tej drugiej której podałem i tożsamości na liczbę regionów twoja nierówność wyjdzie banalnie. W razie kłopotów pisz
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 graf nieskierowany  redxxx  1
 Graf nie izomorficzny regularny 3 stopnia z 9 wierzchołkami  winfast29  3
 graf dwudzielny - zadanie 3  danielek12201220  1
 drzewo i graf krawędzowy  glupiablondyna  3
 Graf 5 skladowych  lutzi0  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl