Test GR4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
8888888888888888888888888888888888888888888888
999999999999999999999999999999999999999
<quiz>Funkcja <math>\displaystyle n^2\lg{n}+\frac{n^2\sqrt{n}}{\lg{n}}</math> jest:}
<wrongoption> <math>\displaystyle \Theta(n^2\lg{n})</math>
<wrongoption> <math>\displaystyle O(n^2\lg{n})</math>
<wrongoption> <math>\displaystyle \Theta{n^2\sqrt{n}}</math>
<rightoption>  <math>\displaystyle O(\frac{n^2\sqrt{n}}{\lg{n}})</math>
</quiz>
<quiz>Funkcja <math>\displaystyle \frac{n^9}{\lg^{10}n}</math> jest:}
<wrongoption> <math>\displaystyle O(n^{\frac{9}{10}})</math>
<wrongoption> <math>\displaystyle O(n)</math>
<rightoption>  <math>\displaystyle O(n^9)</math>
<rightoption>  <math>\displaystyle \Omega(\lg^{10}n)</math>
</quiz>
<quiz>Dla <math>\displaystyle f(n)=2^{\lg{n}+1}</math> oraz <math>\displaystyle g(n)=\lg{2n}-1</math> zachodzi:}
<wrongoption> <math>\displaystyle f(x)=\omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=o(g(x))</math>
</quiz>
<quiz>Dowolny wielomian <math>\displaystyle k</math>-tego stopnia jest:}
<rightoption>  <math>\displaystyle \Omega(n^k)</math>
<rightoption>  <math>\displaystyle \Theta(n^k)</math>
<rightoption>  <math>\displaystyle O(n^k)</math>
<rightoption>  <math>\displaystyle o(n^{k+\varepsilon})</math> dla dowolnego <math>\displaystyle \varepsilon>0</math>
</quiz>
<quiz>Dla <math>\displaystyle f(n)=\frac{\lg n}{n}</math> oraz <math>\displaystyle g(n)=\frac{1}{\sqrt{n}}</math> zachodzi:}
<wrongoption> <math>\displaystyle f(x)=\omega(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=\Omega(g(x))</math>
<wrongoption> <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=o(g(x))</math>
</quiz>
<quiz>Dla <math>\displaystyle f(x)=x^2</math> oraz <math>\displaystyle g(x)=x^2+\sin x</math> zachodzi:}
<rightoption>  <math>\displaystyle f(x)=\Omega(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=\Theta(g(x))</math>
<rightoption>  <math>\displaystyle f(x)=O(g(x))</math>
<wrongoption> żadne z pozostałych
</quiz>
<quiz>Dla <math>\displaystyle T(n)=9T(\frac{n}{3})+\frac{n^2}{\lg n}</math>:}
<wrongoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2)</math>
<wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2\lg n)</math>
<wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(\frac{n^2}{\lg n})</math>
<rightoption>  żadne z pozostałych
</quiz>
<quiz>Dla <math>\displaystyle T(n)=25T(\frac{n}{4})+\frac{n^2}{\lg n}</math>}
<rightoption>  możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^{\lg_4{25}})</math>
<wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(n^2)</math>
<wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i <math>\displaystyle T(n)=\Theta(\frac{n^2}{\lg n})</math>
<wrongoption> żadne z pozostałych
</quiz>
<quiz>Funkcja spełniająca zależność <math>\displaystyle T(n)=T(\frac{n}{2})+1</math> jest:}
<rightoption>  <math>\displaystyle \Theta(\lg n)</math>
<rightoption>  <math>\displaystyle \Theta(n)</math>
<rightoption>  <math>\displaystyle O(n)</math>
<wrongoption> żadne z pozostałych
</quiz>
101010101010101010101010101010101010
{article}
{../makraT}
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Teoria liczb I'''
|-
|
|}
10mm
<quiz>Liczb naturalnych <math>\displaystyle n>1</math> w rozkładzie których
występują wszystkie liczby pierwsze niewiększe od <math>\displaystyle n</math> jest:}
<wrongoption> nieskończenie wiele
<rightoption>  co najmniej jedna
<rightoption>  skończenie wiele
<wrongoption> nie ma takich liczb
</quiz>
<quiz>Liczb pierwszych postaci <math>\displaystyle 91n+7</math>, dla <math>\displaystyle n\in\mathbb{N}</math> jest:}
<wrongoption> nie ma takich liczb
<rightoption>  dokładnie jedna
<rightoption>  skończenie wiele
<wrongoption> nieskończenie wiele
</quiz>
<quiz>Jeśli w ciągu postaci <math>\displaystyle \left\lbrace an+b \right\rbrace_{n\in\mathbb{N}}</math>, gdzie <math>\displaystyle a,b\in\mathbb{N}</math>, 
są przynajmniej dwie liczby pierwsze, to}
<rightoption>  jest ich nieskończenie wiele
<wrongoption> wszystkie liczby tego ciągu są pierwsze
<wrongoption> może ich być tylko skończenie wiele
<rightoption>  <math>\displaystyle a</math> i <math>\displaystyle b</math> są względnie pierwsze
</quiz>
<quiz>Jeśli <math>\displaystyle p</math> jest dowolną liczbą pierwszą, to sito Eratostenesa
zastosowane do liczby <math>\displaystyle p^2+2</math> jako ostatnią skreśli:}
<wrongoption> <math>\displaystyle p</math>
<rightoption>  <math>\displaystyle p^2</math>
<wrongoption> <math>\displaystyle p^2+1</math>
<wrongoption> <math>\displaystyle p^2+2</math>
</quiz>
<quiz>Jeśli <math>\displaystyle a|bc</math> oraz  NWD <math>\displaystyle  (a,b)=d</math>, to}
<rightoption>  <math>\displaystyle \frac{a}{d}|c</math>
<rightoption>  <math>\displaystyle a|cd</math>
<rightoption>  <math>\displaystyle \frac{a}{d}\perp b</math>
<rightoption>  <math>\displaystyle \frac{a}{d}\perp\frac{b}{d}</math>
</quiz>
<quiz>Liczb pierwszych postaci <math>\displaystyle n^2-1</math>, gdzie <math>\displaystyle n\in\mathbb{N}</math>, jest:}
<wrongoption> <math>\displaystyle 0</math>
<rightoption>  <math>\displaystyle 1</math>
<rightoption>  skończenie wiele
<wrongoption> nieskończenie wiele
</quiz>
<quiz>Jeśli <math>\displaystyle a</math> i <math>\displaystyle b</math> są liczbami złożonymi to}
<wrongoption>  NWD <math>\displaystyle  (a,b)>1</math>
<rightoption>  <math>\displaystyle \frac{a}{ </math>  NWD <math>\displaystyle  (a,b)}\perp\frac{b}{ </math>  NWD <math>\displaystyle  (a,b)}</math>
<wrongoption> jedna z liczb <math>\displaystyle \frac{a}{ </math>  NWD <math>\displaystyle  (a,b)}</math>, <math>\displaystyle \frac{b}{ </math>  NWD <math>\displaystyle  (a,b)}</math> jest pierwsza
<wrongoption> jeśli <math>\displaystyle a\perp b</math>, to przynajmniej jedna z liczb <math>\displaystyle a-b</math>, <math>\displaystyle a+b</math> jest parzysta
</quiz>
<quiz>Jeśli <math>\displaystyle a|c</math> i <math>\displaystyle b|c</math>, to}
<wrongoption>  NWD <math>\displaystyle  (a,b)>1</math>
<wrongoption>  NWD <math>\displaystyle  (a,b)<c</math>
<rightoption>  jeśli  NWD <math>\displaystyle  (a,b)>1</math>, to  NWW <math>\displaystyle  (a,b)<c</math>
<rightoption>    NWW <math>\displaystyle  (a,b)\leqslant c</math>
</quiz>
<quiz>Rosnący ciąg arytmetyczny rozpoczynający się od <math>\displaystyle 1</math>:}
<rightoption>  zawsze zawiera nieskończenie wiele liczb pierwszych
<wrongoption> może zawierać tylko skończenie wiele liczb pierwszych
<wrongoption> zawsze zawiera tylko skończenie wiele liczb pierwszych
<wrongoption> może nie zawierać żadnej liczby pierwszej
</quiz>
11111111111111111111111111111111
{article}
{../makraT}
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Teoria liczb II'''
|-
|
|}
10mm
<quiz>Jeśli <math>\displaystyle d\perp n</math> oraz  <math>\displaystyle acd\equiv_{cn}bcd</math>, to}
<rightoption>  <math>\displaystyle a\equiv_nb</math>
<rightoption>  <math>\displaystyle ad\equiv_nbd</math>
<rightoption>  <math>\displaystyle acd\equiv_nbcd</math>
<wrongoption> <math>\displaystyle ac\equiv_{nd}bc</math>
</quiz>
<quiz>Równanie <math>\displaystyle 7x\equiv_{91}4</math>}
<wrongoption> nie ma rozwiązania
<wrongoption> ma skończenie wiele rozwiązań
<wrongoption> zbiór wszystkich jego rozwiązań jest postaci <math>\displaystyle \left\lbrace 13n+c:n\in\ N \right\rbrace</math> dla pewnego <math>\displaystyle c\in\mathbb{N}</math>
<rightoption>  zbiór wszystkich rozwiązań jest postaci <math>\displaystyle \left\lbrace 91n+c:n\in\mathbb{N} \right\rbrace</math> dla pewnego <math>\displaystyle c\in\mathbb{N}</math>
</quiz>
<quiz>Układ równań
<center><math>\displaystyle \aligned x&\equiv_9&8,\\
x&\equiv_{223}&222.
\endaligned</math></center>
}
<rightoption>  ma całkowite rozwiązanie mniejsze od 2006
<wrongoption> <math>\displaystyle 2006</math> jest jego jedynym rozwiązaniem
<wrongoption> wszystkie jego rozwiązania są postaci <math>\displaystyle 2006\cdot n</math>, gdzie <math>\displaystyle n\in\mathbb{Z}</math>
<rightoption>  wszystkie jego rozwiązania są postaci <math>\displaystyle 2007n+2006</math>
</quiz>
<quiz>Dla <math>\displaystyle a<b</math> warunek <math>\displaystyle \varphi(a)\leqslant\varphi(b)</math> zachodzi jeśli}
<wrongoption> <math>\displaystyle a\leqslant b</math>
<rightoption>  <math>\displaystyle a|b</math>
<wrongoption> <math>\displaystyle a\perp b</math>
<rightoption>  <math>\displaystyle a\leqslant b</math> i <math>\displaystyle b</math> jest pierwsza
</quiz>
<quiz><math>\displaystyle 16^{49}  </math>  { mod}  <math>\displaystyle  25</math> wynosi:}
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 7</math>
<wrongoption> <math>\displaystyle 14</math>
<rightoption>  <math>\displaystyle 21</math>
</quiz>
<quiz><math>\displaystyle 14^{111}  </math>  { mod}  <math>\displaystyle  15</math> wynosi:}
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 3</math>
<wrongoption> <math>\displaystyle 12</math>
<rightoption>  <math>\displaystyle 14</math>
</quiz>
<quiz>Wiedząc, że <math>\displaystyle 2006=2\cdot17\cdot59</math> oblicz <math>\displaystyle \mu(2006)</math>: }
<rightoption>  <math>\displaystyle -1</math>
<wrongoption> <math>\displaystyle 0</math>
<wrongoption> <math>\displaystyle 1</math>
<wrongoption> <math>\displaystyle 3</math>
</quiz>
<quiz><math>\displaystyle (n-1)!</math> modulo <math>\displaystyle n</math> to:}
<rightoption>  <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle -1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<rightoption>  <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle n-1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<wrongoption> <math>\displaystyle 0</math>, jeśli <math>\displaystyle n</math> jest złożona a <math>\displaystyle 1</math>, jeśli <math>\displaystyle n</math> jest pierwsza
<wrongoption> zawsze wynosi <math>\displaystyle 1</math>
</quiz>
12121212121212121212121212121212
12121212121212121212121212121212
{article}
{../makraT}
0mm
{| border=1
|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
|-
| '''Grafy I'''
|-
|
|}
10mm


