Matematyka dyskretna 1/Test 12: Grafy: Różnice pomiędzy wersjami

← poprzednia edycja

WizualnieWikikod

Aktualna wersja na dzień 10:04, 5 wrz 2023

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^{(\binom{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^{(\binom{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

$(\binom{1000}{2})$ Źle

$(\binom{1000}{50})$ Źle

$(\binom{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 $𝐆_{1} = (V, E_{1})$ i $𝐆_{2} = (V, E_{2})$ są grafami niespójnymi o tym samym zbiorze wierzchołków $V$ , to:

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

graf $𝐆_{1} \cup 𝐆_{1}$ jest spójny Źle

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

graf $𝐆_{1} \cap 𝐆_{1}$ nie jest spójny Dobrze

Graf $𝐏_{4}$ to graf, który składa się jedynie ze ścieżki odwiedzającej $4$ wierzchołki, czyli $V (𝐏_{4}) = {a, b, c, d}$ oraz $E (𝐏_{4}) = {{a, b}, {b, c}, {c, d}}$ . W grafie spójnym, w którym nie ma podgrafu indukowanego izomorficznego do $𝐏_{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 $𝐓$ był drzewem potrzeba i wystarcza, by:

$𝐓$ nie zawierał cykli Źle

$𝐓$ był spójny i miał $| V | - 1$ krawędzi Dobrze

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

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

@@ Linia 97: / Linia 97: @@
-<quiz>Graf o  <math>2005 </math>  wierzchołkach, z których każdy ma stopień  <math>101 </math> :
+<quiz>Graf o  <math>2005</math>  wierzchołkach, z których każdy ma stopień  <math>101</math> :
-<wrongoption>ma  <math>202505 </math>  krawędzi</wrongoption>
+<wrongoption>ma  <math>202505</math>  krawędzi</wrongoption>
-<wrongoption>ma  <math>2106 </math>  krawędzi</wrongoption>
+<wrongoption>ma  <math>2106</math>  krawędzi</wrongoption>
-<wrongoption>ma  <math>405010 </math>   krawędzi</wrongoption>
+<wrongoption>ma  <math>405010</math>   krawędzi</wrongoption>
 <rightoption>nie istnieje</rightoption>
 </quiz>
-<quiz>Jeśli  <math>\mathbf{G}_1=\left( V,E_1 \right) </math>  i  <math>\mathbf{G}_2=\left( V,E_2 \right) </math>
+<quiz>Jeśli  <math>\mathbf{G}_1=\left( V,E_1 \right)</math>  i  <math>\mathbf{G}_2=\left( V,E_2 \right)</math>
-są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>V </math> , to:
+są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>V</math> , to:
-<rightoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1 </math>  może być spójny</rightoption>
+<rightoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  może być spójny</rightoption>
-<wrongoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1 </math>  jest spójny</wrongoption>
+<wrongoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  jest spójny</wrongoption>
-<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1 </math>  może nie być spójny</rightoption>
+<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  może nie być spójny</rightoption>
-<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1 </math>  nie jest spójny</rightoption>
+<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  nie jest spójny</rightoption>
 </quiz>
-<quiz>Graf  <math>\mathbf{P}_4 </math>  to graf, który składa się jedynie ze ścieżki
+<quiz>Graf  <math>\mathbf{P}_4</math>  to graf, który składa się jedynie ze ścieżki
-odwiedzającej  <math>4 </math>  wierzchołki,
+odwiedzającej  <math>4</math>  wierzchołki,
-czyli  <math>\mathsf{ V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace </math>
+czyli  <math>\mathsf{ V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace</math>
-oraz  <math>\mathsf{ E}\!\left(\mathbf{P}_4\right)=\left\lbrace \left\lbrace a,b \right\rbrace,\left\lbrace b,c \right\rbrace,\left\lbrace c,d \right\rbrace \right\rbrace </math> .
+oraz  <math>\mathsf{ E}\!\left(\mathbf{P}_4\right)=\left\lbrace \left\lbrace a,b \right\rbrace,\left\lbrace b,c \right\rbrace,\left\lbrace c,d \right\rbrace \right\rbrace</math> .
 W grafie spójnym, w którym nie ma
-podgrafu indukowanego izomorficznego do  <math>\mathbf{P}_4 </math> :
+podgrafu indukowanego izomorficznego do  <math>\mathbf{P}_4</math> :
 <rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy</rightoption>
 <rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa</rightoption>
 <wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden</wrongoption>
-<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\mathcal{K}_{3} </math></wrongoption>
+<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\mathcal{K}_{3}</math></wrongoption>
 </quiz>
@@ Linia 130: / Linia 130: @@
 <rightoption>Każdy graf pusty jest grafem dwudzielnym.</rightoption>
 <wrongoption>Każdy graf pełny jest grafem dwudzielnym.</wrongoption>
-<wrongoption>Graf  <math>\mathcal{K}_{3} </math>  jest grafem dwudzielnym.</wrongoption>
+<wrongoption>Graf  <math>\mathcal{K}_{3}</math>  jest grafem dwudzielnym.</wrongoption>
-<rightoption>Graf  <math>\mathcal{K}_{2} </math>  jest grafem dwudzielnym.</rightoption>
+<rightoption>Graf  <math>\mathcal{K}_{2}</math>  jest grafem dwudzielnym.</rightoption>
 </quiz>
@@ Linia 137: / Linia 137: @@
 <quiz>Zaznacz zdania prawdziwe:
 <rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.</rightoption>
-<rightoption>Graf  <math>\mathcal{K}_{4} </math>  jest grafem planarnym.</rightoption>
+<rightoption>Graf  <math>\mathcal{K}_{4}</math>  jest grafem planarnym.</rightoption>
-<wrongoption>Graf  <math>\mathcal{K}_{5} </math>  jest grafem planarnym.</wrongoption>
+<wrongoption>Graf  <math>\mathcal{K}_{5}</math>  jest grafem planarnym.</wrongoption>
 <wrongoption>Każdy graf dwudzielny jest grafem planarnym.</wrongoption>
 </quiz>
-<quiz>Graf o  <math>100 </math>  wierzchołkach:
+<quiz>Graf o  <math>100</math>  wierzchołkach:
-<wrongoption>jeśli ma  <math>99 </math>  krawędzi, to jest drzewem.</wrongoption>
+<wrongoption>jeśli ma  <math>99</math>  krawędzi, to jest drzewem.</wrongoption>
-<wrongoption>jeśli ma  <math>100 </math>  krawędzi, to jest drzewem.</wrongoption>
+<wrongoption>jeśli ma  <math>100</math>  krawędzi, to jest drzewem.</wrongoption>
-<wrongoption>jeśli ma  <math>4851 </math>  krawędzi, to jest spójny.</wrongoption>
+<wrongoption>jeśli ma  <math>4851</math>  krawędzi, to jest spójny.</wrongoption>
-<rightoption>jeśli ma  <math>4852 </math>  krawędzi, to jest spójny.</rightoption>
+<rightoption>jeśli ma  <math>4852</math>  krawędzi, to jest spójny.</rightoption>
 </quiz>
-<quiz>Na to by graf  <math>\mathbf{T} </math>  był drzewem potrzeba i wystarcza, by:
+<quiz>Na to by graf  <math>\mathbf{T}</math>  był drzewem potrzeba i wystarcza, by:
-<wrongoption> <math>\mathbf{T} </math>  nie zawierał cykli</wrongoption>
+<wrongoption> <math>\mathbf{T}</math>  nie zawierał cykli</wrongoption>
-<rightoption> <math>\mathbf{T} </math>  był spójny i miał  <math>\left\vert V \right\vert-1 </math>  krawędzi</rightoption>
+<rightoption> <math>\mathbf{T}</math>  był spójny i miał  <math>\left\vert V \right\vert-1</math>  krawędzi</rightoption>
-<rightoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T} </math>  były połączone dokładnie jedną drogą</rightoption>
+<rightoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  były połączone dokładnie jedną drogą</rightoption>
-<wrongoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T} </math>  leżały na dokładnie jednym cyklu</wrongoption>
+<wrongoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  leżały na dokładnie jednym cyklu</wrongoption>
 </quiz>

Matematyka dyskretna 1/Test 12: Grafy: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:04, 5 wrz 2023

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia