Matematyka dyskretna 2/Test 1: Zagadnienia Mini-Maksowe w grafach

From Studia Informatyczne



Rysunek 1


Rysunek 2


Które z następujących zdań poprawnie opisują Rysunek 1:

Na Rysunku 1.a oraz 1.b zostały przedstawione minimalne pokrycia krawędziowe.

Na Rysunku 1.a oraz 1.b zostały przedstawione maksymalne skojarzenia.

Na Rysunku 1.a zostało przedstawione minimalne pokrycie krawędziowe, a na Rysunku 1.b maksymalne skojarzenie.

Na Rysunku 1.a zostało przedstawione maksymalne skojarzenie, a na Rysunku 1.b skojarzenie doskonałe.


Które z następujących zdań poprawnie opisują Rysunek 2:

Na Rysunku 2.a oraz 2.b zostały przedstawione minimalne pokrycia wierzchołkowe.

Na Rysunku 2.a oraz 2.b zostały przedstawione zbiory niezależne.

Na Rysunku 2.a zostało przedstawione minimalne pokrycie wierzchołkowe, a na Rysunku 2.b maksymalny zbiór niezależny.

Na Rysunku 2.a zostało przedstawione pokrycie wierzchołkowe, a na Rysunku 2.b zbiór niezależny.


W \displaystyle 100 -wierzchołkowym grafie spójnym \displaystyle \mathbf{G} posiadającym skojarzenie doskonałe:

moc maksymalnego skojarzenia wynosi \displaystyle \nu\left( \mathbf{G} \right)=50

moc najliczniejszego zbioru niezależnego wynosi \displaystyle \alpha\left( \mathbf{G} \right)=50

moc minimalnego pokrycia krawędziowego wynosi \displaystyle \rho\left( \mathbf{G} \right)=50

moc minimalnego pokrycia krawędziowego wynosi \displaystyle \rho\left( \mathbf{G} \right)=49


W \displaystyle 1073 -wierzchołkowym grafie spójnym \displaystyle \mathbf{G} o liczbie chromatycznej \displaystyle \chi\!\left( \mathbf{G} \right)=23 :

moc najliczniejszego zbioru niezależnego wynosi \displaystyle \alpha\left( \mathbf{G} \right)\leq1051

moc najliczniejszego zbioru niezależnego wynosi \displaystyle \alpha\left( \mathbf{G} \right)\leq1050

istnieje pokrycie \displaystyle 23 wierzchołkami

każde pokrycie wierzchołkowe ma co najmniej \displaystyle 24 elementy


Jeśli \displaystyle M jest maksymalnym skojarzeniem w grafie \displaystyle \mathbf{G} , to:

\displaystyle M zawiera się w jakimś minimalnym pokryciu krawędziowym

istnieje maksymalny zbiór niezależny \displaystyle A , dla którego każda krawędź z \displaystyle M jest incydentna z którymś wierzchołkiem w \displaystyle A

wierzchołki nieincydentne z żądną krawędzią z \displaystyle M tworzą zbiór niezależny

\displaystyle M jest minimalnym pokryciem krawędziowym


W \displaystyle 153 -wierzchołkowym grafie dwudzielnym \displaystyle \mathbf{G} , w którym maksymalne skojarzenie ma \displaystyle \nu\left( \mathbf{G} \right)=73 krawędzi:

minimalne pokrycie wierzchołkowe ma moc \displaystyle \tau\left( \mathbf{G} \right)=80

minimalne pokrycie wierzchołkowe ma moc \displaystyle \tau\left( \mathbf{G} \right)=73

minimalne pokrycie krawędziowe ma moc \displaystyle \rho\left( \mathbf{G} \right)=80

minimalne pokrycie krawędziowe ma moc \displaystyle \rho\left( \mathbf{G} \right)=73


W każdym grafie prostym \displaystyle \mathbf{G} zachodzi:

\displaystyle \nu\left( \mathbf{G} \right)\leq \tau\left( \mathbf{G} \right)

\displaystyle \tau\left( \mathbf{G} \right)\leq\nu\left( \mathbf{G} \right)

\displaystyle \nu\left( \mathbf{G} \right)+ \tau\left( \mathbf{G} \right)=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert

\displaystyle \tau\left( \mathbf{G} \right)\leq 2\nu\left( \mathbf{G} \right)