Matematyka dyskretna 1/Test 14: Grafy III

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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ą  ?

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 wierzchołkach, z których każdy jest stopnia ma:

ścian

ścian

ścian

ścian


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


Niech będzie grafem geometrycznie dualnym do grafu płaskiego . Podzbiór zbioru krawędzi grafu jest cyklem w grafie wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru

posiada parzystą liczbę elementów

posiada nieparzystą liczbę elementów

jest cyklem grafu

jest rozcięciem grafu


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

-kolorowalny

-kolorowalny

-kolorowalny

-kolorowalny


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


W grafie prostym zachodzi:


Pełny graf dwudzielny :

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest lasem

jest dwukolorowalny

jest 49-kolorowalny