→ 4-7 → Start Learning

Question		Answer
Grafy platońskie start learning		grafy, utworzone z krawędzi i wierzchołków wielościanów foremnych (np: sześcian). Wszystkie są regularne i planarne.
Grafy dwudzielne (Km,n) start learning		graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości.
(Hiper-) kostki (Qi) - start learning		hiperkostka Qi (rzędu i: wierzchołki są ciągami binarnymi długości i, są sąsiednie tylko gdy różnią się jednym bitem). Qi = Qi-1 x Q1. Kostka Qn składa się z dwóch kopii kostki Qn-1 oraz dodatkowo łączymy krawędziami każdy wierzchołek z "pierwszej" kostki Qn-1 z jego kopią w "drugiej" kostce Qn-1,
Dopełnienie grafu start learning		dopełnieniem G’ grafu G jest graf prosty, którego zbiorem wierzchołków jest V(G), i w którym dwa wierzchołki są sąsiednie w G’ ⇔ gdy nie są sąsiednie w G. G’ ma tylko te krawędzie, które były nieobecne w G.
Długość ścieżki start learning		- liczba jej krawędzi
Droga (ścieżka) - start learning		- naprzemienny ciąg wierzchołków i krawędzi (v0, e0, v1, eq, ..., vk, ek, ..., vl) taki, że krawędź ek zawsze łączy wierzchołki vk, vk+1. Droga prosta - nie powtarzają się krawędzie. Droga elementarna - nie powtarzają się wierzchołki
Cykl start learning		- ścieżka o długości co najmniej 3 (... dla grafów skierowanych >= 2), taka, że v0 == vl (początek i koniec są tożsame)
Obwód grafu start learning		długość najkrótszego cyklu elementarnego w grafe (czyli takiego cyklu, gdzie nie powtarzają się wierzchołki)
Zbiór rozspajający start learning		taki zbiór krawędzi grafu, po usunięciu którego graf ma więcej składowych spójnych
Rozcięcie start learning		minimalny zbiór rozspajający (żaden jego podzbiór właściwy nie jest rozspajający).
Spójność krawędziowa start learning		grafu spójnego G (oznaczenie: λ(G)) to liczba krawędzi najmniejszego rozcięcia. Graf jest k-spójny krawędziowo wtedy, gdy k <= λ(G), np. C4 jest 1-spójny krawędziowo i 2-spójny krawędziowo, ale nie 3-spójny krawędziowo.
Zbiór rozdzielający start learning		to taki podzbiór wierzchołków, po usunięciu którego (wraz z incydentnymi krawędziami) graf ma więcej składowych spójnych.
. Punkt artykulacji (wierzchołek rozdzielający/rozcinający) start learning		wierzchołek grafu G, którego usunięcie zwiększa liczbę spójnych składowych grafu. Inaczej: jednoelementowy zbiór rozdzielający.
Podział grafu na bloki start learning		Blok: maksymalny podgraf grafu nie zawierający wierzchołków rozdzielających dla tego podgrafu
Cykl Eulera start learning		taki cykl, który nie powtarza krawędzi i zawiera wszystkie krawędzie grafu.
Graf eulerowski - start learning		graf, w którym istnieje cykl Eulera, czyli daje się narysować bez odrywania długopisu zaczynając i kończąc w tym samym miejscu.
Ścieżka Eulera start learning		ścieżka, która nie powtarza krawędzi i zawiera wszystkie krawędzie grafu.
. Pół-eulerowski start learning		- taki, w którym istnieje ścieżka Eulera, czyli daje się narysować bez odrywania długopisu, niekoniecznie zaczynając i kończąc w tym samym miejscu.
Cykl Hamiltona start learning		cykl zawierający każdy wierzchołek dokładnie raz.
Graf hamiltonowski start learning		zawiera cykl Hamiltona
Pół-hamiltonowski start learning		zawiera ścieżkę przechodzącą przez każdy wierzchołek dokładnie raz.
Drzewo start learning		graf prosty, nieskierowany, który jest acykliczny i spójny, czyli taki graf, że z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność
Las start learning		prosty, niespójny i nieskierowany graf acykliczny, (czyli nie zawierający żadnych cykli). Wtedy jego spójne składowe są drzewami.
Drzewo spinające (rozpinające) start learning		Dla spójnego, nieskierowanego grafu prostego G=(V,E) to taki podgraf T tego grafu, który jest drzewem i zawiera wszystkie wierzchołki danego grafu. Graf niespójny nie posiada drzewa rozpinającego. Jeśli graf G jest niespójny, to graf będący suma drzew rozpinających jego składowych spójnych nazywamy lasem rozpinającym.
Rząd cykliczności (Liczba cyklomatyczna) - 𝛄(G start learning		liczba krawędzi dopełnienia dowolnego lasu rozpinającego grafu G.
Rząd rozcięcia - ξ(G) start learning		liczba krawędzi w dowolnym lesie rozpinającym G. 𝛄(G) + ξ(G) = \|E\|
Zbiór cykli fundamentalnych start learning		Niech L oznacza pewien las rozpinający grafu G. Zauważmy, że dodanie jakiejkolwiek krawędzi G nie należącej do L utworzy dokładnie jeden cykl. Taki cykl nazywamy cyklem fundamentalnym grafu G związanym z lasem rozpinającym L. Zbiór cykli fundamentalnych związanych z lasem L to zbiór wszystkich taki cykli.
Zbiór rozcięć fundamentalnych start learning		Niech L oznacza pewien las rozpinający grafu G. Gdy z lasu L usuniemy dowolną krawędź, to (w odpowiadającej jej składowe spójnej) powstają dwa rozłączne zbiory wierzchołków v1, v2. Zbiór wszystkich krawędzi G takich, że jeden koniec jest w v1 a drugi w v2 tworzy rozcięcie, które nazywamy rozcięciem fundamentalnym związanym z lasem L. Zbiór wszystkich taki rozcięcie nazywamy zbiorem rozcięć fundamentalnych związanych z lasem L.

4-7

You must sign in to write a comment

More