|
|
| (Nie pokazano 50 pośrednich wersji utworzonych przez tego samego użytkownika) |
| Linia 1: |
Linia 1: |
| <quiz>Niech <math>\displaystyle m_{ij} </math> oznacza liczbę skierowanych marszrut,
| | 5555555555555555555555555555555555555555 Logika |
| 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> </rightoption>
| |
| <wrongoption> <math>\displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} </math> </wrongoption>
| |
| <wrongoption> <math>\displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) </math> </wrongoption>
| |
| <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>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> </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>
| |
| <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>
| |
| </quiz>
| |
|
| |
|
|
| |
|
| <quiz>Niech <math>\displaystyle \mathbf{G} </math> będzie grafem o <math>\displaystyle 10 </math> wierzchołkach
| | 10101010101010101010101010101010101010101010101010 Logika |
| przedstawionym na Rysunku 1,
| |
| 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> .
| |
| | |
| Graf <math>\displaystyle \mathbf{G} </math> . '''Rysunek z pliku: testalg.eps'''
| |
|
| |
| | |
| Wtedy:
| |
| <rightoption>macierz <math>\displaystyle M </math> jest nieosobliwa</rightoption>
| |
| <wrongoption>macierz <math>\displaystyle M </math> jest osobliwa</wrongoption>
| |
| <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 antysymetryczna</wrongoption>
| |
| </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</rightoption>
| |
| <wrongoption>graf <math>\displaystyle \mathbf{G} </math> posiadał cykl Eulera</wrongoption>
| |
| <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>Zaznacz zdania prawdziwe o wartościach własnych grafów:
| |
| <wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.</wrongoption>
| |
| <wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.</wrongoption>
| |
| <rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.</rightoption>
| |
| <rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.</rightoption>
| |
| </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> </wrongoption>
| |
| <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>
| |
| 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>
| |
| <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> </rightoption>
| |
| </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>
| |
| <wrongoption> <math>\displaystyle 3 </math> </wrongoption>
| |
| <rightoption> <math>\displaystyle 4 </math> </rightoption>
| |
| <rightoption> <math>\displaystyle 10 </math> </rightoption>
| |
| </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> </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>
| |
| <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>
| |
| </quiz>
| |
5555555555555555555555555555555555555555 Logika
10101010101010101010101010101010101010101010101010 Logika
