4-7

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

Kommentár közzétételéhez be kell jelentkeznie.