Test GR4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
(Nie pokazano 51 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
12121212121212121212121212121212
5555555555555555555555555555555555555555 Logika


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


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


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


<quiz>Zaznacz zdania prawdziwe dla grafów nieskierowanych:}
10101010101010101010101010101010101010101010101010 Logika
<rightoption> podgraf indukowany grafu pełnego jest grafem pełnym
<rightoption> każdy graf jest podgrafem jakiegoś grafu pełnego
<wrongoption> każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego
<wrongoption> graf pełny ma zawsze parzystą liczbę krawędzi
<rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień
</quiz>
 
<quiz>Jaka jest najmniejsza liczba krawędzi w grafie
nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:}
<wrongoption> <math>\displaystyle 99</math>
<rightoption> <math>\displaystyle 97</math>
<wrongoption> <math>\displaystyle 98</math>
<wrongoption> <math>\displaystyle 100</math>
<wrongoption> <math>\displaystyle \frac{100 \cdot 99}{3}</math>
</quiz>
 
<quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>\displaystyle K_{1000,1000}</math>:}
<rightoption> <math>\displaystyle 1000 \cdot 1000</math>
<wrongoption> <math>\displaystyle 1000!</math>
<wrongoption> <math>\displaystyle 1000 \choose 2</math>
<wrongoption> <math>\displaystyle 1000 \choose 50</math>
<wrongoption> <math>\displaystyle 2000 \choose 1000</math>
</quiz>
 
<quiz>W pełnym grafie <math>\displaystyle 100</math>-elementowym:}
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<rightoption>  każde drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> nie ma drzew rozpinających
</quiz>
 
<quiz>W pełnym grafie dwudzielnym <math>\displaystyle K_{50,50}</math>:}
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 50</math> krawędzi
<wrongoption> każde drzewo rozpinające ma <math>\displaystyle 100</math> krawędzi
<rightoption>  każde drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> dokładnie jedno drzewo rozpinające ma <math>\displaystyle 99</math> krawędzi
<wrongoption> nie ma drzew rozpinających
</quiz>
 
<quiz>W <math>\displaystyle 100</math> elementowym grafie o trzech składowych spójnych:}
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 100</math> krawędzi
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 99</math> krawędzi
<wrongoption> jakiś las rozpinający ma <math>\displaystyle 98</math> krawędzi
<rightoption>  jakiś las rozpinający ma <math>\displaystyle 97</math> krawędzi
<wrongoption> może nie być lasu rozpinającego
</quiz>
 
<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<wrongoption> jest spójny
<wrongoption> jest dwudzielny
<rightoption> jest stukolorowalny
</quiz>
 
<quiz>Pełny graf dwudzielny <math>\displaystyle K_{25,25}</math>:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<rightoption> zawiera cykl <math>\displaystyle 4</math> wierzchołkach jako podgraf indukowany
<wrongoption> zawiera cykl <math>\displaystyle 6</math> wierzchołkach jako podgraf indukowany
<rightoption> jest trójkolorowalny
</quiz>
 
<quiz>Graf o  <math>\displaystyle 2005 </math>  wierzchołkach, z których każdy ma stopień  <math>\displaystyle 101 </math> :}
<wrongoption>ma  <math>\displaystyle 202505 </math>  krawędzi}
<wrongoption>ma  <math>\displaystyle 2106 </math>  krawędzi}
<wrongoption>ma  <math>\displaystyle 405010 </math>  krawędzi}
<rightoption>nie istnieje}
</quiz>
 
<quiz>Jeśli  <math>\displaystyle \mathbf{G}_1=\left( V,E_1 \right) </math>  i  <math>\displaystyle \mathbf{G}_2=\left( V,E_2 \right) </math> 
są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>\displaystyle V </math> , to:}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  może być spójny}
<wrongoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  jest spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  może nie być spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  nie jest spójny}
</quiz>
 
<quiz>Graf  <math>\displaystyle \mathbf{P}_4 </math>  to graf, który składa się jedynie ze ścieżki
odwiedzającej  <math>\displaystyle 4 </math>  wierzchołki,
czyli  <math>\displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace </math> 
oraz  <math>\displaystyle {\sf 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>\displaystyle \mathbf{P}_4 </math> :}
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy}
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa}
<wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden}
<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\displaystyle \mathcal{K}_{3} </math> }
</quiz>
 
<quiz>Zaznacz zdania prawdziwe:}
<rightoption>Każdy graf pusty jest grafem dwudzielnym.}
<wrongoption>Każdy graf pełny jest grafem dwudzielnym.}
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{3} </math>  jest grafem dwudzielnym.}
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{2} </math>  jest grafem dwudzielnym.}
</quiz>
 
<quiz>Zaznacz zdania prawdziwe:}
<rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.}
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{4} </math>  jest grafem planarnym.}
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{5} </math>  jest grafem planarnym.}
<wrongoption>Każdy graf dwudzielny jest grafem planarnym.}
</quiz>
 
<quiz>Graf o  <math>\displaystyle 100 </math>  wierzchołkach:}
<wrongoption>jeśli ma  <math>\displaystyle 99 </math>  krawędzi, to jest drzewem.}
<wrongoption>jeśli ma  <math>\displaystyle 100 </math>  krawędzi, to jest drzewem.}
<wrongoption>jeśli ma  <math>\displaystyle 4850 </math>  krawędzi, to jest spójny.}
<rightoption>jeśli ma  <math>\displaystyle 4851 </math>  krawędzi, to jest spójny.}
</quiz>
 
<quiz>Na to by graf  <math>\displaystyle \mathbf{T} </math>  był drzewem potrzeba i wystarcza, by:}
<wrongoption> <math>\displaystyle \mathbf{T} </math>  nie zawierał cykli}
<rightoption> <math>\displaystyle \mathbf{T} </math>  był spójny i miał  <math>\displaystyle \left\vert V \right\vert-1 </math>  krawędzi}
<rightoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  były połączone dokładnie jedną drogą}
<wrongoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  leżały na dokładnie jednym cyklu}
</quiz>
 
131313131313131313131313131313
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy II'''
|-
|
 
|}
 
10mm
 
<quiz>Pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{3,3} </math> :}
<wrongoption>jest eulerowski}
<rightoption>jest hamiltonowski}
<wrongoption>jest planarny}
<wrongoption>nie jest ani eulerowski ani planarny}
</quiz>
 
<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:}
<rightoption> jest grafem Hamiltonowskim
<wrongoption> jest grafem Eulerowskim
<wrongoption> jest spójny
<wrongoption> jest dwudzielny
<rightoption> jest stukolorowalny
</quiz>
 
<quiz>Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera}
<wrongoption>sam jest cyklem o parzystej liczbie krawędzi}
<rightoption>jest cyklem}
<rightoption>ma wierzchołki wyłącznie o stopniu  <math>\displaystyle 2 </math> }
<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}
</quiz>
 
<quiz>Jeśli graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski, to:}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski}
<rightoption>każdy wierzchołek w grafie  <math>\displaystyle \mathbf{G} </math>  ma parzysty stopień}
<rightoption>graf  <math>\displaystyle \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}
<wrongoption>jeśli dodatkowo  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski,
to po usunięciu cyklu Hamiltona graf  <math>\displaystyle \mathbf{G} </math>  dalej jest eulerowski}
</quiz>
 
<quiz>Graf o  <math>\displaystyle 101 </math>  wierzchołkach:}
<wrongoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 50 </math> , jest hamiltonowski}
<rightoption>w którym wszystkie wierzchołki są stopnia  <math>\displaystyle 51 </math> , jest hamiltonowski}
<wrongoption>w którym dowolne dwa niesąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math> 
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski}
<wrongoption>w którym dowolne dwa sąsiednie wierzchołki  <math>\displaystyle v </math>  i  <math>\displaystyle w </math> 
spełniają  <math>\displaystyle \deg{v}+\deg{w}\geq 100 </math>  jest hamiltonowski}
</quiz>
 
<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>
istniało pełne skojarzenie  <math>\displaystyle V_1 </math>  z  <math>\displaystyle V_2 </math> ?}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  jest hamiltonowski}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  jest eulerowski}
<wrongoption>w grafie  <math>\displaystyle \mathbf{G} </math>  każdy wierzchołek z  <math>\displaystyle V_1 </math> 
ma co najmniej dwu sąsiadów}
<rightoption>dowolny zbiór niezależny w  ma co najwyżej  <math>\displaystyle \left\vert V_2 \right\vert </math>  wierzchołków}
</quiz>
 
<quiz>Grafem  <math>\displaystyle 100 </math> -spójnym jest:}
<rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje  <math>\displaystyle 100 </math> 
dróg wierzchołkowo rozłącznych}
<wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej  <math>\displaystyle 99 </math>  wierzchołków}
<rightoption>klika  <math>\displaystyle \mathcal{K}_{101} </math> }
<wrongoption>pełny graf dwudzielny  <math>\displaystyle \mathcal{K}_{100,100} </math> }
</quiz>
 
<quiz>W  <math>\displaystyle 2 </math> -spójnym krawędziowo grafie o  <math>\displaystyle 20 </math>  wierzchołkach
i minimalnej liczbie krawędzi:}
<wrongoption>jest dokładnie  <math>\displaystyle 38 </math>  krawędzi}
<rightoption>jest dokładnie  <math>\displaystyle 20 </math>  krawędzi}
<rightoption>dowolny wierzchołek ma stopień co najmniej  <math>\displaystyle 2 </math> }
<wrongoption>istnieje wierzchołek o stopniu co najmniej  <math>\displaystyle 3 </math> }
</quiz>
 
141414141414141414141414141414141414141414
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy III'''
|-
|
 
|}
 
10mm
 
<quiz>Który z grafów przedstawionych na Rysunku [[##test petersen4|Uzupelnic test petersen4|]] jest planarny?
 
[!ht]
{test_petersen4}
{ '''[Rysunek z pliku:''' <tt>testpetersen4.eps</tt>''']'''}
}
 
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].a.}
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].b.}
<wrongoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].c.}
<rightoption>graf przedstawiony na rysunku [[##test petersen4|Uzupelnic test petersen4|]].d.}
</quiz>
 
<quiz>Który z grafów przedstawionych na Rysunku [[##test klika5|Uzupelnic test klika5|]] jest homeomorficzny z kliką  <math>\displaystyle \mathcal{K}_{5} </math> ?
 
[!ht]
{test_klika5}
{ '''[Rysunek z pliku:''' <tt>testklika5.eps</tt>''']'''}
}
 
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].a.}
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].b.}
<rightoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].c.}
<wrongoption>graf przedstawiony na rysunku [[##test klika5|Uzupelnic test klika5|]].d.}
</quiz>
 
<quiz>Spójny graf planarny o  <math>\displaystyle 20 </math>  wierzchołkach, z których każdy jest stopnia  <math>\displaystyle 3 </math>  ma:}
<wrongoption> <math>\displaystyle 11 </math>  ścian}
<rightoption> <math>\displaystyle 12 </math>  ścian}
<wrongoption> <math>\displaystyle 22 </math>  ścian}
<wrongoption> <math>\displaystyle 24 </math>  ścian}
</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?}
<rightoption> <math>\displaystyle 98 </math> }
<wrongoption> <math>\displaystyle 99 </math> }
<wrongoption> <math>\displaystyle 100 </math> }
<wrongoption> <math>\displaystyle 143 </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle \mathbf{G}^* </math>  będzie grafem geometrycznie dualnym do
grafu płaskiego  <math>\displaystyle \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> 
wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru  <math>\displaystyle C </math> }
<wrongoption>posiada parzystą liczbę elementów}
<wrongoption>posiada nieparzystą liczbę elementów}
<wrongoption>jest cyklem grafu  <math>\displaystyle \mathbf{G}^* </math> }
<rightoption>jest rozcięciem grafu  <math>\displaystyle \mathbf{G}^* </math> }
</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:}
<wrongoption> <math>\displaystyle \left( k-1 \right) </math> -kolorowalny}
<rightoption> <math>\displaystyle k </math> -kolorowalny}
<rightoption> <math>\displaystyle \left( k+1 \right) </math> -kolorowalny}
<rightoption> <math>\displaystyle 2k </math> -kolorowalny}
</quiz>
 
<quiz>Iloma kolorami można pokolorować polityczną mapę Europy?}
<wrongoption> <math>\displaystyle 3 </math> }
<rightoption> <math>\displaystyle 4 </math> }
<rightoption> <math>\displaystyle 5 </math> }
<rightoption> <math>\displaystyle 6 </math> }
</quiz>
 
<quiz>W grafie prostym zachodzi:}
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\chi_s\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)=\chi_s\!\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>Pełny graf dwudzielny <math>\displaystyle K_{50,50}</math>:}
<rightoption> jest grafem Hamiltonowskim
<rightoption> jest grafem Eulerowskim
<wrongoption> jest lasem
<rightoption> jest dwukolorowalny
<rightoption> jest 49-kolorowalny
</quiz>
 
151515151515151515151515151515151515
 
{article}
{../makraT}
 
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Metody algebraiczne w teorii grafów'''
|-
|
 
|}
 
10mm
 
<quiz>Niech  <math>\displaystyle m_{ij} </math>  oznacza liczbę skierowanych marszrut,
nie dłuższych niż  <math>\displaystyle n-1 </math> , z wierzchołka  <math>\displaystyle v_i </math>  do  <math>\displaystyle v_j </math> 
w grafie skierowanym  <math>\displaystyle \mathbf{G}=\left( \left\lbrace v_1,\ldots,v_n \right\rbrace,E \right) </math> ,
a  <math>\displaystyle M </math>  niech będzie macierzą  <math>\displaystyle \langle m_{ij}\rangle  </math> .
Wtedy:}
<rightoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^1+{\sf A}\left( \mathbf{G} \right)^2+\ldots+{\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> }
<wrongoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> }
<wrongoption> <math>\displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle m_{ij}>0 </math>  wtedy i tylko wtedy, gdy  <math>\displaystyle \left( v_i,v_j \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right) </math> }
</quiz>
 
<quiz>Zaznacz prawdziwe zależności dla grafu prostego  <math>\displaystyle \mathbf{G} </math> 
o macierzy sąsiedztwa  <math>\displaystyle {\sf A}\left( \mathbf{G} \right) </math> ,
macierzy incydencji  <math>\displaystyle {\sf B}\left( \mathbf{G} \right) </math> ,
zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math> 
oraz  macierzy stopni  <math>\displaystyle {\sf D}\left( \mathbf{G} \right) </math> :}
<wrongoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf D}\left( \mathbf{G} \right)+ {\sf A}\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle {\sf C}\left( \mathbf{G} \right)\cdot {\sf C}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>Niech  <math>\displaystyle \mathbf{G} </math>  będzie grafem o  <math>\displaystyle 10 </math>  wierzchołkach
przedstawionym na Rysunku [[##test alg|Uzupelnic test alg|]],
a macierz  <math>\displaystyle M </math> , o rozmiarach  <math>\displaystyle 9\times9 </math> ,
będzie minorem (podmacierzą) zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math> ,
w którym kolumny odpowiadają krawędziom
<math>\displaystyle e_0, e_2, e_3, e_6, e_9, e_{12}, e_{13}, e_{14}, e_{15} </math> .
 
[!ht]
{test_alg}
{Graf  <math>\displaystyle \mathbf{G} </math> . '''[Rysunek z pliku:''' <tt>testalg.eps</tt>''']'''}
Wtedy:}
<rightoption>macierz  <math>\displaystyle M </math>  jest nieosobliwa}
<wrongoption>macierz  <math>\displaystyle M </math>  jest osobliwa}
<wrongoption>suma elementów w każdej kolumnie macierzy  <math>\displaystyle M </math>  wynosi  <math>\displaystyle 0 </math> }
<wrongoption>macierz  <math>\displaystyle M </math>  jest antysymetryczna}
</quiz>
 
<quiz>Na to by permanent grafu  <math>\displaystyle \mathbf{G} </math>  był niezerowy, wystarcza by:}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Hamiltona}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Eulera}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  był spójny}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  był grafem dwudzielnym posiadającym skojarzenie doskonałe}
</quiz>
 
<quiz>Zaznacz zdania prawdziwe o wartościach własnych grafów:}
<wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.}
<wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.}
<rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.}
<rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.}
</quiz>
 
<quiz>Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka
w grafie prostym:}
<wrongoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle \left\vert \lambda_{max}\!\left( \mathbf{G} \right) \right\vert\leq\Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> 
wtedy i tylko wtedy, gdy któraś spójna składowa grafu  <math>\displaystyle \mathbf{G} </math>
jest grafem regularnym stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> }
<rightoption> <math>\displaystyle -\Delta\left( \mathbf{G} \right) </math> 
jest wartością własną macierzy  <math>\displaystyle {\sf A}\left( \mathbf{G} \right) </math> 
wtedy i tylko wtedy, gdy  <math>\displaystyle \mathbf{G} </math>  jest regularnym grafem dwudzielnym
stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> }
</quiz>
 
<quiz>W grafie regularnym  <math>\displaystyle \mathbf{G} </math>  o  <math>\displaystyle 10 </math>  wierzchołkach stopnia  <math>\displaystyle 4 </math>
oraz wartościach własnych  <math>\displaystyle \lambda_{min}\!\left( \mathbf{G} \right)\approx-2,73205 </math>  i  <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=4 </math>
moc niezależnego podzbioru jest ograniczona z góry przez:}
<wrongoption> <math>\displaystyle 2 </math> }
<wrongoption> <math>\displaystyle 3 </math> }
<rightoption> <math>\displaystyle 4 </math> }<rightoption> <math>\displaystyle 10 </math> }
</quiz>
 
<quiz>Zaznacz zdania prawdziwe wiążące liczbę chromatyczną  <math>\displaystyle \chi\!\left( \mathbf{G} \right) </math>
z wartościami własnymi grafu regularnego  <math>\displaystyle \mathbf{G} </math> :}
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)} </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)= 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)} </math> }
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\lambda_{max}\!\left( \mathbf{G} \right)+1 </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\lambda_{max}\!\left( \mathbf{G} \right) </math> }
</quiz>

Aktualna wersja na dzień 20:09, 29 wrz 2006

5555555555555555555555555555555555555555 Logika



10101010101010101010101010101010101010101010101010 Logika

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR4&oldid=60021”