Test GR4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

{thm}{Twierdzenie} {obs}[thm]{Obserwacja} {con}[thm]{Wniosek} {exrr}{Zadanie}

{ 

0mm

#1 

10mm }{{ ◻ }

}

{article} {../makraT} 

0mm
Uzupelnij tytul
Współczynniki dwumianowe 
10mm

Zależność (n0)−(n1)+…+(−1)n(nn)=0 zachodzi dla:} </rightoption> wszystkich liczb naturalnych n </wrongoption> tylko skończenie wielu liczb naturalnych n </wrongoption> żadnej liczby naturalnej n </rightoption> wszystkich, poza skończenie wieloma liczbami naturalnymi n

Suma elementów n-tego wiersza Trójkąta Pascala bez obu wartości brzegowych to:}

</wrongoption> 2n. </rightoption> 2n−2. </rightoption> ∑i=1n(ni)−1. </wrongoption> (2nn).

Współczynnik przy wyrazie xn w rozwinięciu dwumianu (x+2)2n to:} </wrongoption> (2nn). </wrongoption> 2n(n2). </rightoption> (2nn)2n. </wrongoption> (2nn)22n.

(−1k) dla k⩾0 jest równe:} </wrongoption> 0. </wrongoption> 1. </wrongoption> (−1)k. </rightoption> (−1)k+1

Suma ∑i=0n2i(ni) wynosi} </wrongoption> 2n. </rightoption> 3n. </wrongoption> (n+2)n. </wrongoption> (2nn).

Liczba nieporządków na zbiorze 3-elementowym to:} </wrongoption> 1. </rightoption> 2. </wrongoption> 3. </wrongoption> 6.

(na,b,0,…,0) gdzie a+b=n to:} </rightoption> (na). </rightoption> (nb). </wrongoption> (na+b). </wrongoption> (n+a+ba+b).

Na ile sposobów z grupy 5n osób, złożonej z 3n mężczyzn i 2n kobiet, można wybrać n-kobiet i n-mężczyzn, i dodatkowo z niewybranych mężczyzn wyznaczyć przywódcę?} </wrongoption> ((5n3n)(3nn)+(5n2n)(2nn))⋅2n. </rightoption> (3nn)(2nn)⋅2n. </wrongoption> ((3nn)+(2nn))⋅2n. </wrongoption> (3nn)(2nn)⋅3n.

Suma (07)+(17)+(27)+(37)+(47)+(57)+(67)+(77) to:} </wrongoption> 0. </wrongoption> (87). </wrongoption> (78). </rightoption> (88).

Współczynnik przy wyrazie xmyn w rozwinięciu dwumianu (x+y)m+n to:} </rightoption> (m+nm). </rightoption> (m+nn). </wrongoption> (mn). </wrongoption> ∑i=0m(m+ni).

66666666666666666666666666666

{article} {../makraT} 

0mm
Uzupelnij tytul
Permutacje i podziały 
10mm

Niech nπ,nσ,nρ będą kolejno liczbami permutacji w S7 tego samego typu co, odpowiednio, π=(14)(26)(357), σ=(1357)(246), ρ=(12)(34)(56)(7). Wtedy:} </rightoption> nπ⩽nτ⩽nρ </rightoption> nτ⩽nπ⩽nρ </wrongoption> nρ⩽nπ⩽nτ </wrongoption> nπ⩽nρ⩽nτ

Dla sprzężonych permutacji π,σ∈S13 zachodzi:} </rightoption> π i σ mają tyle samo cykli 4-elementowych </wrongoption> elementy 1 i 2 albo są w tym samym cyklu w obu permutacjach, 

   albo nie są w tym samym cyklu w obu permutacjach

</rightoption> π i σ mają ten sam typ </rightoption> π i σ mają ten sam znak

Dla n⩾2, 

   podziałowa liczba Stirlinga  {n2} wynosi:}

</wrongoption> ∑k=1n−1(nk)k!=∑k=1n−1n!k! </wrongoption> n!∑k=1n−11k(n−k) </wrongoption> n!∑k=1n−11k(n−k) </rightoption> n!2∑k=1n−11k(n−k)

Średnia liczba cykli permutacji n-elementowej (czyli stosunek sumarycznej liczby cykli we wszystkich permutacjach n-elementowych do liczby cykli n-elementowych) to:} </wrongoption> 2n </wrongoption> ⌊nlg⁡n⌋+1 </rightoption> ∑k=1n1k </wrongoption> n2

Podziałowa liczba Stirlinga{74} wynosi} </wrongoption> 90 </wrongoption> 140 </wrongoption> 301 </rightoption> 350

