wykl 3 i 4
0 10 kartičky adamomasz
otázka  |
odpověď |
|||
|---|---|---|---|---|
|
Charakteryzacja drzew
|
1. graf T jest drzewem o n wierzchołkach 2. T ma n-1 krawędzi i jest spojny i acykliczny 3. każda krawędź jest mostem 4. ka»de dwa wierzchoªki T sa poª¡czone dokªadnie jedn¡ drog¡ elementarn¡ 5. T jest acykliczny, ale po dodaniu jakiejkolwiek kraw¦dzi powstaje dokªadnie jeden nowy cykl
|
|||
|
Indeks Wienera
|
ds(G) dla grafu G: suma wszystkich odleglosci miedzy parami wierzchołków grafu.
|
|||
|
drzewa etykietowane
|
y drzewa, których wierzchoªki maj¡ etykiety b¦d¡ce kolejnymi dodatnimi liczbami naturalnymi
|
|||
|
Twierdzenie (Cayley, 1989):
|
Istnieje n^n−2 różnych n-wierzchołkowych drzew etykietowanych. dowód: wynika z wzajemnej jednoznaczno±ci kodowania i dedokowania Prüfera, gdy» dokªadnie tyle istnieje ró»nych ci¡gów o takiej formie
|
|||
|
Przeszukiwanie grafu
|
Rezultatem caªego przeszukiwania jest wi¦c zbiór (rozª¡cznych wierzchoªkowo) drzew przeszukiwania zwany lasem przeszukiwania.
|
|||
|
Klasy kacja kraw¦dzi w wyniku przeszukiwania grafu
|
kazda krawedz (u, v) nalezy do dokl. 1 z kategorii: drzewowa (T): v jest odwiedzony z u w wyniku przej±cia (u, v) 2. w przód (F): nie jest drzewowa i v jest potomkiem u w drzewie 3. w tył (B): nie jest drzewowa i v jest przodkiem u w drzewie 4. poprzeczna (C): w pozostaªych przypadkach pomiędzy gałęziami
|
|||
|
Rodzaje kraw¦dzi w grafach - DSF i BSF
|
DFS: nieskierowane: nie ma w przód ani poprzecznych, DFS: skierowane: wszystkie 4, BFS: nieskierowane: nie ma w przód ani wstecz, BFS skierowane: nie ma w przód
|
|||
|
Ścieżka DFS
|
fragment drzewa przeszukiwania DFS zbudowany do momentu, gdy jakiś wierzchołek staje się czarny.
|
|||
|
Fakt ścieżka DFS
|
Jeżeli P jest ścieżką DFS kończącą się na wierzchołku t, to wszyscy sąsiedzi t leżą na ścieżce P. Ponadto, jeżeli deg(t) > 1 to wszyscy sąsiedzi t leżą na pewnym cyklu
|
|||
|
Kontrakcja
|
podgrafu H: uczynienie z H pojedynczego wierzchołka. (algorytm stopniowo dokonuje kontrakcji wszystkich wykrytych cykli aż zostaną same mosty
|
|||