<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>\displaystyle n</math>-elementowym jest:}
<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>\displaystyle n</math>-elementowym jest:}

Wersja z 18:22, 18 wrz 2006

12121212121212121212121212121212

Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze n-elementowym jest:} <wrongoption> 2n2 <rightoption> 2n2−n <wrongoption> 22n <wrongoption> 22n−n <wrongoption> 2(n2)

Różnych grafów nieskierowanych bez cykli jednoelementowych w zbiorze n-elementowym jest:} <wrongoption> 2n2 <wrongoption> 2n2−n <wrongoption> 22n <wrongoption> 22n−n <rightoption> 2(n2)

Zaznacz zdania prawdziwe:} <wrongoption> W każdym grafie prostym G=(V;E) relacja E musi być zwrotna. <rightoption> W grafie nieskierowanym G=(V,E) relacja E jest symetryczna. <wrongoption> Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków. <rightoption> W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.

Zaznacz zdania prawdziwe dla grafów nieskierowanych:} <rightoption> podgraf indukowany grafu pełnego jest grafem pełnym <rightoption> każdy graf jest podgrafem jakiegoś grafu pełnego <wrongoption> każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego <wrongoption> graf pełny ma zawsze parzystą liczbę krawędzi <rightoption> w grafie pełnym wszystkie wierzchołki mają ten sam stopień

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

