Grafy skonczone
: 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 \(\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}\).
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}\).