Tekst źródłowy strony Matematyka dyskretna 1/Test 12: Grafy

<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>n</math>-elementowym jest:
<wrongoption><math>2^{n^2}</math></wrongoption>
<rightoption><math>2^{n^2-n}</math></rightoption>
<wrongoption><math>2^{2^n}</math></wrongoption>
<wrongoption><math>2^{2^n-n}</math></wrongoption>
<wrongoption><math>2^{n \choose 2}</math></wrongoption>
</quiz>


<quiz>Różnych grafów nieskierowanych bez cykli jednoelementowych  w zbiorze <math>n</math>-elementowym jest:
<wrongoption><math>2^{n^2}</math></wrongoption>
<wrongoption><math>2^{n^2-n}</math></wrongoption>
<wrongoption><math>2^{2^n}</math></wrongoption>
<wrongoption><math>2^{2^n-n}</math></wrongoption>
<rightoption><math>2^{n \choose 2}</math></rightoption>
</quiz>


<quiz>Zaznacz zdania prawdziwe:
<wrongoption>W każdym grafie prostym <math>G= \left( V;E \right)</math> relacja <math>E</math> musi być zwrotna.</wrongoption>
<rightoption>W grafie nieskierowanym  <math>G= \left( V,E \right)</math> relacja <math>E</math> jest symetryczna.</rightoption>
<wrongoption>Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków.</wrongoption>
<rightoption>W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.</rightoption>
</quiz>


<quiz>Zaznacz zdania prawdziwe dla grafów nieskierowanych:
<rightoption> podgraf indukowany grafu pełnego jest grafem pełnym</rightoption>
<rightoption> każdy graf jest podgrafem jakiegoś grafu pełnego</rightoption>
<wrongoption> każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego</wrongoption>
<wrongoption> graf pełny ma zawsze parzystą liczbę krawędzi</wrongoption>
<rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień</rightoption></quiz>


<quiz>Jaka jest najmniejsza liczba krawędzi w grafie
nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:
<wrongoption> <math>99</math></wrongoption>
<rightoption> <math>97</math></rightoption>
<wrongoption> <math>98</math></wrongoption>
<wrongoption> <math>100</math></wrongoption>
<wrongoption> <math>\frac{100 \cdot 99}{3}</math></wrongoption>
</quiz>


<quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>K_{1000,1000}</math>:
<rightoption> <math>1000 \cdot 1000</math></rightoption>
<wrongoption> <math>1000!</math></wrongoption>
<wrongoption> <math>1000 \choose 2</math></wrongoption>
<wrongoption> <math>1000 \choose 50</math></wrongoption>
<wrongoption> <math>2000 \choose 1000</math></wrongoption>
</quiz>


<quiz>W pełnym grafie <math>100</math>-elementowym:
<wrongoption> każde drzewo rozpinające ma <math>100</math> krawędzi</wrongoption>
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>100</math> krawędzi</wrongoption>
<rightoption>  każde drzewo rozpinające ma <math>99</math> krawędzi</rightoption>
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>99</math> krawędzi</wrongoption>
<wrongoption> nie ma drzew rozpinających</wrongoption>
</quiz>


<quiz>W pełnym grafie dwudzielnym <math>K_{50,50}</math>:
<wrongoption> każde drzewo rozpinające ma <math>50</math> krawędzi</wrongoption>
<wrongoption> każde drzewo rozpinające ma <math>100</math> krawędzi</wrongoption>
<rightoption>  każde drzewo rozpinające ma <math>99</math> krawędzi</rightoption>
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>99</math> krawędzi</wrongoption>
<wrongoption> nie ma drzew rozpinających</wrongoption>
</quiz>


<quiz>W <math>100</math> elementowym grafie o trzech składowych spójnych:
<wrongoption> jakiś las rozpinający ma <math>100</math> krawędzi</wrongoption>
<wrongoption> jakiś las rozpinający ma <math>99</math> krawędzi</wrongoption>
<wrongoption> jakiś las rozpinający ma <math>98</math> krawędzi</wrongoption>
<rightoption>  jakiś las rozpinający ma <math>97</math> krawędzi</rightoption>
<wrongoption> może nie być lasu rozpinającego</wrongoption>
</quiz>