<wrongoption> 99
<rightoption> 97
<wrongoption> 98
<wrongoption> 100
<wrongoption> 100⋅993

Ile jest krawędzi w pełnym grafie dwudzielnym K1000,1000:} 

<rightoption> 1000⋅1000
<wrongoption> 1000!
<wrongoption> (10002)
<wrongoption> (100050)
<wrongoption> (20001000)

W pełnym grafie 100-elementowym:} <wrongoption> każde drzewo rozpinające ma 100 krawędzi <wrongoption> dokładnie jedno drzewo rozpinające ma 100 krawędzi <rightoption> każde drzewo rozpinające ma 99 krawędzi <wrongoption> dokładnie jedno drzewo rozpinające ma 99 krawędzi <wrongoption> nie ma drzew rozpinających

W pełnym grafie dwudzielnym K50,50:} <wrongoption> każde drzewo rozpinające ma 50 krawędzi <wrongoption> każde drzewo rozpinające ma 100 krawędzi <rightoption> każde drzewo rozpinające ma 99 krawędzi <wrongoption> dokładnie jedno drzewo rozpinające ma 99 krawędzi <wrongoption> nie ma drzew rozpinających

W 100 elementowym grafie o trzech składowych spójnych:} <wrongoption> jakiś las rozpinający ma 100 krawędzi <wrongoption> jakiś las rozpinający ma 99 krawędzi <wrongoption> jakiś las rozpinający ma 98 krawędzi <rightoption> jakiś las rozpinający ma 97 krawędzi <wrongoption> może nie być lasu rozpinającego

