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

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 21:15, 18 wrz 2006

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

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace } oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf 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 } . 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 $4850$ krawędzi, to jest spójny. Źle

jeśli ma $4851$ 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 6: / Linia 6: @@
 <wrongoption><math>\displaystyle 2^{n \choose 2}</math></wrongoption>
 </quiz>
 <quiz>Różnych grafów nieskierowanych bez cykli jednoelementowych  w zbiorze <math>\displaystyle n</math>-elementowym jest:
@@ Linia 14: / Linia 15: @@
 <rightoption><math>\displaystyle 2^{n \choose 2}</math></rightoption>
 </quiz>
 <quiz>Zaznacz zdania prawdziwe:
@@ Linia 21: / Linia 23: @@
 <rightoption>W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.</rightoption>
 </quiz>
 <quiz>Zaznacz zdania prawdziwe dla grafów nieskierowanych:
@@ Linia 27: / Linia 30: @@
 <wrongoption> każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego</wrongoption>
 <wrongoption> graf pełny ma zawsze parzystą liczbę krawędzi</wrongoption>
-<rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień
+<rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień</rightoption></quiz>
-</rightoption></quiz>
 <quiz>Jaka jest najmniejsza liczba krawędzi w grafie
@@ Linia 38: / Linia 41: @@
 <wrongoption> <math>\displaystyle \frac{100 \cdot 99}{3}</math></wrongoption>
 </quiz>
 <quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>\displaystyle K_{1000,1000}</math>:
@@ Linia 46: / Linia 50: @@
 <wrongoption> <math>\displaystyle 2000 \choose 1000</math></wrongoption>
 </quiz>
 <quiz>W pełnym grafie <math>\displaystyle 100</math>-elementowym:
@@ Linia 54: / Linia 59: @@
 <wrongoption> nie ma drzew rozpinających</wrongoption>
 </quiz>
 <quiz>W pełnym grafie dwudzielnym <math>\displaystyle K_{50,50}</math>:
@@ Linia 62: / Linia 68: @@
 <wrongoption> nie ma drzew rozpinających</wrongoption>
 </quiz>
 <quiz>W <math>\displaystyle 100</math> elementowym grafie o trzech składowych spójnych:
@@ Linia 70: / Linia 77: @@
 <wrongoption> może nie być lasu rozpinającego</wrongoption>
 </quiz>
 <quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:
@@ Linia 78: / Linia 86: @@
 <rightoption> jest stukolorowalny</rightoption>
 </quiz>
 <quiz>Pełny graf dwudzielny <math>\displaystyle K_{25,25}</math>:
@@ Linia 86: / Linia 95: @@
 <rightoption> jest trójkolorowalny</rightoption>
 </quiz>
 <quiz>Graf o  <math>\displaystyle 2005 </math>  wierzchołkach, z których każdy ma stopień  <math>\displaystyle 101 </math> :
@@ Linia 93: / Linia 103: @@
 <rightoption>nie istnieje</rightoption>
 </quiz>
 <quiz>Jeśli  <math>\displaystyle \mathbf{G}_1=\left( V,E_1 \right) </math>  i  <math>\displaystyle \mathbf{G}_2=\left( V,E_2 \right) </math>
@@ Linia 101: / Linia 112: @@
 <rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  nie jest spójny</rightoption>
 </quiz>
 <quiz>Graf  <math>\displaystyle \mathbf{P}_4 </math>  to graf, który składa się jedynie ze ścieżki
@@ Linia 113: / Linia 125: @@
 <wrongoption>każde trzy wierzchołki tworzą klikę  <math>\displaystyle \mathcal{K}_{3} </math></wrongoption>
 </quiz>
 <quiz>Zaznacz zdania prawdziwe:
@@ Linia 120: / Linia 133: @@
 <rightoption>Graf  <math>\displaystyle \mathcal{K}_{2} </math>  jest grafem dwudzielnym.</rightoption>
 </quiz>
 <quiz>Zaznacz zdania prawdziwe:
@@ Linia 127: / Linia 141: @@
 <wrongoption>Każdy graf dwudzielny jest grafem planarnym.</wrongoption>
 </quiz>
 <quiz>Graf o  <math>\displaystyle 100 </math>  wierzchołkach:
@@ Linia 134: / Linia 149: @@
 <rightoption>jeśli ma  <math>\displaystyle 4851 </math>  krawędzi, to jest spójny.</rightoption>
 </quiz>
 <quiz>Na to by graf  <math>\displaystyle \mathbf{T} </math>  był drzewem potrzeba i wystarcza, by:

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

Wersja z 21:15, 18 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia