Matematyka dyskretna 1/Test 13: Grafy II: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu – „ </math>” na „</math>”
 
(Nie pokazano 1 pośredniej wersji utworzonej przez tego samego użytkownika)
Linia 1: Linia 1:
<quiz>Pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{3,3} </math> :
<quiz>Pełny graf dwudzielny  <math>\mathcal{K}_{3,3}</math> :
<wrongoption>jest eulerowski</wrongoption>
<wrongoption>jest eulerowski</wrongoption>
<rightoption>jest hamiltonowski</rightoption>
<rightoption>jest hamiltonowski</rightoption>
Linia 7: Linia 7:




<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:
<quiz>Pełny graf <math>100</math>-elementowy:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<rightoption> jest grafem Hamiltonowskim</rightoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
Linia 19: Linia 19:
<wrongoption>sam jest cyklem o parzystej liczbie krawędzi</wrongoption>
<wrongoption>sam jest cyklem o parzystej liczbie krawędzi</wrongoption>
<rightoption>jest cyklem</rightoption>
<rightoption>jest cyklem</rightoption>
<rightoption>ma wierzchołki wyłącznie o stopniu  <math>\displaystyle 2 </math> </rightoption>
<rightoption>ma wierzchołki wyłącznie o stopniu  <math>2</math> </rightoption>
<wrongoption>jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi,  
<wrongoption>jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi,  
przy czym każdy z nich jest cyklem</wrongoption>
przy czym każdy z nich jest cyklem</wrongoption>
Linia 25: Linia 25:




<quiz>Jeśli graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski, to:
<quiz>Jeśli graf  <math>\mathbf{G}</math>  jest eulerowski, to:
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski</wrongoption>
<wrongoption>graf  <math>\mathbf{G}</math>  jest hamiltonowski</wrongoption>
<rightoption>każdy wierzchołek w grafie  <math>\displaystyle \mathbf{G} </math>  ma parzysty stopień</rightoption>
<rightoption>każdy wierzchołek w grafie  <math>\mathbf{G}</math>  ma parzysty stopień</rightoption>
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  jest sumą grafów o tych samych wierzchołkach  
<rightoption>graf  <math>\mathbf{G}</math>  jest sumą grafów o tych samych wierzchołkach  
ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem</rightoption>
ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem</rightoption>
<wrongoption>jeśli dodatkowo  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski,  
<wrongoption>jeśli dodatkowo  <math>\mathbf{G}</math>  jest hamiltonowski,  
to po usunięciu cyklu Hamiltona graf  <math>\displaystyle \mathbf{G} </math>  dalej jest eulerowski</wrongoption>
to po usunięciu cyklu Hamiltona graf  <math>\mathbf{G}</math>  dalej jest eulerowski</wrongoption>
</quiz>  
</quiz>  




<quiz>Graf o  <math>\displaystyle 101 </math>  wierzchołkach:
<quiz>Graf o  <math>101</math>  wierzchołkach:
<wrongoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 50 </math> , jest hamiltonowski</wrongoption>
<wrongoption>w którym wszystkie wierzchołki są stopnia  <math>50</math> , jest hamiltonowski</wrongoption>
<rightoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 51 </math> , jest hamiltonowski</rightoption>
<rightoption>w którym wszystkie wierzchołki są stopnia  <math>51</math> , jest hamiltonowski</rightoption>
<wrongoption>w którym dowolne dwa niesąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math>   
<wrongoption>w którym dowolne dwa niesąsiednie wierzchołki  <math>v</math>  i  <math>w</math>   
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski</wrongoption>
spełniają  <math>\deg{v}+\deg{w}\geq 100</math>  jest hamiltonowski</wrongoption>
<wrongoption>w którym dowolne dwa sąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math>   
<wrongoption>w którym dowolne dwa sąsiednie wierzchołki  <math>v</math>  i  <math>w</math>   
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski</wrongoption>
spełniają  <math>\deg{v}+\deg{w}\geq 100</math>  jest hamiltonowski</wrongoption>
</quiz>  
</quiz>  




<quiz>Który z warunków wystarcza na to,  
<quiz>Który z warunków wystarcza na to,  
by w grafie dwudzielnym  <math>\displaystyle \mathbf{G}=\left( V_1\cup V_2, E \right) </math>  
by w grafie dwudzielnym  <math>\mathbf{G}=\left( V_1\cup V_2, E \right)</math>  
istniało pełne skojarzenie  <math>\displaystyle V_1 </math>  z  <math>\displaystyle V_2 </math> ?
istniało pełne skojarzenie  <math>V_1</math>  z  <math>V_2</math> ?
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski</rightoption>
<rightoption>graf  <math>\mathbf{G}</math>  jest hamiltonowski</rightoption>
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski</wrongoption>
<wrongoption>graf  <math>\mathbf{G}</math>  jest eulerowski</wrongoption>
<wrongoption>w grafie  <math>\displaystyle \mathbf{G} </math>  każdy wierzchołek z  <math>\displaystyle V_1 </math>   
<wrongoption>w grafie  <math>\mathbf{G}</math>  każdy wierzchołek z  <math>V_1</math>   
ma co najmniej dwu sąsiadów</wrongoption>
ma co najmniej dwu sąsiadów</wrongoption>
<rightoption>dowolny zbiór niezależny w  ma co najwyżej  <math>\displaystyle \left\vert V_2 \right\vert </math>  wierzchołków</rightoption>
<rightoption>dowolny zbiór niezależny w  ma co najwyżej  <math>\left\vert V_2 \right\vert</math>  wierzchołków</rightoption>
</quiz>  
</quiz>  