Pełny graf 100-elementowy:} <rightoption> jest grafem Hamiltonowskim <wrongoption> jest grafem Eulerowskim <wrongoption> jest spójny <wrongoption> jest dwudzielny <rightoption> jest stukolorowalny

Pełny graf dwudzielny K25,25:} <rightoption> jest grafem Hamiltonowskim <wrongoption> jest grafem Eulerowskim <rightoption> zawiera cykl 4 wierzchołkach jako podgraf indukowany <wrongoption> zawiera cykl 6 wierzchołkach jako podgraf indukowany <rightoption> jest trójkolorowalny

Graf o 2005 wierzchołkach, z których każdy ma stopień 101 :} <wrongoption>ma 202505 krawędzi} <wrongoption>ma 2106 krawędzi} <wrongoption>ma 405010 krawędzi} <rightoption>nie istnieje}

Jeśli 𝐆1=(V,E1) i 𝐆2=(V,E2) są grafami niespójnymi o tym samym zbiorze wierzchołków V , to:} <rightoption>graf 𝐆1∪𝐆1 może być spójny} <wrongoption>graf 𝐆1∪𝐆1 jest spójny} <rightoption>graf 𝐆1∩𝐆1 może nie być spójny} <rightoption>graf 𝐆1∩𝐆1 nie jest spójny}

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 :} <rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy} <rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa} <wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden} <wrongoption>każde trzy wierzchołki tworzą klikę 𝒦3 }

