Matematyka dyskretna 1/Test 12: Grafy

Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze $n$-elementowym jest:

$2^{n^2}$ Źle

$2^{n^2-n}$ Dobrze

$2^{2^n}$ Źle

$2^{2^n-n}$ Źle

$2^{(\genfrac{}{}{0ex}{}{n}{2})}$ Źle

Różnych grafów nieskierowanych bez cykli jednoelementowych w zbiorze $n$-elementowym jest:

$2^{n^2}$ Źle

$2^{n^2-n}$ Źle

$2^{2^n}$ Źle

$2^{2^n-n}$ Źle

$2^{(\genfrac{}{}{0ex}{}{n}{2})}$ Dobrze

Zaznacz zdania prawdziwe:

W każdym grafie prostym $G=(V;E)$ relacja $E$ musi być zwrotna. Źle

W grafie nieskierowanym $G=(V,E)$ relacja $E$ jest symetryczna. Dobrze

Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków. Źle

W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią. Dobrze

Zaznacz zdania prawdziwe dla grafów nieskierowanych:

podgraf indukowany grafu pełnego jest grafem pełnym Dobrze

każdy graf jest podgrafem jakiegoś grafu pełnego Dobrze

każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego Źle

graf pełny ma zawsze parzystą liczbę krawędzi Źle

w grafie pełnym wszystkie wierzchołki mają ten sam stopień Dobrze

Jaka jest najmniejsza liczba krawędzi w grafie nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:

$99$ Źle

$97$ Dobrze

$98$ Źle

$100$ Źle

$\frac{100\cdot 99}{3}$ Źle

Ile jest krawędzi w pełnym grafie dwudzielnym $K_{1000,1000}$:

$1000\cdot 1000$ Dobrze

$1000!$ Źle

$(\genfrac{}{}{0ex}{}{1000}{2})$ Źle

$(\genfrac{}{}{0ex}{}{1000}{50})$ Źle

$(\genfrac{}{}{0ex}{}{2000}{1000})$ Źle

W pełnym grafie $100$-elementowym:

każde drzewo rozpinające ma $100$ krawędzi Źle

dokładnie jedno drzewo rozpinające ma $100$ krawędzi Źle

każde drzewo rozpinające ma $99$ krawędzi Dobrze

dokładnie jedno drzewo rozpinające ma $99$ krawędzi Źle

nie ma drzew rozpinających Źle

W pełnym grafie dwudzielnym $K_{50,50}$:

każde drzewo rozpinające ma $50$ krawędzi Źle

każde drzewo rozpinające ma $100$ krawędzi Źle

każde drzewo rozpinające ma $99$ krawędzi Dobrze

dokładnie jedno drzewo rozpinające ma $99$ krawędzi Źle

nie ma drzew rozpinających Źle

W $100$ elementowym grafie o trzech składowych spójnych:

jakiś las rozpinający ma $100$ krawędzi Źle

jakiś las rozpinający ma $99$ krawędzi Źle

jakiś las rozpinający ma $98$ krawędzi Źle

jakiś las rozpinający ma $97$ krawędzi Dobrze

może nie być lasu rozpinającego Źle

Pełny graf $100$-elementowy:

jest grafem Hamiltonowskim Dobrze

jest grafem Eulerowskim Źle

jest spójny Źle

jest dwudzielny Dobrze

jest stukolorowalny Dobrze

Pełny graf dwudzielny $K_{25,25}$:

jest grafem Hamiltonowskim Dobrze

jest grafem Eulerowskim Źle

zawiera cykl $4$ wierzchołkach jako podgraf indukowany Dobrze

zawiera cykl $6$ wierzchołkach jako podgraf indukowany Źle

jest trójkolorowalny Dobrze

Graf o $2005$ wierzchołkach, z których każdy ma stopień $101$ :

ma $202505$ krawędzi Źle

ma $2106$ krawędzi Źle

ma $405010$ krawędzi Źle

nie istnieje Dobrze

Jeśli ${\mathbf{𝐆}}_1=(V,E_1)$ i ${\mathbf{𝐆}}_2=(V,E_2)$ są grafami niespójnymi o tym samym zbiorze wierzchołków $V$ , to:

graf ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_1$ może być spójny Dobrze

graf ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_1$ jest spójny Źle

graf ${\mathbf{𝐆}}_1\cap {\mathbf{𝐆}}_1$ może nie być spójny Dobrze

graf ${\mathbf{𝐆}}_1\cap {\mathbf{𝐆}}_1$ nie jest spójny Dobrze

Graf ${\mathbf{𝐏}}_4$ to graf, który składa się jedynie ze ścieżki odwiedzającej $4$ wierzchołki, czyli $\mathsf{V}\left({\mathbf{𝐏}}_4\right)=\{a,b,c,d\}$ oraz $\mathsf{E}\left({\mathbf{𝐏}}_4\right)=\{\{a,b\},\{b,c\},\{c,d\}\}$ . W grafie spójnym, w którym nie ma podgrafu indukowanego izomorficznego do ${\mathbf{𝐏}}_4$ :

dowolne dwa punkty leżą w odległości co najwyżej trzy Dobrze

dowolne dwa punkty leżą w odległości co najwyżej dwa Dobrze

dowolne dwa punkty leżą w odległości co najwyżej jeden Źle

każde trzy wierzchołki tworzą klikę ${{𝒦}}_3$ Źle

Zaznacz zdania prawdziwe:

Każdy graf pusty jest grafem dwudzielnym. Dobrze

Każdy graf pełny jest grafem dwudzielnym. Źle

Graf ${{𝒦}}_3$ jest grafem dwudzielnym. Źle

Graf ${{𝒦}}_2$ jest grafem dwudzielnym. Dobrze

Zaznacz zdania prawdziwe:

Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny. Dobrze

Graf ${{𝒦}}_4$ jest grafem planarnym. Dobrze

Graf ${{𝒦}}_5$ jest grafem planarnym. Źle

Każdy graf dwudzielny jest grafem planarnym. Źle

Graf o $100$ wierzchołkach:

jeśli ma $99$ krawędzi, to jest drzewem. Źle

jeśli ma $100$ krawędzi, to jest drzewem. Źle

jeśli ma $4851$ krawędzi, to jest spójny. Źle

jeśli ma $4852$ krawędzi, to jest spójny. Dobrze

Na to by graf $\mathbf{𝐓}$ był drzewem potrzeba i wystarcza, by:

$\mathbf{𝐓}$ nie zawierał cykli Źle

$\mathbf{𝐓}$ był spójny i miał $\left|V\right|-1$ krawędzi Dobrze

dowolne dwa wierzchołki grafu $\mathbf{𝐓}$ były połączone dokładnie jedną drogą Dobrze

dowolne dwa wierzchołki grafu $\mathbf{𝐓}$ leżały na dokładnie jednym cyklu Źle