Grafy skonczone

Archiwum kompendium.
Linka
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka »

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 \(\displaystyle{ G=(V,E)}\) składa się ze skończonego, niepustego zbioru wierzchołków \(\displaystyle{ V}\) i zbioru krawędzi \(\displaystyle{ E}\), który jest dowolnym podzbiorem par
\(\displaystyle{ \{\{v,w\}: v,w \in V, w \ne v \}}\) .

Szlak jest to ciąg wierzchołków
\(\displaystyle{ v_{1}, v_{2}, ... v_{n}}\) (w którym są dozwolone powtórzenia), taki, że wszystkie \(\displaystyle{ 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 \(\displaystyle{ v_{1}, v_{2}, ... v_{n}, v_{1}}\) gdzie \(\displaystyle{ 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 \(\displaystyle{ \delta v}\).

Lemat "o uściskach dłoni": w dowolnym grafie \(\displaystyle{ G=(V,E)}\)
\(\displaystyle{ \sum_{v \in V}\delta v=2|E|}\)


Drzewa

Graf spójny bez cykli nazywamy drzewem.

\(\displaystyle{ G=(V,E)}\) jest drzewem wtedy i tylko wtedy, gdy \(\displaystyle{ |E| = |V| - 1.}\)

Suma stopni wierzchołków w drzewie wynosi \(\displaystyle{ 2n-2}\).

Niech \(\displaystyle{ n \geq 2}\) i niech \(\displaystyle{ d_{1}, ... , d_{n}}\) będą dodatnimi liczbami całkowitymi, które sumują się do \(\displaystyle{ 2n-2}\). Wówczas liczba drzew na zbiorze wierzchołków \(\displaystyle{ \{1, ... , n\}}\), z których każdy ma stopień odpowiednio \(\displaystyle{ \delta1 = d_{1}, ... , \delta n = d_{n}}\) wynosi \(\displaystyle{ {n-2 \choose d_{1}-1\ d_{2}-1 ... d_{n}-1}}\)

Twierdzenie Cayleya: Dla \(\displaystyle{ n q 2}\) liczba drzew na zbiorze wierzchołków {1, ... , n} wynosi \(\displaystyle{ n^{n-2}}\).

Kod Pruefera: aby wyznaczyć kod Pruefera dla danego drzewa \(\displaystyle{ T}\) na zbiorze wierzchołków \(\displaystyle{ \{1, ... , n\}}\) należy:
I. Znaleźć wierzchołek o najmniejszym indeksie i stopniu \(\displaystyle{ 1}\) (nazwijmy go \(\displaystyle{ v}\)). Niech \(\displaystyle{ w}\) będzie wierzchołkiem połączonym z \(\displaystyle{ v.}\)
II. Zapisać indeks \(\displaystyle{ w}\) oraz usunąć wierzchołek \(\displaystyle{ v}\) wraz z krawędzią \(\displaystyle{ 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 \(\displaystyle{ 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
Pomógł: 2 razy

Grafy skonczone

Post autor: Ptolemeusz »

Linka pisze: 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
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka »

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
Pomógł: 2 razy

Grafy skonczone

Post autor: Ptolemeusz »

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
Użytkownik
Użytkownik
Posty: 81
Rejestracja: 26 lis 2004, o 11:00
Płeć: Kobieta
Lokalizacja: Lublin

Grafy skonczone

Post autor: Linka »

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
Pomógł: 67 razy

Grafy skonczone

Post autor: bstq »

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
ta dziedzina potrafi byc bardzo trudna... jesli ma ktos jakies konkretne pytania to prosze na pw, poszukam notatek:)
Zablokowany