Matematyka dyskretna 1/Test 13: Grafy II

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Pełny graf dwudzielny  :

jest eulerowski

jest hamiltonowski

jest planarny

nie jest ani eulerowski ani planarny


Pełny graf -elementowy:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest spójny

jest dwudzielny

jest stukolorowalny


Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera:

sam jest cyklem o parzystej liczbie krawędzi

jest cyklem

ma wierzchołki wyłącznie o stopniu

jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem


Jeśli graf jest eulerowski, to:

graf jest hamiltonowski

każdy wierzchołek w grafie ma parzysty stopień

graf jest sumą grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem

jeśli dodatkowo jest hamiltonowski, to po usunięciu cyklu Hamiltona graf dalej jest eulerowski


Graf o wierzchołkach:

w którym wszystkie wierzchołki są stopnia , jest hamiltonowski

w którym wszystkie wierzchołki są stopnia , jest hamiltonowski

w którym dowolne dwa niesąsiednie wierzchołki i spełniają jest hamiltonowski

w którym dowolne dwa sąsiednie wierzchołki i spełniają jest hamiltonowski


Który z warunków wystarcza na to, by w grafie dwudzielnym istniało pełne skojarzenie z  ?

graf jest hamiltonowski

graf jest eulerowski

w grafie każdy wierzchołek z ma co najmniej dwu sąsiadów

dowolny zbiór niezależny w ma co najwyżej wierzchołków


Grafem -spójnym jest:

graf w którym pomiędzy dowolnymi wierzchołkami istnieje dróg wierzchołkowo rozłącznych

graf, którego każdy zbiór rozdzielający ma co najmniej wierzchołków

klika

pełny graf dwudzielny


W -spójnym krawędziowo grafie o wierzchołkach i minimalnej liczbie krawędzi:

jest dokładnie krawędzi

jest dokładnie krawędzi

dowolny wierzchołek ma stopień co najmniej

istnieje wierzchołek o stopniu co najmniej