Matematyka dyskretna 1/Test 14: Grafy III

Który z grafów przedstawionych na Rysunku 1 jest planarny?

<flash>file=Test petersen4.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 1

graf przedstawiony na rysunku 1.a. Źle

graf przedstawiony na rysunku 1.b. Źle

graf przedstawiony na rysunku 1.c. Źle

graf przedstawiony na rysunku 1.d. Dobrze

Który z grafów przedstawionych na Rysunku 2 jest homeomorficzny z kliką ${{𝒦}}_5$ ?

<flash>file=Test klika5.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 2

graf przedstawiony na rysunku 2.a. Źle

graf przedstawiony na rysunku 2.b. Źle

graf przedstawiony na rysunku 2.c. Dobrze

graf przedstawiony na rysunku 2.d. Źle

Spójny graf planarny o $20$ wierzchołkach, z których każdy jest stopnia $3$ ma:

$11$ ścian Źle

$12$ ścian Dobrze

$22$ ścian Źle

$24$ ścian Źle

Ile spójnych składowych ma graf planarny o $121$ wierzchołkach, $53$ krawędziach, oraz $30$ ścianach?

$98$ Dobrze

$99$ Źle

$100$ Źle

$143$ Źle

Niech ${\mathbf{𝐆}}^{*}$ będzie grafem geometrycznie dualnym do grafu płaskiego $\mathbf{𝐆}$ . Podzbiór $C$ zbioru krawędzi grafu $\mathbf{𝐆}$ jest cyklem w grafie $\mathbf{𝐆}$ wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru $C$

posiada parzystą liczbę elementów Źle

posiada nieparzystą liczbę elementów Źle

jest cyklem grafu ${\mathbf{𝐆}}^{*}$ Źle

jest rozcięciem grafu ${\mathbf{𝐆}}^{*}$ Dobrze

Spójny graf prosty, który nie jest pełny, i w którym wszystkie wierzchołki mają stopień nie większy niż $k$ jest:

$(k-1)$ -kolorowalny Źle

$k$ -kolorowalny Dobrze

$(k+1)$ -kolorowalny Dobrze

$2k$ -kolorowalny Dobrze

Iloma kolorami można pokolorować polityczną mapę Europy?

$3$ Źle

$4$ Dobrze

$5$ Dobrze

$6$ Dobrze

W grafie prostym zachodzi:

$\chi \left(\mathbf{𝐆}\right)\le {\chi }_s\left(\mathbf{𝐆}\right)+1$ Dobrze

$\chi \left(\mathbf{𝐆}\right)\le {\chi }_s\left(\mathbf{𝐆}\right)$ Źle

$\chi \left(\mathbf{𝐆}\right)\ge {\chi }_s\left(\mathbf{𝐆}\right)+1$ Źle

$\chi \left(\mathbf{𝐆}\right)={\chi }_s\left(\mathbf{𝐆}\right)$ Źle

Pełny graf dwudzielny $K_{50,50}$:

jest grafem Hamiltonowskim Dobrze

jest grafem Eulerowskim Dobrze

jest lasem Źle

jest dwukolorowalny Dobrze

jest 49-kolorowalny Dobrze