Grafy skonczone

Archiwum kompendium.
Linka
Gość Specjalny
Gość Specjalny
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka » 10 sty 2005, o 15:32

Grafy Na dobry początek - mały słowniczek. Niedługo pojawią się tu też informacje o grafach hamiltonowskich i eulerowskich, kolorowaniu grafów i map. Graf skonczony G=(V,E) składa się ze skończonego, niepustego zbioru wierzchołków V i zbioru krawędzi E, który jest dowolnym podzbiorem par \(\{\{v,w\}: v,w V, w v \}\) . Szlak jest to ciąg wierzchołków \(v_{1}, v_{2}, ... v_{n}\) (w którym są dozwolone powtórzenia), taki, że wszystkie \(v_{1}v_{2}, v_{2}v_{3}, ... v_{n-1}v_{n}\) są różnymi krawędziami grafu. Jeżeli dodatkowo założymy, że wierzchołki szlaku nie mogą się powtarzać, to mamy do czynienia ze ścieżką. Szlak postaci \(v_{1}, v_{2}, ... v_{n}, v_{1}\) gdzie \(v_{1}, v_{2}, ... v_{n}\) jest ścieżką nazywamy cyklem. Jeżeli jest możliwe przejście z dowolnego wierzchołka do każdego innego wzdłuż pewnego szlaku, to graf jest spójny, w przeciwnym wypadku jest niespójny. Graf niespójny składa się z pewnej ilości składowych. Składowa grafu jest jego maksymalnym spójnym podgrafem. Liczbę krawędzi wychodzącą z danego wierzchołka v nazywamy stopniem tego wierzchołka i oznaczamy \(\delta v\). Lemat "o uściskach dłoni": w dowolnym grafie G=(V,E) \(\bigsum_{v V}\delta v=2|E|\) Drzewa Graf spójny bez cykli nazywamy drzewem. G=(V,E) jest drzewem wtedy i tylko wtedy, gdy |E| = |V| - 1. Suma stopni wierzchołków w drzewie wynosi 2n-2. Niech \(n q 2\) i niech\(d_{1}, ... , d_{n}\) będą dodatnimi liczbami całkowitymi, które sumują się do 2n-2. Wówczas liczba drzew na zbiorze wierzchołków {1, ... , n}, z których każdy ma stopień odpowiednio \(\delta 1 = d_{1}, ... , \delta n = d_{n}\) wynosi \({n-2} \choose {{d_{1}-1} {d_{2}-1} ... {d_{n}-1}}\) Twierdzenie Cayleya: Dla \(n q 2\) liczba drzew na zbiorze wierzchołków {1, ... , n} wynosi \(n^{n-2}\). Kod Pruefera: aby wyznaczyć kod Pruefera dla danego drzewa T na zbiorze wierzchołków {1, ... , n} należy: I. Znaleźć wierzchołek o najmniejszym indeksie i stopniu 1 (nazwijmy go v). Niech w będzie wierzchołkiem połączonym z v. II. Zapisać indeks w oraz usunąć wierzchołek v wraz z krawędzią vw. III. Jeżeli w drzewie pozostała więcej niż jedna krawędź, przejść do kroku I, w przeciwnym razie zakończyć algorytm. Otrzymany ciąg liczb jest kodem Pruefera dla drzewa T.
Ostatnio zmieniony 20 mar 2005, o 19:28 przez Linka, łącznie zmieniany 2 razy.

Ptolemeusz
Użytkownik
Użytkownik
Posty: 365
Rejestracja: 11 lip 2004, o 18:51
Płeć: Mężczyzna
Lokalizacja: Jarosław/Kraków

Grafy skonczone

Post autor: Ptolemeusz » 18 mar 2005, o 15:26

Graf G=(V,E) składa się ze skończonego, niepustego zbioru wierzchołków V i zbioru krawędzi E, który jest dowolnym podzbiorem par .
nie wiem czy dobrze robie że to tu pisze ale w razie czego wykasujesz mój post... otóż są jeszcze grafy nieskończine!!! i w związku z tym Twoja def. jest błędna...

Linka
Gość Specjalny
Gość Specjalny
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka » 19 mar 2005, o 09:00

Wiem ze sa tez nieskonczone, ale niestety zadnej ksiazki nie udalo mi sie o nich znalezc, a definicje wzielam z "Aspektow kombinatoryki" Bryanta, ktora wg mnie jest jedna z lepszych ksiazek w tej tematyce. Jesli masz jakies informacje o grafach nieskonczonych to moze dopisz tutaj, chetnie bym sobie poczytala

Ptolemeusz
Użytkownik
Użytkownik
Posty: 365
Rejestracja: 11 lip 2004, o 18:51
Płeć: Mężczyzna
Lokalizacja: Jarosław/Kraków

Grafy skonczone

Post autor: Ptolemeusz » 19 mar 2005, o 14:25

no moja wiedza z zakresu matematyki dyskretnej jest bardzo ograniczona ale nadal uważam że musisz coś zmienić, np. napisz że jest to def. grafu skończonego... nie można wykluczać istnienia grafów nieskończonych (taka def. to czyni); wiem trochę sie czepiam ale cóż... a i polecam lekturę... R. J. Wilson "Wprowadzenie do teorii grafów"

Linka
Gość Specjalny
Gość Specjalny
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka » 20 mar 2005, o 19:41

Poprawilam caly temat, bo nie wiem na ile reszta definicji odnosi sie do grafow nieskonczonych. Poszukam jakis wiadomosci o tych grafach, bo mnie zaciekawily, i jak znajde to dopisze.

bstq
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 7 lut 2008, o 12:45
Płeć: Mężczyzna
Lokalizacja: Warszawa

Grafy skonczone

Post autor: bstq » 15 lut 2008, o 01:14

Graf G=(V,E) składa się z niepustego zbioru wierzchołków V i zbioru krawędzi E, który jest dowolnym podzbiorem par itd. - to nie jest ogolna definicja grafu? mozesz napisac cos o grafach skierowanych... itp.. hmm wg mnie najlepsze ksiazki to ksiazki autorow takich jak Ore itd. albo dostepna w internecie za darmo ksiazka R.Diestel "Graph Theory" ja mialem tyle z grafow http://www.mini.pw.edu.pl/~tomtracz/md/topics.html ta dziedzina potrafi byc bardzo trudna... jesli ma ktos jakies konkretne pytania to prosze na pw, poszukam notatek:)

ODPOWIEDZ