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

From Studia Informatyczne

Niech \displaystyle m_{ij} oznacza liczbę skierowanych marszrut, nie dłuższych niż \displaystyle n-1 , z wierzchołka \displaystyle v_i do \displaystyle v_j w grafie skierowanym \displaystyle \mathbf{G}=\left( \left\lbrace v_1,\ldots,v_n \right\rbrace,E \right) , a \displaystyle M niech będzie macierzą \displaystyle \langle m_{ij}\rangle . Wtedy:

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

\displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)}

\displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right)

\displaystyle m_{ij}>0 wtedy i tylko wtedy, gdy \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 \displaystyle \mathbf{G} o macierzy sąsiedztwa \displaystyle {\sf A}\left( \mathbf{G} \right) , macierzy incydencji \displaystyle {\sf B}\left( \mathbf{G} \right) , zorientowanej macierzy incydencji \displaystyle {\sf C}\left( \mathbf{G} \right) oraz macierzy stopni \displaystyle {\sf D}\left( \mathbf{G} \right) :

\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)

\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)

\displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right)

\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)



Rysunek 1: Graf \displaystyle \mathbf{G}

Niech \displaystyle \mathbf{G} będzie grafem o \displaystyle 10 wierzchołkach przedstawionym na Rysunku 1, a macierz \displaystyle M , o rozmiarach \displaystyle 9\times9 , będzie minorem (podmacierzą) zorientowanej macierzy incydencji \displaystyle {\sf C}\left( \mathbf{G} \right) , w którym kolumny odpowiadają krawędziom \displaystyle e_0, e_2, e_3, e_6, e_9, e_{12}, e_{13}, e_{14}, e_{15} .

Wtedy:

macierz \displaystyle M jest nieosobliwa

macierz \displaystyle M jest osobliwa

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

macierz \displaystyle M jest antysymetryczna


Na to by permanent grafu \displaystyle \mathbf{G} był niezerowy, wystarcza by:

graf \displaystyle \mathbf{G} posiadał cykl Hamiltona

graf \displaystyle \mathbf{G} posiadał cykl Eulera

graf \displaystyle \mathbf{G} był spójny

graf \displaystyle \mathbf{G} 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:

\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right)

\displaystyle \left\vert \lambda_{max}\!\left( \mathbf{G} \right) \right\vert\leq\Delta\left( \mathbf{G} \right)

\displaystyle \lambda_{max}\!\left( \mathbf{G} \right)=\Delta\left( \mathbf{G} \right) wtedy i tylko wtedy, gdy któraś spójna składowa grafu \displaystyle \mathbf{G} jest grafem regularnym stopnia \displaystyle \Delta\left( \mathbf{G} \right)

\displaystyle -\Delta\left( \mathbf{G} \right) jest wartością własną macierzy \displaystyle {\sf A}\left( \mathbf{G} \right) wtedy i tylko wtedy, gdy \displaystyle \mathbf{G} jest regularnym grafem dwudzielnym stopnia \displaystyle \Delta\left( \mathbf{G} \right)


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

\displaystyle 2

\displaystyle 3

\displaystyle 4

\displaystyle 10


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

\displaystyle \chi\!\left( \mathbf{G} \right)\geq 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)}

\displaystyle \chi\!\left( \mathbf{G} \right)= 1-\frac{\lambda_{max}\!\left( \mathbf{G} \right)}{\lambda_{min}\!\left( \mathbf{G} \right)}

\displaystyle \chi\!\left( \mathbf{G} \right)\leq\lambda_{max}\!\left( \mathbf{G} \right)+1

\displaystyle \chi\!\left( \mathbf{G} \right)\geq\lambda_{max}\!\left( \mathbf{G} \right)