Matematyka dyskretna 1/Test 15: Metody algebraiczne w teorii grafów

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:

$M=\mathsf{A}{\left(\mathbf{𝐆}\right)}^1+\mathsf{A}{\left(\mathbf{𝐆}\right)}^2+\dots +\mathsf{A}{\left(\mathbf{𝐆}\right)}^{(n-1)}$ Dobrze

$M=\mathsf{A}{\left(\mathbf{𝐆}\right)}^{(n-1)}$ Źle

$M=n\cdot \mathsf{A}\left(\mathbf{𝐆}\right)$ Źle

$m_{ij}>0$ wtedy i tylko wtedy, gdy $(v_i,v_j)\in \mathsf{E}\left(\mathsf{T}\mathsf{C}\left(\mathbf{𝐆}\right)\right)$ Dobrze

Zaznacz prawdziwe zależności dla grafu prostego $\mathbf{𝐆}$ o macierzy sąsiedztwa $\mathsf{A}\left(\mathbf{𝐆}\right)$ , macierzy incydencji $\mathsf{B}\left(\mathbf{𝐆}\right)$ , zorientowanej macierzy incydencji $\mathsf{C}\left(\mathbf{𝐆}\right)$ oraz macierzy stopni $\mathsf{D}\left(\mathbf{𝐆}\right)$ :

$\mathsf{B}\left(\mathbf{𝐆}\right)\cdot \mathsf{B}{\left(\mathbf{𝐆}\right)}^T=\mathsf{A}\left(\mathbf{𝐆}\right)-\mathsf{D}\left(\mathbf{𝐆}\right)$ Źle

$\mathsf{B}\left(\mathbf{𝐆}\right)\cdot \mathsf{B}{\left(\mathbf{𝐆}\right)}^T=\mathsf{D}\left(\mathbf{𝐆}\right)+\mathsf{A}\left(\mathbf{𝐆}\right)$ Dobrze

$\mathsf{B}\left(\mathbf{𝐆}\right)\cdot \mathsf{A}\left(\mathbf{𝐆}\right)=\mathsf{C}\left(\mathbf{𝐆}\right)$ Źle

$\mathsf{C}\left(\mathbf{𝐆}\right)\cdot \mathsf{C}{\left(\mathbf{𝐆}\right)}^T=\mathsf{A}\left(\mathbf{𝐆}\right)-\mathsf{D}\left(\mathbf{𝐆}\right)$ Źle

Rysunek 1: Graf $\mathbf{𝐆}$

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 $\mathsf{C}\left(\mathbf{𝐆}\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}$ .

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 $\mathsf{A}\left(\mathbf{𝐆}\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