→ 4-7 → Начать обучение

Вопрос		Ответ
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.

4-7

Вы должны войти в свой аккаунт чтобы написать комментарий.

Ещё