Jednomian xn jest równy:} </rightoption> ∑i{ni}xi_ </wrongoption> Bnxn_, gdzie Bn jest n-tą liczbą Bella </wrongoption> ∑i[ni]xi‾ </rightoption> ∑i{ni}(−1)n−ixi‾

Na ile sposobów można rozłożyć a rozróżnialnych obiektów do dokładnie b rozróżnialnych szuflad, tak by każda szufladka była niepusta?} </wrongoption> ba </wrongoption> {ab} </rightoption> b!{ab} </wrongoption> (a−1b−1)

Na ile sposobów można rozłożyć a nierozróżnialnych obiektów do co najwyżej b rozróżnialnych szuflad?} </wrongoption> (a−1b−1) </rightoption> (b+a−1b−1) </wrongoption> {ab} </wrongoption> ∑i=1b{ai}

Gdy P(n,k) jest liczbą rozkładów liczby n na sumy dokładnie k nieujemnych całkowitych składników, to limn→∞P(n,k)nk wynosi:} </rightoption> 0 </wrongoption> 1k!(k−1)! </wrongoption> 1k </wrongoption> 1

Na ile sposobów można podzielić zbiór a elementowy na b+c bloków, przy czym b bloków jest wyróżnionych?} </rightoption> {ab+c}(b+cb) </rightoption> ∑k(ak){kb}{a−kc} </wrongoption> {ab}{a−bc} </wrongoption> {ab+c}b!

777777777777777777777777777777777777777777777777777777777

{article} {../makraT} 

0mm
Uzupelnij tytul
Funkcje tworzące 
10mm

Na ile sposobów można rozmienić 25 centów za pomocą monet 1 , 5 , 10 oraz 25 centowych?} 

</wrongoption>{ 6 }
</wrongoption>{ 12 }
</rightoption>{ 13 }
</wrongoption>{ 49 }

Funkcja tworząca postaci G(x)=g0+g1x+g2x2+g3x3+… ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca U(x) taka, że U(x)G(x)=1 } 

</wrongoption>{jeśli  g0≠1 }
</rightoption>{jeśli  g0≠0 }
</rightoption>{jeśli wszystkie  gi≠0 }
</rightoption>{wtedy i tylko wtedy, gdy  g0≠0 }

Funkcja G(x) spełniająca 

G(x)=(∑n=0∞xn)⋅(1+xG(x))

jest funkcją tworzącą:} </wrongoption>{ciągu 1,1,2,4,8,16,32,…,2n−1,… } </rightoption>{ciągu geometrycznego gn=2n } </wrongoption>{nie ma takiego ciągu} </wrongoption>{nie istnieje taka funkcja tworząca}

Funkcja G(x) spełniająca 

G(x)=G′(x)  oraz  G(0)=1

jest funkcją tworzącą ciągu:} </wrongoption>{ gn=1n } </rightoption>{ gn=1n! } </wrongoption>{ gn=1 } </wrongoption>{ g0=1 oraz gn=0 dla n>1 }

Niech G(x)=(1+x)y , gdzie y jest liczba rzeczywistą. Jeśli G(x)=∑n=0∞gnxn , to:} </wrongoption>{ gn=(y+n)n_n } </wrongoption>{ gn=ynn! } </wrongoption>{ gn=(y+nn)=(y+n)n_n! } </rightoption>{ gn=(yn)=yn_n! }

Suma ∑k=0n(3k2−3k+1) wynosi:} </wrongoption>{ 2n3+3n+n ,} </rightoption>{ n3 ,} </wrongoption>{ (2n3+3n+n)/6 ,} </wrongoption>{ 3n3−3n2+n }

Niech a0=2 , a1=3 , a2=5 , oraz an+3=7an+2−16an+1+12an . Wtedy:} </wrongoption>{ an=(1−n)2n+3n } </rightoption>{ an=15((1+52)n+3−(1−52)n+3) } </wrongoption>{ an=15((1+52)n−(1−52)n) } </wrongoption>{żadna z pozostałych odpowiedzi nie jest prawidłowa}

8888888888888888888888888888888888888888888888

{article} {../makraT} 

0mm
Uzupelnij tytul
Zliczanie obiektów 
10mm

Liczby Catalana cn spełniają zależność rekurencyjną:} </wrongoption>{ cn=∑k=1n−1ck } </wrongoption>{ cn=∑k=1nck } </wrongoption>{ cn=∑k=1n−1ckcn−k } </rightoption>{ cn=∑k=1nck−1cn−k }

