→ Wykl 3 I 4 →学習を始める

質問		答え
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

wykl 3 i 4

コメントを投稿するにはログインする必要があります。

もっと