Matematyka dyskretna 1/Test 14: Grafy III

From Studia Informatyczne



Rysunek 1


Rysunek 2

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

graf przedstawiony na rysunku 1.a.

graf przedstawiony na rysunku 1.b.

graf przedstawiony na rysunku 1.c.

graf przedstawiony na rysunku 1.d.

Który z grafów przedstawionych na Rysunku 2 jest homeomorficzny z kliką \displaystyle \mathcal{K}_{5} ?

graf przedstawiony na rysunku 2.a.

graf przedstawiony na rysunku 2.b.

graf przedstawiony na rysunku 2.c.

graf przedstawiony na rysunku 2.d.


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

\displaystyle 11 ścian

\displaystyle 12 ścian

\displaystyle 22 ścian

\displaystyle 24 ścian


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

\displaystyle 98

\displaystyle 99

\displaystyle 100

\displaystyle 143


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

posiada parzystą liczbę elementów

posiada nieparzystą liczbę elementów

jest cyklem grafu \displaystyle \mathbf{G}^*

jest rozcięciem grafu \displaystyle \mathbf{G}^*


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

\displaystyle \left( k-1 \right) -kolorowalny

\displaystyle k -kolorowalny

\displaystyle \left( k+1 \right) -kolorowalny

\displaystyle 2k -kolorowalny


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

\displaystyle 3

\displaystyle 4

\displaystyle 5

\displaystyle 6


W grafie prostym zachodzi:

\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1

\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)

\displaystyle \chi\!\left( \mathbf{G} \right)\geq\chi_s\!\left( \mathbf{G} \right)+1

\displaystyle \chi\!\left( \mathbf{G} \right)=\chi_s\!\left( \mathbf{G} \right)


Pełny graf dwudzielny \displaystyle K_{50,50}:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest lasem

jest dwukolorowalny

jest 49-kolorowalny