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{𝐆}$ posiadającym skojarzenie doskonałe:

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

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

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

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

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

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

moc najliczniejszego zbioru niezależnego wynosi $\alpha \left(\mathbf{𝐆}\right)\le 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{𝐆}$ , 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{𝐆}$ , w którym maksymalne skojarzenie ma $\nu \left(\mathbf{𝐆}\right)=73$ krawędzi:

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

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

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

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

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

$\nu \left(\mathbf{𝐆}\right)\le \tau \left(\mathbf{𝐆}\right)$ Dobrze

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

$\nu \left(\mathbf{𝐆}\right)+\tau \left(\mathbf{𝐆}\right)=\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|$ Źle

$\tau \left(\mathbf{𝐆}\right)\le 2\nu \left(\mathbf{𝐆}\right)$ Dobrze