Zaznacz zdania prawdziwe:} <rightoption>Każdy graf pusty jest grafem dwudzielnym.} <wrongoption>Każdy graf pełny jest grafem dwudzielnym.} <wrongoption>Graf 𝒦3 jest grafem dwudzielnym.} <rightoption>Graf 𝒦2 jest grafem dwudzielnym.}

Zaznacz zdania prawdziwe:} <rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.} <rightoption>Graf 𝒦4 jest grafem planarnym.} <wrongoption>Graf 𝒦5 jest grafem planarnym.} <wrongoption>Każdy graf dwudzielny jest grafem planarnym.}

Graf o 100 wierzchołkach:} <wrongoption>jeśli ma 99 krawędzi, to jest drzewem.} <wrongoption>jeśli ma 100 krawędzi, to jest drzewem.} <wrongoption>jeśli ma 4850 krawędzi, to jest spójny.} <rightoption>jeśli ma 4851 krawędzi, to jest spójny.}

Na to by graf 𝐓 był drzewem potrzeba i wystarcza, by:} <wrongoption> 𝐓 nie zawierał cykli} <rightoption> 𝐓 był spójny i miał |V|−1 krawędzi} <rightoption>dowolne dwa wierzchołki grafu 𝐓 były połączone dokładnie jedną drogą} <wrongoption>dowolne dwa wierzchołki grafu 𝐓 leżały na dokładnie jednym cyklu}

131313131313131313131313131313

{article} {../makraT} 

0mm
Uzupelnij tytul
Grafy II 
10mm

Pełny graf dwudzielny 𝒦3,3 :} <wrongoption>jest eulerowski} <rightoption>jest hamiltonowski} <wrongoption>jest planarny} <wrongoption>nie jest ani eulerowski ani planarny}

Pełny graf 100-elementowy:} <rightoption> jest grafem Hamiltonowskim <wrongoption> jest grafem Eulerowskim <wrongoption> jest spójny <wrongoption> jest dwudzielny <rightoption> jest stukolorowalny

Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera} <wrongoption>sam jest cyklem o parzystej liczbie krawędzi} <rightoption>jest cyklem} <rightoption>ma wierzchołki wyłącznie o stopniu 2 } <wrongoption>jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem}

Jeśli graf 𝐆 jest eulerowski, to:} <wrongoption>graf 𝐆 jest hamiltonowski} <rightoption>każdy wierzchołek w grafie 𝐆 ma parzysty stopień} <rightoption>graf 𝐆 jest sumą grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem} <wrongoption>jeśli dodatkowo 𝐆 jest hamiltonowski, to po usunięciu cyklu Hamiltona graf 𝐆 dalej jest eulerowski}

