Test GR4

Niech $m_{ij}$ oznacza liczbę skierowanych marszrut, nie dłuższych niż $n-1$ , z wierzchołka $v_i$ do $v_j$ w grafie skierowanym $\mathbf{𝐆}=(\{v_1,\dots ,v_n\},E)$ , a $M$ niech będzie macierzą $⟨m_{ij}⟩$ . 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)} } Dobrze

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

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

$m_{ij}>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) } Dobrze

Zaznacz prawdziwe zależności dla grafu prostego $\mathbf{𝐆}$ 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) } Źle

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) } Dobrze

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) } Źle

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) } Źle

Niech $\mathbf{𝐆}$ będzie grafem o $10$ wierzchołkach przedstawionym na Rysunku 1, a macierz $M$ , o rozmiarach $9\times 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 $e_0,e_2,e_3,e_6,e_9,e_{12},e_{13},e_{14},e_{15}$ .

Graf $\mathbf{𝐆}$ . Rysunek z pliku: testalg.eps

Wtedy:

macierz $M$ jest nieosobliwa Dobrze

macierz $M$ jest osobliwa Źle

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

macierz $M$ jest antysymetryczna Źle

Na to by permanent grafu $\mathbf{𝐆}$ był niezerowy, wystarcza by:

graf $\mathbf{𝐆}$ posiadał cykl Hamiltona Dobrze

graf $\mathbf{𝐆}$ posiadał cykl Eulera Źle

graf $\mathbf{𝐆}$ był spójny Źle

graf $\mathbf{𝐆}$ był grafem dwudzielnym posiadającym skojarzenie doskonałe Dobrze

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

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

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

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

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

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

${\lambda }_{max}\left(\mathbf{𝐆}\right)=\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ Źle

$\left|{\lambda }_{max}\left(\mathbf{𝐆}\right)\right|\le \mathrm{\Delta }\left(\mathbf{𝐆}\right)$ Dobrze

${\lambda }_{max}\left(\mathbf{𝐆}\right)=\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ wtedy i tylko wtedy, gdy któraś spójna składowa grafu $\mathbf{𝐆}$ jest grafem regularnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ Dobrze

$-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ 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 $\mathbf{𝐆}$ jest regularnym grafem dwudzielnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ Dobrze

W grafie regularnym $\mathbf{𝐆}$ o $10$ wierzchołkach stopnia $4$ oraz wartościach własnych ${\lambda }_{min}\left(\mathbf{𝐆}\right)\approx -2,73205$ i ${\lambda }_{max}\left(\mathbf{𝐆}\right)=4$ moc niezależnego podzbioru jest ograniczona z góry przez:

$2$ Źle

$3$ Źle

$4$ Dobrze

$10$ Dobrze

Zaznacz zdania prawdziwe wiążące liczbę chromatyczną $\chi \left(\mathbf{𝐆}\right)$ z wartościami własnymi grafu regularnego $\mathbf{𝐆}$ :

$\chi \left(\mathbf{𝐆}\right)\ge 1-\frac{{\lambda }_{max}\left(\mathbf{𝐆}\right)}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}$ Dobrze

$\chi \left(\mathbf{𝐆}\right)=1-\frac{{\lambda }_{max}\left(\mathbf{𝐆}\right)}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}$ Źle

$\chi \left(\mathbf{𝐆}\right)\le {\lambda }_{max}\left(\mathbf{𝐆}\right)+1$ Dobrze

$\chi \left(\mathbf{𝐆}\right)\ge {\lambda }_{max}\left(\mathbf{𝐆}\right)$ Źle