Matematyka dyskretna 1/Test 14: Grafy III: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 32: Linia 32:




<quiz>Ile spójnych składowych ma graf planarny o <math>\displaystyle 121 </math>  wierzchołkach,  
<quiz>Ile spójnych składowych ma graf planarny o <math>\displaystyle 121 </math>  wierzchołkach, <math>\displaystyle 53 </math> krawędziach, oraz  <math>\displaystyle 30 </math>  ścianach?
<math>\displaystyle 53 </math> krawędziach, oraz  <math>\displaystyle 30 </math>  ścianach?
<rightoption> <math>\displaystyle 98 </math> </rightoption>
<rightoption> <math>\displaystyle 98 </math> </rightoption>
<wrongoption> <math>\displaystyle 99 </math> </wrongoption>
<wrongoption> <math>\displaystyle 99 </math> </wrongoption>
Linia 52: Linia 51:




<quiz>Spójny graf prosty, który nie jest pełny,  
<quiz>Spójny graf prosty, który nie jest pełny, i w którym wszystkie wierzchołki  mają stopień nie większy niż  <math>\displaystyle k </math> jest:
i w którym wszystkie wierzchołki  mają stopień nie większy niż  <math>\displaystyle k </math> jest:
<wrongoption> <math>\displaystyle \left( k-1 \right) </math> -kolorowalny</wrongoption>
<wrongoption> <math>\displaystyle \left( k-1 \right) </math> -kolorowalny</wrongoption>
<rightoption> <math>\displaystyle k </math> -kolorowalny</rightoption>
<rightoption> <math>\displaystyle k </math> -kolorowalny</rightoption>

Wersja z 21:35, 18 wrz 2006

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


Rysunek z pliku: testpetersen4.eps


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ą 𝒦5 ?


Rysunek z pliku: testklika5.eps


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

11 ścian

12 ścian

22 ścian

24 ścian


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

98

99

100

143


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

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ż k jest:

(k−1) -kolorowalny

k -kolorowalny

(k+1) -kolorowalny

2k -kolorowalny


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

3

4

5

6


W grafie prostym zachodzi:

χ(𝐆)≤χs(𝐆)+1

χ(𝐆)≤χs(𝐆)

χ(𝐆)≥χs(𝐆)+1

χ(𝐆)=χs(𝐆)


Pełny graf dwudzielny K50,50:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest lasem

jest dwukolorowalny

jest 49-kolorowalny

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Test_14:_Grafy_III&oldid=53674”