Matematyka dyskretna 1/Test 13: Grafy II

Pełny graf dwudzielny ${{𝒦}}_{3,3}$ :

jest eulerowski Źle

jest hamiltonowski Dobrze

jest planarny Źle

nie jest ani eulerowski ani planarny Źle

Pełny graf $100$-elementowy:

jest grafem Hamiltonowskim Dobrze

jest grafem Eulerowskim Źle

jest spójny Źle

jest dwudzielny Źle

jest stukolorowalny Dobrze

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

sam jest cyklem o parzystej liczbie krawędzi Źle

jest cyklem Dobrze

ma wierzchołki wyłącznie o stopniu $2$ Dobrze

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

Jeśli graf $\mathbf{𝐆}$ jest eulerowski, to:

graf $\mathbf{𝐆}$ jest hamiltonowski Źle

każdy wierzchołek w grafie $\mathbf{𝐆}$ ma parzysty stopień Dobrze

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

jeśli dodatkowo $\mathbf{𝐆}$ jest hamiltonowski, to po usunięciu cyklu Hamiltona graf $\mathbf{𝐆}$ dalej jest eulerowski Źle

Graf o $101$ wierzchołkach:

w którym wszystkie wierzchołki są stopnia $50$ , jest hamiltonowski Źle

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

w którym dowolne dwa niesąsiednie wierzchołki $v$ i $w$ spełniają $\mathrm{deg}v+\mathrm{deg}w\ge 100$ jest hamiltonowski Źle

w którym dowolne dwa sąsiednie wierzchołki $v$ i $w$ spełniają $\mathrm{deg}v+\mathrm{deg}w\ge 100$ jest hamiltonowski Źle

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

graf $\mathbf{𝐆}$ jest hamiltonowski Dobrze

graf $\mathbf{𝐆}$ jest eulerowski Źle

w grafie $\mathbf{𝐆}$ każdy wierzchołek z $V_1$ ma co najmniej dwu sąsiadów Źle

dowolny zbiór niezależny w ma co najwyżej $\left|V_2\right|$ wierzchołków Dobrze

Grafem $100$ -spójnym jest:

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

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

klika ${{𝒦}}_{101}$ Dobrze

pełny graf dwudzielny ${{𝒦}}_{100,100}$ Źle

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

jest dokładnie $38$ krawędzi Źle

jest dokładnie $20$ krawędzi Dobrze

dowolny wierzchołek ma stopień co najmniej $2$ Dobrze

istnieje wierzchołek o stopniu co najmniej $3$ Źle