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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Nie podano opisu zmian
m Zastępowanie tekstu – „ </math>” na „</math>”
 
(Nie pokazano 5 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
[[File:Test petersen4.svg|150x150px|thumb|right|Rysunek 1]]
[[File:Test klika5.svg|150x150px|thumb|right|Rysunek 2]]
<quiz>Który z grafów przedstawionych na Rysunku 1 jest planarny?
<quiz>Który z grafów przedstawionych na Rysunku 1 jest planarny?
<div class="thumb tright"><div style="width:250px;">
<flash>file=Test petersen4.swf|width=250|height=250</flash>
<div.thumbcaption>Rysunek 1</div></div>
</div>


<wrongoption>graf przedstawiony na rysunku 1.a.</wrongoption>
<wrongoption>graf przedstawiony na rysunku 1.a.</wrongoption>
Linia 11: Linia 10:
</quiz>  
</quiz>  


<quiz>Który z grafów przedstawionych na Rysunku 2 jest homeomorficzny z kliką  <math>\displaystyle \mathcal{K}_{5} </math> ?
<quiz>Który z grafów przedstawionych na Rysunku 2 jest homeomorficzny z kliką  <math>\mathcal{K}_{5}</math> ?
 
 
<div class="thumb tright"><div style="width:250px;">
<flash>file=Test klika5.swf|width=250|height=250</flash>
<div.thumbcaption>Rysunek 2</div></div>
</div>


<wrongoption>graf przedstawiony na rysunku 2.a.</wrongoption>
<wrongoption>graf przedstawiony na rysunku 2.a.</wrongoption>
Linia 27: Linia 19:




<quiz>Spójny graf planarny o  <math>\displaystyle 20 </math>  wierzchołkach, z których każdy jest stopnia  <math>\displaystyle 3 </math>  ma:
<quiz>Spójny graf planarny o  <math>20</math>  wierzchołkach, z których każdy jest stopnia  <math>3</math>  ma:
<wrongoption> <math>\displaystyle 11 </math>  ścian</wrongoption>
<wrongoption> <math>11</math>  ścian</wrongoption>
<rightoption> <math>\displaystyle 12 </math>  ścian</rightoption>
<rightoption> <math>12</math>  ścian</rightoption>
<wrongoption> <math>\displaystyle 22 </math>  ścian</wrongoption>
<wrongoption> <math>22</math>  ścian</wrongoption>
<wrongoption> <math>\displaystyle 24 </math>  ścian</wrongoption>
<wrongoption> <math>24</math>  ścian</wrongoption>
</quiz>  
</quiz>  




<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?
<quiz>Ile spójnych składowych ma graf planarny o <math>121</math>  wierzchołkach, <math>53</math> krawędziach, oraz  <math>30</math>  ścianach?
<rightoption> <math>\displaystyle 98 </math> </rightoption>
<rightoption> <math>98</math> </rightoption>
<wrongoption> <math>\displaystyle 99 </math> </wrongoption>
<wrongoption> <math>99</math> </wrongoption>
<wrongoption> <math>\displaystyle 100 </math> </wrongoption>
<wrongoption> <math>100</math> </wrongoption>
<wrongoption> <math>\displaystyle 143 </math> </wrongoption>
<wrongoption> <math>143</math> </wrongoption>
</quiz>  
</quiz>  




<quiz>Niech  <math>\displaystyle \mathbf{G}^* </math>  będzie grafem geometrycznie dualnym do  
<quiz>Niech  <math>\mathbf{G}^*</math>  będzie grafem geometrycznie dualnym do  
grafu płaskiego  <math>\displaystyle \mathbf{G} </math> .
grafu płaskiego  <math>\mathbf{G}</math> .
Podzbiór  <math>\displaystyle C </math>  zbioru krawędzi grafu  <math>\displaystyle \mathbf{G} </math>  jest cyklem w grafie  <math>\displaystyle \mathbf{G} </math>   
Podzbiór  <math>C</math>  zbioru krawędzi grafu  <math>\mathbf{G}</math>  jest cyklem w grafie  <math>\mathbf{G}</math>   
wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru  <math>\displaystyle C </math>  
wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru  <math>C</math>  
<wrongoption>posiada parzystą liczbę elementów</wrongoption>
<wrongoption>posiada parzystą liczbę elementów</wrongoption>
<wrongoption>posiada nieparzystą liczbę elementów</wrongoption>
<wrongoption>posiada nieparzystą liczbę elementów</wrongoption>
<wrongoption>jest cyklem grafu  <math>\displaystyle \mathbf{G}^* </math> </wrongoption>
<wrongoption>jest cyklem grafu  <math>\mathbf{G}^*</math> </wrongoption>
<rightoption>jest rozcięciem grafu  <math>\displaystyle \mathbf{G}^* </math> </rightoption>
<rightoption>jest rozcięciem grafu  <math>\mathbf{G}^*</math> </rightoption>
</quiz>  
</quiz>  




<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:
<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>k</math> jest:
<wrongoption> <math>\displaystyle \left( k-1 \right) </math> -kolorowalny</wrongoption>
<wrongoption> <math>\left( k-1 \right)</math> -kolorowalny</wrongoption>
<rightoption> <math>\displaystyle k </math> -kolorowalny</rightoption>
<rightoption> <math>k</math> -kolorowalny</rightoption>
<rightoption> <math>\displaystyle \left( k+1 \right) </math> -kolorowalny</rightoption>
<rightoption> <math>\left( k+1 \right)</math> -kolorowalny</rightoption>
<rightoption> <math>\displaystyle 2k </math> -kolorowalny</rightoption>
<rightoption> <math>2k</math> -kolorowalny</rightoption>
</quiz>  
</quiz>  




<quiz>Iloma kolorami można pokolorować polityczną mapę Europy?
<quiz>Iloma kolorami można pokolorować polityczną mapę Europy?
<wrongoption> <math>\displaystyle 3 </math> </wrongoption>
<wrongoption> <math>3</math> </wrongoption>
<rightoption> <math>\displaystyle 4 </math> </rightoption>
<rightoption> <math>4</math> </rightoption>
<rightoption> <math>\displaystyle 5 </math> </rightoption>
<rightoption> <math>5</math> </rightoption>
<rightoption> <math>\displaystyle 6 </math> </rightoption>
<rightoption> <math>6</math> </rightoption>
</quiz>  
</quiz>  




<quiz>W grafie prostym zachodzi:
<quiz>W grafie prostym zachodzi:
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1 </math> </rightoption>
<rightoption> <math>\chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1</math> </rightoption>
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right) </math> </wrongoption>
<wrongoption> <math>\chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)</math> </wrongoption>
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\chi_s\!\left( \mathbf{G} \right)+1 </math> </wrongoption>
<wrongoption> <math>\chi\!\left( \mathbf{G} \right)\geq\chi_s\!\left( \mathbf{G} \right)+1</math> </wrongoption>
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)=\chi_s\!\left( \mathbf{G} \right) </math> </wrongoption>
<wrongoption> <math>\chi\!\left( \mathbf{G} \right)=\chi_s\!\left( \mathbf{G} \right)</math> </wrongoption>
</quiz>  
</quiz>  




<quiz>Pełny graf dwudzielny <math>\displaystyle K_{50,50}</math>:
<quiz>Pełny graf dwudzielny <math>K_{50,50}</math>:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<rightoption> jest grafem Hamiltonowskim</rightoption>
<rightoption> jest grafem Eulerowskim</rightoption>
<rightoption> jest grafem Eulerowskim</rightoption>

Aktualna wersja na dzień 10:04, 5 wrz 2023

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ą 𝒦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 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=80829”