4-7
0 28 flashcards
adamomasz
soru  |
cevap |
|||
|---|---|---|---|---|
|
Grafy platońskie
|
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)
|
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) -
|
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
|
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
|
- liczba jej krawędzi
|
|||
|
Droga (ścieżka) -
|
- 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
|
- ś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
|
długość najkrótszego cyklu elementarnego w grafe (czyli takiego cyklu, gdzie nie powtarzają się wierzchołki)
|
|||
|
Zbiór rozspajający
|
taki zbiór krawędzi grafu, po usunięciu którego graf ma więcej składowych spójnych
|
|||
|
Rozcięcie
|
minimalny zbiór rozspajający (żaden jego podzbiór właściwy nie jest rozspajający).
|
|||
|
Spójność krawędziowa
|
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
|
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)
|
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
|
Blok: maksymalny podgraf grafu nie zawierający wierzchołków rozdzielających dla tego podgrafu
|
|||
|
Cykl Eulera
|
taki cykl, który nie powtarza krawędzi i zawiera wszystkie krawędzie grafu.
|
|||
|
Graf eulerowski -
|
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
|
ścieżka, która nie powtarza krawędzi i zawiera wszystkie krawędzie grafu.
|
|||
|
. Pół-eulerowski
|
- 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
|
cykl zawierający każdy wierzchołek dokładnie raz.
|
|||
|
Graf hamiltonowski
|
zawiera cykl Hamiltona
|
|||
|
Pół-hamiltonowski
|
zawiera ścieżkę przechodzącą przez każdy wierzchołek dokładnie raz.
|
|||
|
Drzewo
|
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
|
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)
|
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
|
liczba krawędzi dopełnienia dowolnego lasu rozpinającego grafu G.
|
|||
|
Rząd rozcięcia - ξ(G)
|
liczba krawędzi w dowolnym lesie rozpinającym G. 𝛄(G) + ξ(G) = |E|
|
|||
|
Zbiór cykli fundamentalnych
|
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
|
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.
|
|||