Graf o 101 wierzchołkach:} <wrongoption>w którym wszystkie wierzchołki są stopnia 50 , jest hamiltonowski} <rightoption>w którym wszystkie wierzchołki są stopnia 51 , jest hamiltonowski} <wrongoption>w którym dowolne dwa niesąsiednie wierzchołki v i w spełniają deg⁡v+deg⁡w≥100 jest hamiltonowski} <wrongoption>w którym dowolne dwa sąsiednie wierzchołki v i w spełniają deg⁡v+deg⁡w≥100 jest hamiltonowski}

Który z warunków wystarcza na to, by w grafie dwudzielnym 𝐆=(V1∪V2,E) istniało pełne skojarzenie V1 z V2 ?} <rightoption>graf 𝐆 jest hamiltonowski} <wrongoption>graf 𝐆 jest eulerowski} <wrongoption>w grafie 𝐆 każdy wierzchołek z V1 ma co najmniej dwu sąsiadów} <rightoption>dowolny zbiór niezależny w ma co najwyżej |V2| wierzchołków}

Grafem 100 -spójnym jest:} <rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje 100 dróg wierzchołkowo rozłącznych} <wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej 99 wierzchołków} <rightoption>klika 𝒦101 } <wrongoption>pełny graf dwudzielny 𝒦100,100 }

W 2 -spójnym krawędziowo grafie o 20 wierzchołkach i minimalnej liczbie krawędzi:} <wrongoption>jest dokładnie 38 krawędzi} <rightoption>jest dokładnie 20 krawędzi} <rightoption>dowolny wierzchołek ma stopień co najmniej 2 } <wrongoption>istnieje wierzchołek o stopniu co najmniej 3 }

141414141414141414141414141414141414141414

{article} {../makraT} 

0mm
Uzupelnij tytul
Grafy III 
10mm

Który z grafów przedstawionych na Rysunku Uzupelnic test petersen4| jest planarny? 

[!ht]

{test_petersen4} { [Rysunek z pliku: testpetersen4.eps]}

}

<wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.a.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.b.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.c.} <rightoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.d.}

Który z grafów przedstawionych na Rysunku Uzupelnic test klika5| jest homeomorficzny z kliką 𝒦5 ? 

[!ht]

{test_klika5} { [Rysunek z pliku: testklika5.eps]}

}

<wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.a.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.b.} <rightoption>graf przedstawiony na rysunku Uzupelnic test klika5|.c.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.d.}

Spójny graf planarny o 20 wierzchołkach, z których każdy jest stopnia 3 ma:} <wrongoption> 11 ścian} <rightoption> 12 ścian} <wrongoption> 22 ścian} <wrongoption> 24 ścian}

Ile spójnych składowych ma graf planarny o 121 wierzchołkach, 

53  krawędziach, oraz  30  ścianach?}

<rightoption> 98 } <wrongoption> 99 } <wrongoption> 100 } <wrongoption> 143 }

Niech 𝐆* będzie grafem geometrycznie dualnym do grafu płaskiego 𝐆 . Podzbiór C zbioru krawędzi grafu 𝐆 jest cyklem w grafie 𝐆 wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru C } <wrongoption>posiada parzystą liczbę elementów} <wrongoption>posiada nieparzystą liczbę elementów} <wrongoption>jest cyklem grafu 𝐆* } <rightoption>jest rozcięciem grafu 𝐆* }

Spójny graf prosty, który nie jest pełny, 

i w którym wszystkie wierzchołki  mają stopień nie większy niż  k jest:}

<wrongoption> (k−1) -kolorowalny} <rightoption> k -kolorowalny} <rightoption> (k+1) -kolorowalny} <rightoption> 2k -kolorowalny}

Iloma kolorami można pokolorować polityczną mapę Europy?} <wrongoption> 3 } <rightoption> 4 } <rightoption> 5 } <rightoption> 6 }

W grafie prostym zachodzi:} <rightoption> χ(𝐆)≤χs(𝐆)+1 } <wrongoption> χ(𝐆)≤χs(𝐆) } <wrongoption> χ(𝐆)≥χs(𝐆)+1 } <wrongoption> χ(𝐆)=χs(𝐆) }