<quiz>Pełny graf <math>100</math>-elementowy:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<wrongoption> jest spójny</wrongoption>
<rightoption> jest dwudzielny</rightoption>
<rightoption> jest stukolorowalny</rightoption>
</quiz>


<quiz>Pełny graf dwudzielny <math>K_{25,25}</math>:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<rightoption> zawiera cykl <math>4</math> wierzchołkach jako podgraf indukowany</rightoption>
<wrongoption> zawiera cykl <math>6</math> wierzchołkach jako podgraf indukowany </wrongoption>
<rightoption> jest trójkolorowalny</rightoption>
</quiz>


<quiz>Graf o  <math>2005</math>  wierzchołkach, z których każdy ma stopień  <math>101</math> :
<wrongoption>ma  <math>202505</math>  krawędzi</wrongoption>
<wrongoption>ma  <math>2106</math>  krawędzi</wrongoption>
<wrongoption>ma  <math>405010</math>   krawędzi</wrongoption>
<rightoption>nie istnieje</rightoption>
</quiz> 


<quiz>Jeśli  <math>\mathbf{G}_1=\left( V,E_1 \right)</math>  i  <math>\mathbf{G}_2=\left( V,E_2 \right)</math>  
są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>V</math> , to:
<rightoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  może być spójny</rightoption>
<wrongoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  jest spójny</wrongoption>
<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  może nie być spójny</rightoption>
<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  nie jest spójny</rightoption>
</quiz> 


<quiz>Graf  <math>\mathbf{P}_4</math>  to graf, który składa się jedynie ze ścieżki 
odwiedzającej  <math>4</math>  wierzchołki, 
czyli  <math>\mathsf{ V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace</math>  
oraz  <math>\mathsf{ E}\!\left(\mathbf{P}_4\right)=\left\lbrace \left\lbrace a,b \right\rbrace,\left\lbrace b,c \right\rbrace,\left\lbrace c,d \right\rbrace \right\rbrace</math> . 
W grafie spójnym, w którym nie ma 
podgrafu indukowanego izomorficznego do  <math>\mathbf{P}_4</math> :
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy</rightoption>
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa</rightoption>
<wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden</wrongoption>
<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\mathcal{K}_{3}</math></wrongoption>
</quiz> 


<quiz>Zaznacz zdania prawdziwe:
<rightoption>Każdy graf pusty jest grafem dwudzielnym.</rightoption>
<wrongoption>Każdy graf pełny jest grafem dwudzielnym.</wrongoption>
<wrongoption>Graf  <math>\mathcal{K}_{3}</math>  jest grafem dwudzielnym.</wrongoption>
<rightoption>Graf  <math>\mathcal{K}_{2}</math>  jest grafem dwudzielnym.</rightoption>
</quiz> 


<quiz>Zaznacz zdania prawdziwe:
<rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.</rightoption>
<rightoption>Graf  <math>\mathcal{K}_{4}</math>  jest grafem planarnym.</rightoption>
<wrongoption>Graf  <math>\mathcal{K}_{5}</math>  jest grafem planarnym.</wrongoption>
<wrongoption>Każdy graf dwudzielny jest grafem planarnym.</wrongoption>
</quiz> 


<quiz>Graf o  <math>100</math>  wierzchołkach:
<wrongoption>jeśli ma  <math>99</math>  krawędzi, to jest drzewem.</wrongoption>
<wrongoption>jeśli ma  <math>100</math>  krawędzi, to jest drzewem.</wrongoption>
<wrongoption>jeśli ma  <math>4851</math>  krawędzi, to jest spójny.</wrongoption>
<rightoption>jeśli ma  <math>4852</math>  krawędzi, to jest spójny.</rightoption>
</quiz> 


<quiz>Na to by graf  <math>\mathbf{T}</math>  był drzewem potrzeba i wystarcza, by:
<wrongoption> <math>\mathbf{T}</math>  nie zawierał cykli</wrongoption>
<rightoption> <math>\mathbf{T}</math>  był spójny i miał  <math>\left\vert V \right\vert-1</math>  krawędzi</rightoption>
<rightoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  były połączone dokładnie jedną drogą</rightoption>
<wrongoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  leżały na dokładnie jednym cyklu</wrongoption>
</quiz>