n -ta liczba Catalana to:} </wrongoption>{ (2nn) } </rightoption>{ 1n+1(2nn) } </wrongoption>{ (1/2n)(−4)n } </rightoption>{ 2(1/2n+1)(−4)n }

Niech t10 będzie liczbą drzew o wysokości 10 . Wtedy:} </rightoption>{ t10≤21023 } </rightoption>{ t10≥2512 } </wrongoption>{ t10≤210 } </wrongoption>{ t10≥29 }

Liczba podziałów liczby 16 na sumy złożone jedynie ze składników 1,2,4,8,16 wynosi:} </wrongoption>{ 25 } </wrongoption>{ 26 } </rightoption>{ 35 } </wrongoption>{ 165 }

Funkcja tworząca podziału liczby na sumy jest przedstawialna jako:} </rightoption>{ ∏k=1∞11−xk } </wrongoption>{ ∑k=1∞11−xk } </wrongoption>{ ∑n=0∞∏k=1∞11−xnk } </rightoption>{ ∏k=1∞∑n=0∞xnk }

Funkcja tworząca 

sn(x)=[n0]+[n1]x+[n2]x2+[n3]x3+…,

dla cyklowych liczb Stirlinga [nm] , ma postać zwartą: } </rightoption>{ sn(x)=xn‾ } </rightoption>{ sn(x)=∏k=0n−1(x+k) } </wrongoption>{ sn(x)=xn_ } </wrongoption>{ sn(x)=1/∏k=0n−1(1−kx) }

Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:} </wrongoption>{ {nk}=(n−1){n−1k}+{n−1k−1} , dla 0>k>n } </wrongoption>{ {n+kk}={n+k−1k}+k{n+k−1k−1} , dla n>1, k>0 } </rightoption>{ {n+kk}=k{n+k−1k}+{n+k−1k−1} , dla n>1, k>0 } </wrongoption>{żadna z pozostałych odpowiedzi nie jest prawidłowa}

Niech a0=1 , a1=0 oraz an=an−2n . Funkcja tworząca A(x)=∑n=0∞anxn ma postać zwartą:} </wrongoption>{ A(x)=sin⁡x } </wrongoption>{ A(x)=ex2 } </rightoption>{ A(x)=ex2/2 } </wrongoption>{żadna z pozostałych odpowiedzi nie jest prawidłowa}

999999999999999999999999999999999999999

{article} {../makraT} 

0mm
Uzupelnij tytul
Asymptotyka 
10mm

Funkcja n2lg⁡n+n2nlg⁡n jest:} </wrongoption> Θ(n2lg⁡n) </wrongoption> O(n2lg⁡n) </wrongoption> Θn2n </rightoption> O(n2nlg⁡n)

Funkcja n9lg10n jest:} </wrongoption> O(n910) </wrongoption> O(n) </rightoption> O(n9) </rightoption> Ω(lg10n)

Dla f(n)=2lg⁡n+1 oraz g(n)=lg⁡2n−1 zachodzi:} </wrongoption> f(x)=ω(g(x)) </rightoption> f(x)=Ω(g(x)) </rightoption> f(x)=Θ(g(x)) </rightoption> f(x)=O(g(x)) </wrongoption> f(x)=o(g(x))

Dowolny wielomian k-tego stopnia jest:} </rightoption> Ω(nk) </rightoption> Θ(nk) </rightoption> O(nk) </rightoption> o(nk+ε) dla dowolnego ε>0

Dla f(n)=lg⁡nn oraz g(n)=1n zachodzi:} </wrongoption> f(x)=ω(g(x)) </wrongoption> f(x)=Ω(g(x)) </wrongoption> f(x)=Θ(g(x)) </rightoption> f(x)=O(g(x)) </rightoption> f(x)=o(g(x))

Dla f(x)=x2 oraz g(x)=x2+sin⁡x zachodzi:} </rightoption> f(x)=Ω(g(x)) </rightoption> f(x)=Θ(g(x)) </rightoption> f(x)=O(g(x)) </wrongoption> żadne z pozostałych

Dla T(n)=9T(n3)+n2lg⁡n:} </wrongoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(n2) </wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(n2lg⁡n) </wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(n2lg⁡n) </rightoption> żadne z pozostałych

Dla T(n)=25T(n4)+n2lg⁡n} </rightoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(nlg425) </wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(n2) </wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i T(n)=Θ(n2lg⁡n) </wrongoption> żadne z pozostałych

