twierdzenie dotyczące grafów planarnych
twierdzenie dotyczące grafów planarnych
Uogólnienie twierdzenia Eulera.
\(\displaystyle{ n -m + f = 2 -2g.}\)
Potrzebuję dowód do tego twierdzenia, no ale niestety nie jest to takie proste...:/
Zatem: g-rodzaj (genus) grafu.
Udało się mi znaleźć dowód tego tw, ale w języku ang i tu kolejny problem:
Theorem 4 If G is a connected graph with genus g, then:\(\displaystyle{ f(G) = e(G) – n(G) + 2 –2g}\)
Proof. By induction on g.
· For \(\displaystyle{ g=0}\) the graph is planar and we have \(\displaystyle{ f(G) = e(G) – n(G) + 2 – 2g}\)
from Euler’s formula.
· We assume that the theorem is true for all graphs with genus (g-1)
These graphs may be drawn on a spherical surface with (g-1) handles and include
all those graphs obtained by deleting those edges passing over a single handle in
any graph of genus g.
· We construct G with genus g on a surface o genus g by adding a single edge to G’,
requiring an additional handle. Using prime letters for G’, we have by the induction
hypothesis:
\(\displaystyle{ F(G’) = e(G’) – n(G’) + 2 – 2g’}\)
But\(\displaystyle{ e(G)=e(G’)+1, g = g’+1, n-n(G’) +1}\) (nie rozumiem skąd takie n ? czy na pewno tutaj nic nie brakuje?)
Also \(\displaystyle{ f(G) = f(G’) – 1}\) because the handle connects two distinct faces in G’ making
A single face in G. Hence by substitution:
\(\displaystyle{ F(G) = e(G) – n(G) + 2 – 2 g.}\)
And so by induction the theorem is proved.
Byłabym bardzo wdzięczna za pomoc
Jeślibym miała w miarę przetłumaczony ten tekst, to może udałoby się mi zrozumieć coś wiecej z tego dowodu... może poprostu żle tłumaczę ten tekst...
nierozumiem tekstu od drugej kropki: załóżmy, że tw jets prawdziwe dla wszystkich grafów rodzaju g-1. Grafy te moga być sporządzone na sferze z g-1 uchwytamii obejmują wszystkie te grafy uzyskane przez usunięcie tych krawędzi przechodzących przez jeden uchwyt (nie wiem czy tu juz dobrze tłumaczę?) grafu rodzaju g. Dalej budujemy graf G przez dodanie jednej krawędzi do grafu G' (nie rozumiem co ozn graf G'), wymaga to dodatkowego uchwytu. i dalej to już zupełnie nie rozumiem....
\(\displaystyle{ n -m + f = 2 -2g.}\)
Potrzebuję dowód do tego twierdzenia, no ale niestety nie jest to takie proste...:/
Zatem: g-rodzaj (genus) grafu.
Udało się mi znaleźć dowód tego tw, ale w języku ang i tu kolejny problem:
Theorem 4 If G is a connected graph with genus g, then:\(\displaystyle{ f(G) = e(G) – n(G) + 2 –2g}\)
Proof. By induction on g.
· For \(\displaystyle{ g=0}\) the graph is planar and we have \(\displaystyle{ f(G) = e(G) – n(G) + 2 – 2g}\)
from Euler’s formula.
· We assume that the theorem is true for all graphs with genus (g-1)
These graphs may be drawn on a spherical surface with (g-1) handles and include
all those graphs obtained by deleting those edges passing over a single handle in
any graph of genus g.
· We construct G with genus g on a surface o genus g by adding a single edge to G’,
requiring an additional handle. Using prime letters for G’, we have by the induction
hypothesis:
\(\displaystyle{ F(G’) = e(G’) – n(G’) + 2 – 2g’}\)
But\(\displaystyle{ e(G)=e(G’)+1, g = g’+1, n-n(G’) +1}\) (nie rozumiem skąd takie n ? czy na pewno tutaj nic nie brakuje?)
Also \(\displaystyle{ f(G) = f(G’) – 1}\) because the handle connects two distinct faces in G’ making
A single face in G. Hence by substitution:
\(\displaystyle{ F(G) = e(G) – n(G) + 2 – 2 g.}\)
And so by induction the theorem is proved.
Byłabym bardzo wdzięczna za pomoc
Jeślibym miała w miarę przetłumaczony ten tekst, to może udałoby się mi zrozumieć coś wiecej z tego dowodu... może poprostu żle tłumaczę ten tekst...
nierozumiem tekstu od drugej kropki: załóżmy, że tw jets prawdziwe dla wszystkich grafów rodzaju g-1. Grafy te moga być sporządzone na sferze z g-1 uchwytamii obejmują wszystkie te grafy uzyskane przez usunięcie tych krawędzi przechodzących przez jeden uchwyt (nie wiem czy tu juz dobrze tłumaczę?) grafu rodzaju g. Dalej budujemy graf G przez dodanie jednej krawędzi do grafu G' (nie rozumiem co ozn graf G'), wymaga to dodatkowego uchwytu. i dalej to już zupełnie nie rozumiem....
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
twierdzenie dotyczące grafów planarnych
po pierwsze to nie bardzo rozumiem dalszą częśc tekstu...nie wiem ile powinno wynosić n, pisałam pytania w pierwszym poscie:)
nie wiem też jak przetłumaczyć tekst: "because the handle connects two distinct faces in G’ making
A single face in G. Hence by substitution: \(\displaystyle{ F(G) = e(G) – n(G) + 2 – 2 g.}\)
nie wiem też jak przetłumaczyć tekst: "because the handle connects two distinct faces in G’ making
A single face in G. Hence by substitution: \(\displaystyle{ F(G) = e(G) – n(G) + 2 – 2 g.}\)
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
twierdzenie dotyczące grafów planarnych
1.zamiast pierwszego minusa powinno być \(\displaystyle{ =}\)
2.Ponieważ połączenie rączek dwóch rozłącznych powierzchni grafu daje pojedyńczą powierzchnię, zatem poprzez podstawienie....
2.Ponieważ połączenie rączek dwóch rozłącznych powierzchni grafu daje pojedyńczą powierzchnię, zatem poprzez podstawienie....
twierdzenie dotyczące grafów planarnych
Kartezjusz jak definiujesz rączkę w grafie(czy tam w powierzchni grafu)?
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
twierdzenie dotyczące grafów planarnych
O ile pamiętam genus powierzchni jest to liczba definiowana następująco:
1.sfera ma genus zero, jak każda powierzchnia z nią homeomorficzna
2.Powierzchnia o genusie \(\displaystyle{ g}\) powstaje poprzez dołączenie do powierzchni o genusie \(\displaystyle{ g-1}\) powierchni o genusie \(\displaystyle{ 0}\) tak,aby nowa powierchnia była niehomeomoerficzna. i ta doczepiana powierzchnia to jest uchwyt( inaczej rączka) Jeśli dobrze to zrozumiałem.
1.sfera ma genus zero, jak każda powierzchnia z nią homeomorficzna
2.Powierzchnia o genusie \(\displaystyle{ g}\) powstaje poprzez dołączenie do powierzchni o genusie \(\displaystyle{ g-1}\) powierchni o genusie \(\displaystyle{ 0}\) tak,aby nowa powierchnia była niehomeomoerficzna. i ta doczepiana powierzchnia to jest uchwyt( inaczej rączka) Jeśli dobrze to zrozumiałem.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy