Test GR4: 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 1: Linia 1:
12121212121212121212121212121212
<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>
<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>\displaystyle n</math>-elementowym jest:}
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> .
<wrongoption> <math>\displaystyle 2^{n^2}</math>
Wtedy:
<rightoption>  <math>\displaystyle 2^{n^2-n}</math>
<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> </rightoption>
<wrongoption>  <math>\displaystyle 2^{2^n}</math>
<wrongoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> </wrongoption>
<wrongoption>  <math>\displaystyle 2^{2^n-n}</math>
<wrongoption> <math>\displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) </math> </wrongoption>
<wrongoption>    <math>\displaystyle 2^{n \choose 2}</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> </rightoption>
</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:}
<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>  


<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>   
<quiz>Zaznacz prawdziwe zależności dla grafu prostego  <math>\displaystyle \mathbf{G} </math>   
Linia 365: Linia 14:
macierzy incydencji  <math>\displaystyle {\sf B}\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>   
zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math>   
oraz  macierzy stopni  <math>\displaystyle {\sf D}\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> }
<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> </wrongoption>
<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> }
<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> </rightoption>
<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 B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) </math> </wrongoption>
<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> }
<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> </wrongoption>
</quiz>  
</quiz>  


<quiz>Niech  <math>\displaystyle \mathbf{G} </math>  będzie grafem o  <math>\displaystyle 10 </math>  wierzchołkach  
<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|]],  
przedstawionym na Rysunku 1,  
a macierz  <math>\displaystyle M </math> , o rozmiarach  <math>\displaystyle 9\times9 </math> ,  
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> ,  
będzie minorem (podmacierzą) zorientowanej macierzy incydencji  <math>\displaystyle {\sf C}\left( \mathbf{G} \right) </math> ,  
Linia 379: Linia 29:
  <math>\displaystyle e_0, e_2, e_3, e_6, e_9, e_{12}, e_{13}, e_{14}, e_{15} </math> .  
  <math>\displaystyle e_0, e_2, e_3, e_6, e_9, e_{12}, e_{13}, e_{14}, e_{15} </math> .  


  [!ht]
Graf <math>\displaystyle \mathbf{G} </math> . '''Rysunek z pliku: testalg.eps'''
   
   
{test_alg}
 
{Graf  <math>\displaystyle \mathbf{G} </math> . '''[Rysunek z pliku:''' <tt>testalg.eps</tt>''']'''}
Wtedy:
<rightoption>macierz  <math>\displaystyle M </math>  jest nieosobliwa</rightoption>
Wtedy:}
<wrongoption>macierz  <math>\displaystyle M </math>  jest osobliwa</wrongoption>
<rightoption>macierz  <math>\displaystyle M </math>  jest nieosobliwa}
<wrongoption>suma elementów w każdej kolumnie macierzy  <math>\displaystyle M </math>  wynosi  <math>\displaystyle 0 </math> </wrongoption>
<wrongoption>macierz  <math>\displaystyle M </math>  jest osobliwa}
<wrongoption>macierz  <math>\displaystyle M </math>  jest antysymetryczna</wrongoption>
<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>  


<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}
<quiz>Na to by permanent grafu  <math>\displaystyle \mathbf{G} </math>  był niezerowy, wystarcza by:
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Eulera}
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Hamiltona</rightoption>
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  był spójny}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  posiadał cykl Eulera</wrongoption>
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  był grafem dwudzielnym posiadającym skojarzenie doskonałe}
<wrongoption>graf  <math>\displaystyle \mathbf{G} </math>  był spójny</wrongoption>
<rightoption>graf  <math>\displaystyle \mathbf{G} </math>  był grafem dwudzielnym posiadającym skojarzenie doskonałe</rightoption>
</quiz>  
</quiz>  


<quiz>Zaznacz zdania prawdziwe o wartościach własnych grafów:}
 
<wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.}
<quiz>Zaznacz zdania prawdziwe o wartościach własnych grafów:
<wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.}
<wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.</wrongoption>
<rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.}
<wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.</wrongoption>
<rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.}
<rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.</rightoption>
<rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.</rightoption>
</quiz>  
</quiz>  


<quiz>Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka  
<quiz>Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka  
w grafie prostym:}
w grafie prostym:
<wrongoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) </math> </wrongoption>
<rightoption> <math>\displaystyle \left\vert \lambda_{max}\!\left( \mathbf{G} \right) \right\vert\leq\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>
<rightoption> <math>\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\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>  
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> }
jest grafem regularnym stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> </rightoption>
<rightoption> <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>   
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  
wtedy i tylko wtedy, gdy  <math>\displaystyle \mathbf{G} </math>  jest regularnym grafem dwudzielnym  
stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> }
stopnia  <math>\displaystyle \Delta\left( \mathbf{G} \right) </math> </rightoption>
</quiz>  
</quiz>  


<quiz>W grafie regularnym  <math>\displaystyle \mathbf{G} </math>  o  <math>\displaystyle 10 </math>  wierzchołkach stopnia  <math>\displaystyle 4 </math>  
<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>  
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:}
moc niezależnego podzbioru jest ograniczona z góry przez:
<wrongoption> <math>\displaystyle 2 </math> }
<wrongoption> <math>\displaystyle 2 </math> </wrongoption>
<wrongoption> <math>\displaystyle 3 </math> }
<wrongoption> <math>\displaystyle 3 </math> </wrongoption>
<rightoption> <math>\displaystyle 4 </math> }<rightoption> <math>\displaystyle 10 </math> }
<rightoption> <math>\displaystyle 4 </math> </rightoption>
<rightoption> <math>\displaystyle 10 </math> </rightoption>
</quiz>  
</quiz>  


<quiz>Zaznacz zdania prawdziwe wiążące liczbę chromatyczną  <math>\displaystyle \chi\!\left( \mathbf{G} \right) </math>  
<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> :}
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> }
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)} </math> </rightoption>
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)= 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> </wrongoption>
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\lambda_{max}\!\left( \mathbf{G} \right)+1 </math> }
<rightoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\leq\lambda_{max}\!\left( \mathbf{G} \right)+1 </math> </rightoption>
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\lambda_{max}\!\left( \mathbf{G} \right) </math> }
<wrongoption> <math>\displaystyle \chi\!\left( \mathbf{G} \right)\geq\lambda_{max}\!\left( \mathbf{G} \right) </math> </wrongoption>
</quiz>
</quiz>

Wersja z 21:42, 18 wrz 2006

Niech mij oznacza liczbę skierowanych marszrut, nie dłuższych niż n−1 , z wierzchołka vi do vj w grafie skierowanym 𝐆=({v1,…,vn},E) , a M niech będzie macierzą ⟨mij⟩ . Wtedy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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)} }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) }

mij>0 wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( v_i,v_j \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right) }


Zaznacz prawdziwe zależności dla grafu prostego 𝐆 o macierzy sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } , macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) } , zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } oraz macierzy stopni Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf D}\left( \mathbf{G} \right) }  :

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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) }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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) }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) }

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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) }


Niech 𝐆 będzie grafem o 10 wierzchołkach przedstawionym na Rysunku 1, a macierz M , o rozmiarach 9×9 , będzie minorem (podmacierzą) zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } , w którym kolumny odpowiadają krawędziom 

e0,e2,e3,e6,e9,e12,e13,e14,e15 .

Graf 𝐆 . Rysunek z pliku: testalg.eps


Wtedy:

macierz M jest nieosobliwa

macierz M jest osobliwa

suma elementów w każdej kolumnie macierzy M wynosi 0

macierz M jest antysymetryczna


Na to by permanent grafu 𝐆 był niezerowy, wystarcza by:

graf 𝐆 posiadał cykl Hamiltona

graf 𝐆 posiadał cykl Eulera

graf 𝐆 był spójny

graf 𝐆 był grafem dwudzielnym posiadającym skojarzenie doskonałe


Zaznacz zdania prawdziwe o wartościach własnych grafów:

Co najmniej jedna z wartości własnych jest liczbą zespoloną.

Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.

Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.

Wszystkie wartości własne dowolnego grafu są rzeczywiste.


Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka w grafie prostym:

λmax(𝐆)=Δ(𝐆)

|λmax(𝐆)|≤Δ(𝐆)

λmax(𝐆)=Δ(𝐆) wtedy i tylko wtedy, gdy któraś spójna składowa grafu 𝐆 jest grafem regularnym stopnia Δ(𝐆)

−Δ(𝐆) jest wartością własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } wtedy i tylko wtedy, gdy 𝐆 jest regularnym grafem dwudzielnym stopnia Δ(𝐆)


W grafie regularnym 𝐆 o 10 wierzchołkach stopnia 4 oraz wartościach własnych λmin(𝐆)≈−2,73205 i λmax(𝐆)=4 moc niezależnego podzbioru jest ograniczona z góry przez:

2

3

4

10


Zaznacz zdania prawdziwe wiążące liczbę chromatyczną χ(𝐆) z wartościami własnymi grafu regularnego 𝐆 :

χ(𝐆)≥1−λmax(𝐆)λmin(𝐆)

χ(𝐆)=1−λmax(𝐆)λmin(𝐆)

χ(𝐆)≤λmax(𝐆)+1

χ(𝐆)≥λmax(𝐆)

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