Funkcja spełniająca zależność T(n)=T(n2)+1 jest:} </rightoption> Θ(lg⁡n) </rightoption> Θ(n) </rightoption> O(n) </wrongoption> żadne z pozostałych

101010101010101010101010101010101010

{article} {../makraT} 

0mm
Uzupelnij tytul
Teoria liczb I 
10mm

Liczb naturalnych n>1 w rozkładzie których występują wszystkie liczby pierwsze niewiększe od n jest:} </wrongoption> nieskończenie wiele </rightoption> co najmniej jedna </rightoption> skończenie wiele </wrongoption> nie ma takich liczb

Liczb pierwszych postaci 91n+7, dla n∈ℕ jest:} </wrongoption> nie ma takich liczb </rightoption> dokładnie jedna </rightoption> skończenie wiele </wrongoption> nieskończenie wiele

Jeśli w ciągu postaci {an+b}n∈ℕ, gdzie a,b∈ℕ, 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> a i b są względnie pierwsze

Jeśli p jest dowolną liczbą pierwszą, to sito Eratostenesa zastosowane do liczby p2+2 jako ostatnią skreśli:} </wrongoption> p </rightoption> p2 </wrongoption> p2+1 </wrongoption> p2+2

Jeśli a|bc oraz NWD (a,b)=d, to} </rightoption> ad|c </rightoption> a|cd </rightoption> ad⊥b </rightoption> ad⊥bd

Liczb pierwszych postaci n2−1, gdzie n∈ℕ, jest:} </wrongoption> 0 </rightoption> 1 </rightoption> skończenie wiele </wrongoption> nieskończenie wiele

Jeśli a i b są liczbami złożonymi to} </wrongoption> NWD (a,b)>1 </rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{a}{ } NWD (a,b)⊥b NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} </wrongoption> jedna z liczb Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{a}{ } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{b}{ } NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} jest pierwsza </wrongoption> jeśli a⊥b, to przynajmniej jedna z liczb a−b, a+b jest parzysta

Jeśli a|c i b|c, to} </wrongoption> NWD (a,b)>1 </wrongoption> NWD (a,b)<c </rightoption> jeśli NWD (a,b)>1, to NWW (a,b)<c </rightoption> NWW (a,b)⩽c

Rosnący ciąg arytmetyczny rozpoczynający się od 1:} </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

11111111111111111111111111111111

{article} {../makraT} 

0mm
Uzupelnij tytul
Teoria liczb II 
10mm

Jeśli d⊥n oraz acd≡cnbcd, to} </rightoption> a≡nb </rightoption> ad≡nbd </rightoption> acd≡nbcd </wrongoption> ac≡ndbc

Równanie 7x≡914} </wrongoption> nie ma rozwiązania </wrongoption> ma skończenie wiele rozwiązań </wrongoption> zbiór wszystkich jego rozwiązań jest postaci {13n+c:n∈ N} dla pewnego c∈ℕ </rightoption> zbiór wszystkich rozwiązań jest postaci {91n+c:n∈ℕ} dla pewnego c∈ℕ

Układ równań

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&\equiv_9&8,\\ x&\equiv_{223}&222. \endaligned}

} </rightoption> ma całkowite rozwiązanie mniejsze od 2006 </wrongoption> 2006 jest jego jedynym rozwiązaniem </wrongoption> wszystkie jego rozwiązania są postaci 2006⋅n, gdzie n∈ℤ </rightoption> wszystkie jego rozwiązania są postaci 2007n+2006

Dla a<b warunek φ(a)⩽φ(b) zachodzi jeśli} </wrongoption> a⩽b </rightoption> a|b </wrongoption> a⊥b </rightoption> a⩽b i b jest pierwsza

1649 { mod} 25 wynosi:} </wrongoption> 1 </wrongoption> 7 </wrongoption> 14 </rightoption> 21

14111 { mod} 15 wynosi:} </wrongoption> 1 </wrongoption> 3 </wrongoption> 12 </rightoption> 14

Wiedząc, że 2006=2⋅17⋅59 oblicz μ(2006): } </rightoption> −1 </wrongoption> 0 </wrongoption> 1 </wrongoption> 3

(n−1)! modulo n to:} </rightoption> 0, jeśli n jest złożona a −1, jeśli n jest pierwsza </rightoption> 0, jeśli n jest złożona a n−1, jeśli n jest pierwsza </wrongoption> 0, jeśli n jest złożona a 1, jeśli n jest pierwsza </wrongoption> zawsze wynosi 1

12121212121212121212121212121212

{article} {../makraT} 

0mm
Uzupelnij tytul
Grafy I 
10mm

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=53396”