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

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. Źle

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

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

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

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. Dobrze

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

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

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

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

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

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

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

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

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

moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf {G} \right)\leq 1051$ Dobrze

moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf {G} \right)\leq 1050$ Źle

istnieje pokrycie $23$ wierzchołkami Źle

każde pokrycie wierzchołkowe ma co najmniej $24$ elementy Dobrze

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

$M$ zawiera się w jakimś minimalnym pokryciu krawędziowym Dobrze

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

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

$M$ jest minimalnym pokryciem krawędziowym Źle

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

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

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

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

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

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

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

$\tau \left(\mathbf {G} \right)\leq \nu \left(\mathbf {G} \right)$ Źle

$\nu \left(\mathbf {G} \right)+\tau \left(\mathbf {G} \right)=\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert$ Źle

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