<quiz>Grafem  <math>\displaystyle 100 </math> -spójnym jest:
<quiz>Grafem  <math>100</math> -spójnym jest:
<rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje  <math>\displaystyle 100 </math>   
<rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje  <math>100</math>   
dróg wierzchołkowo rozłącznych</rightoption>
dróg wierzchołkowo rozłącznych</rightoption>
<wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej  <math>\displaystyle 99 </math>  wierzchołków</wrongoption>
<wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej  <math>99</math>  wierzchołków</wrongoption>
<rightoption>klika  <math>\displaystyle \mathcal{K}_{101} </math></rightoption>
<rightoption>klika  <math>\mathcal{K}_{101}</math></rightoption>
<wrongoption>pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{100,100} </math></wrongoption>
<wrongoption>pełny graf dwudzielny  <math>\mathcal{K}_{100,100}</math></wrongoption>
</quiz>  
</quiz>  




<quiz>W  <math>\displaystyle 2 </math> -spójnym krawędziowo grafie o  <math>\displaystyle 20 </math>  wierzchołkach  
<quiz>W  <math>2</math> -spójnym krawędziowo grafie o  <math>20</math>  wierzchołkach  
i minimalnej liczbie krawędzi:
i minimalnej liczbie krawędzi:
<wrongoption>jest dokładnie  <math>\displaystyle 38 </math>  krawędzi</wrongoption>
<wrongoption>jest dokładnie  <math>38</math>  krawędzi</wrongoption>
<rightoption>jest dokładnie  <math>\displaystyle 20 </math>  krawędzi</rightoption>
<rightoption>jest dokładnie  <math>20</math>  krawędzi</rightoption>
<rightoption>dowolny wierzchołek ma stopień co najmniej  <math>\displaystyle 2 </math> </rightoption>
<rightoption>dowolny wierzchołek ma stopień co najmniej  <math>2</math> </rightoption>
<wrongoption>istnieje wierzchołek o stopniu co najmniej  <math>\displaystyle 3 </math> </wrongoption>
<wrongoption>istnieje wierzchołek o stopniu co najmniej  <math>3</math> </wrongoption>
</quiz>
</quiz>

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

Pełny graf dwudzielny 𝒦3,3 :

jest eulerowski

jest hamiltonowski

jest planarny

nie jest ani eulerowski ani planarny


Pełny graf 100-elementowy:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest spójny

jest dwudzielny

jest stukolorowalny


Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera:

sam jest cyklem o parzystej liczbie krawędzi

jest cyklem

ma wierzchołki wyłącznie o stopniu 2

jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem


Jeśli graf 𝐆 jest eulerowski, to:

graf 𝐆 jest hamiltonowski

każdy wierzchołek w grafie 𝐆 ma parzysty stopień

graf 𝐆 jest sumą grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem

jeśli dodatkowo 𝐆 jest hamiltonowski, to po usunięciu cyklu Hamiltona graf 𝐆 dalej jest eulerowski


Graf o 101 wierzchołkach:

w którym wszystkie wierzchołki są stopnia 50 , jest hamiltonowski

w którym wszystkie wierzchołki są stopnia 51 , jest hamiltonowski

w którym dowolne dwa niesąsiednie wierzchołki v i w spełniają deg⁡v+deg⁡w≥100 jest hamiltonowski

w którym dowolne dwa sąsiednie wierzchołki v i w spełniają deg⁡v+deg⁡w≥100 jest hamiltonowski


Który z warunków wystarcza na to, by w grafie dwudzielnym 𝐆=(V1∪V2,E) istniało pełne skojarzenie V1 z V2 ?

graf 𝐆 jest hamiltonowski

graf 𝐆 jest eulerowski

w grafie 𝐆 każdy wierzchołek z V1 ma co najmniej dwu sąsiadów

dowolny zbiór niezależny w ma co najwyżej |V2| wierzchołków


Grafem 100 -spójnym jest:

graf w którym pomiędzy dowolnymi wierzchołkami istnieje 100 dróg wierzchołkowo rozłącznych

graf, którego każdy zbiór rozdzielający ma co najmniej 99 wierzchołków

klika 𝒦101

pełny graf dwudzielny 𝒦100,100


W 2 -spójnym krawędziowo grafie o 20 wierzchołkach i minimalnej liczbie krawędzi:

jest dokładnie 38 krawędzi

jest dokładnie 20 krawędzi

dowolny wierzchołek ma stopień co najmniej 2

istnieje wierzchołek o stopniu co najmniej 3

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