Pełny graf dwudzielny K50,50:} <rightoption> jest grafem Hamiltonowskim <rightoption> jest grafem Eulerowskim <wrongoption> jest lasem <rightoption> jest dwukolorowalny <rightoption> jest 49-kolorowalny

151515151515151515151515151515151515

{article} {../makraT} 

0mm
Uzupelnij tytul
Metody algebraiczne w teorii grafów 
10mm

Niech mij oznacza liczbę skierowanych marszrut, nie dłuższych niż n−1 , z wierzchołka vi do vj w grafie skierowanym 𝐆=({v1,…,vn},E) , a M niech będzie macierzą ⟨mij⟩ . Wtedy:} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M={\sf A}\left( \mathbf{G} \right)^1+{\sf A}\left( \mathbf{G} \right)^2+\ldots+{\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) } } <rightoption> mij>0 wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( v_i,v_j \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right) } }

Zaznacz prawdziwe zależności dla grafu prostego 𝐆 o macierzy sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } , macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) } , zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } oraz macierzy stopni Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf D}\left( \mathbf{G} \right) }  :} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) } } <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf D}\left( \mathbf{G} \right)+ {\sf A}\left( \mathbf{G} \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right)\cdot {\sf C}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) } }

Niech 𝐆 będzie grafem o 10 wierzchołkach przedstawionym na Rysunku Uzupelnic test alg|, a macierz M , o rozmiarach 9×9 , będzie minorem (podmacierzą) zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } , w którym kolumny odpowiadają krawędziom 

e0,e2,e3,e6,e9,e12,e13,e14,e15 . 

[!ht]

{test_alg} {Graf 𝐆 . [Rysunek z pliku: testalg.eps]}

Wtedy:} <rightoption>macierz M jest nieosobliwa} <wrongoption>macierz M jest osobliwa} <wrongoption>suma elementów w każdej kolumnie macierzy M wynosi 0 } <wrongoption>macierz M jest antysymetryczna}

Na to by permanent grafu 𝐆 był niezerowy, wystarcza by:} <rightoption>graf 𝐆 posiadał cykl Hamiltona} <wrongoption>graf 𝐆 posiadał cykl Eulera} <wrongoption>graf 𝐆 był spójny} <rightoption>graf 𝐆 był grafem dwudzielnym posiadającym skojarzenie doskonałe}

Zaznacz zdania prawdziwe o wartościach własnych grafów:} <wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.} <wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.} <rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.} <rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.}

Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka w grafie prostym:} <wrongoption> λmax(𝐆)=Δ(𝐆) } <rightoption> |λmax(𝐆)|≤Δ(𝐆) } <rightoption> λmax(𝐆)=Δ(𝐆) wtedy i tylko wtedy, gdy któraś spójna składowa grafu 𝐆 jest grafem regularnym stopnia Δ(𝐆) } <rightoption> −Δ(𝐆) jest wartością własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } wtedy i tylko wtedy, gdy 𝐆 jest regularnym grafem dwudzielnym stopnia Δ(𝐆) }

W grafie regularnym 𝐆 o 10 wierzchołkach stopnia 4 oraz wartościach własnych λmin(𝐆)≈−2,73205 i λmax(𝐆)=4 moc niezależnego podzbioru jest ograniczona z góry przez:} <wrongoption> 2 } <wrongoption> 3 } <rightoption> 4 }<rightoption> 10 }

Zaznacz zdania prawdziwe wiążące liczbę chromatyczną χ(𝐆) z wartościami własnymi grafu regularnego 𝐆 :} <rightoption> χ(𝐆)≥1−λmax(𝐆)λmin(𝐆) } <wrongoption> χ(𝐆)=1−λmax(𝐆)λmin(𝐆) } <rightoption> χ(𝐆)≤λmax(𝐆)+1 } <wrongoption> χ(𝐆)≥λmax(𝐆) }

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR4&oldid=53578”