Matematyka dyskretna 1/Test 13: Grafy II

From Studia Informatyczne

Pełny graf dwudzielny \displaystyle \mathcal{K}_{3,3} :

jest eulerowski

jest hamiltonowski

jest planarny

nie jest ani eulerowski ani planarny


Pełny graf \displaystyle 100-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 \displaystyle 2

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 \displaystyle \mathbf{G} jest eulerowski, to:

graf \displaystyle \mathbf{G} jest hamiltonowski

każdy wierzchołek w grafie \displaystyle \mathbf{G} ma parzysty stopień

graf \displaystyle \mathbf{G} 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 \displaystyle \mathbf{G} jest hamiltonowski, to po usunięciu cyklu Hamiltona graf \displaystyle \mathbf{G} dalej jest eulerowski


Graf o \displaystyle 101 wierzchołkach:

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

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

w którym dowolne dwa niesąsiednie wierzchołki \displaystyle v i \displaystyle w spełniają \displaystyle \deg{v}+\deg{w}\geq 100 jest hamiltonowski

w którym dowolne dwa sąsiednie wierzchołki \displaystyle v i \displaystyle w spełniają \displaystyle \deg{v}+\deg{w}\geq 100 jest hamiltonowski


Który z warunków wystarcza na to, by w grafie dwudzielnym \displaystyle \mathbf{G}=\left( V_1\cup V_2, E \right) istniało pełne skojarzenie \displaystyle V_1 z \displaystyle V_2 ?

graf \displaystyle \mathbf{G} jest hamiltonowski

graf \displaystyle \mathbf{G} jest eulerowski

w grafie \displaystyle \mathbf{G} każdy wierzchołek z \displaystyle V_1 ma co najmniej dwu sąsiadów

dowolny zbiór niezależny w ma co najwyżej \displaystyle \left\vert V_2 \right\vert wierzchołków


Grafem \displaystyle 100 -spójnym jest:

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

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

klika \displaystyle \mathcal{K}_{101}

pełny graf dwudzielny \displaystyle \mathcal{K}_{100,100}


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

jest dokładnie \displaystyle 38 krawędzi

jest dokładnie \displaystyle 20 krawędzi

dowolny wierzchołek ma stopień co najmniej \displaystyle 2

istnieje wierzchołek o stopniu co najmniej \displaystyle 3