szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 2 sie 2018, o 17:26 
Użytkownik

Posty: 5
Lokalizacja: Warszawa
Witam, mam tu dowód wzoru Eulera uogólnionego na powierzchnie genusu g. (Książka Robin J. Wilson Wprowadzenie do teorii grafów.) W dowodzie jest zaznaczone, ze pominięte są szczegóły. Może jest w stanie ktoś pomóc w dokładnym zrozumieniu tego dowodu.

Twierdzenie: Niech G będzie grafem spójnym genusu g, mającym n wierzchołków, m krawędzi i f ścian. Wtedy n-m+f=2-2g

Szkic dowodu.

Bez straty ogólności możemy założyć, ze graf G jest narysowany na sferze z g rączkami. Możemy również założyć, ze krzywe A, wzdłuż których rączki łącza się ze sferą, są cyklami grafu G; w razie potrzeby ściągamy te cykle, które zawierają krzywe A we wnętrzu.

Następnie odłączamy od sfery jeden koniec każdej rączki, w ten sposób każda rączka ma wolny koniec E,a sfera ma w tym miejscu dziurę H. Możemy założyć, że cykl odpowiadający zakończeniu rączki występuje zarówno na końcu raczki E, jak i wokół dziur H na sferze, gdyż nie zmienia to wartości wyrażenia n-m+f: liczby dodatkowych wierzchołków i krawędzi znoszą sie wzajemnie w tym wyrażeniu (patrz rys.).
Kończymy dowód ,,wciskając'' każdą z tych rączek w sferę. Otrzymujemy w ten sposób sferę mającą 2g dziur. To wciskanie rączek nie zmienia wartości wyrażenia n-m+f. Ale na sferze wartością tego wyrażenia jest 2, więc na sferze mającej 2g dziur będziemy mieli n-m+f=2-2g co kończy dowód.

link do rysunku https://zapodaj.net/aeae286158232.jpg.html

Chodzi głównie o to ,,wciskanie'' rączek w sferę
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 sie 2018, o 17:38 
Użytkownik
Avatar użytkownika

Posty: 2705
Lokalizacja: Radom
Napisałbyś jak się defniujiuje genus grafu?
Góra
Kobieta Offline
PostNapisane: 3 sie 2018, o 16:04 
Użytkownik

Posty: 5
Lokalizacja: Warszawa
W tej książce jest następująca definicja:
\\ Graf przedstawiony bez przecięć na powierzchni genusu g, niemozliwy do przedstawienia na g-1 nazywany jest grafem genusu g .
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Algorytm Fleury’ego. Droga/ciąg Eulera  Wyleksony  2
 Funkcja Eulera - zadanie 3  flake  1
 funkcja Eulera - zadanie 5  matkar1  2
 dowód dla wniosku z wzoru Eulera  przyszly_naukowiec  4
 Problem z grafem Eulera  matwie  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl