Test GR4

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?

$6$ Źle

$12$ Źle

$13$ Dobrze

$49$ Źle

Funkcja tworząca postaci $G\left(x\right)=g_0+g_{1}x+g_2{x}^2+g_3{x}^3+\dots$ ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca $U\left(x\right)$ taka, że $U\left(x\right)G\left(x\right)=1$:

 jeśli  $g_0\ne 1$ Źle


 jeśli  $g_0\ne 0$ Dobrze


 jeśli wszystkie  $g_i\ne 0$ Dobrze


 wtedy i tylko wtedy, gdy  $g_0\ne 0$ Dobrze

Funkcja $G\left(x\right)$ spełniająca

$G\left(x\right)=\left(\sum _{n=0}^{\mathrm{\infty }}{x}^n\right)\cdot (1+xG\left(x\right))$ 

jest funkcją tworzącą:} <wrongoption>ciągu $1,1,2,4,8,16,32,\dots ,2^{n-1},\dots$ } <rightoption>ciągu geometrycznego $g_n=2^n$ } <wrongoption>nie ma takiego ciągu} <wrongoption>nie istnieje taka funkcja tworząca}

Funkcja $G\left(x\right)$ spełniająca

$G\left(x\right)=G^{\prime }\left(x\right)$  oraz  $G\left(0\right)=1$ 

jest funkcją tworzącą ciągu:} <wrongoption> $g_n=\frac{1}{n}$ } <rightoption> $g_n=\frac{1}{n!}$ } <wrongoption> $g_n=1$ } <wrongoption> $g_0=1$ oraz $g_n=0$ dla $n>1$ }

Niech $G\left(x\right)={(1+x)}^y$ , gdzie $y$ jest liczba rzeczywistą. Jeśli $G\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{g}_n{x}^n$ , to:} <wrongoption> $g_n=\frac{{(y+n)}^{\underset{\_}{n}}}{n}$ } <wrongoption> $g_n=\frac{y^n}{n!}$ } <wrongoption> $g_n=(\genfrac{}{}{0ex}{}{y+n}{n})=\frac{{(y+n)}^{\underset{\_}{n}}}{n!}$ } <rightoption> $g_n=(\genfrac{}{}{0ex}{}{y}{n})=\frac{y^{\underset{\_}{n}}}{n!}$ }

Suma $\sum _{k=0}^n(3k^2-3k+1)$ wynosi:} <wrongoption> $2n^3+3n+n$ ,} <rightoption> $n^3$ ,} <wrongoption> $(2n^3+3n+n)/6$ ,} <wrongoption> $3n^3-3n^2+n$ }

Niech $a_0=2$ , $a_1=3$ , $a_2=5$ , oraz $a_{n+3}=7a_{n+2}-16a_{n+1}+12a_n$ . Wtedy:} <wrongoption> $a_n=(1-n)2^n+3^n$ } <rightoption> $a_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^{n+3}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+3})$ } <wrongoption> $a_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

---

8888888888888888888888888888888888888888888888

{article} {../makraT}

0mm

Uzupelnij tytul

Zliczanie obiektów

10mm

Liczby Catalana $c_n$ spełniają zależność rekurencyjną:} <wrongoption> $c_n=\sum _{k=1}^{n-1}{c}_k$ } <wrongoption> $c_n=\sum _{k=1}^n{c}_k$ } <wrongoption> $c_n=\sum _{k=1}^{n-1}{c}_k{c}_{n-k}$ } <rightoption> $c_n=\sum _{k=1}^n{c}_{k-1}{c}_{n-k}$ }

$n$ -ta liczba Catalana to:} <wrongoption> $(\genfrac{}{}{0ex}{}{2n}{n})$ } <rightoption> $\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$ } <wrongoption> $(\genfrac{}{}{0ex}{}{1/2}{n}){(-4)}^n$ } <rightoption> $2(\genfrac{}{}{0ex}{}{1/2}{n+1}){(-4)}^n$ }

Niech $t_{10}$ będzie liczbą drzew o wysokości $10$ . Wtedy:} <rightoption> $t_{10}\le 2^{1023}$ } <rightoption> $t_{10}\ge 2^{512}$ } <wrongoption> $t_{10}\le 2^{10}$ } <wrongoption> $t_{10}\ge 2^9$ }

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> $\prod _{k=1}^{\mathrm{\infty }}\frac{1}{1-x^k}$ } <wrongoption> $\sum _{k=1}^{\mathrm{\infty }}\frac{1}{1-x^k}$ } <wrongoption> $\sum _{n=0}^{\mathrm{\infty }}\prod _{k=1}^{\mathrm{\infty }}\frac{1}{1-x^{nk}}$ } <rightoption> $\prod _{k=1}^{\mathrm{\infty }}\sum _{n=0}^{\mathrm{\infty }}{x}^{nk}$ }

Funkcja tworząca

$s_n\left(x\right)=\left[\begin{array}{c}n\\ 0\end{array}\right]+\left[\begin{array}{c}n\\ 1\end{array}\right]x+\left[\begin{array}{c}n\\ 2\end{array}\right]x^2+\left[\begin{array}{c}n\\ 3\end{array}\right]x^3+\dots ,$ 

dla cyklowych liczb Stirlinga $\left[\begin{array}{c}n\\ m\end{array}\right]$ , ma postać zwartą: } <rightoption> $s_n\left(x\right)=x^{\bar{n}}$ } <rightoption> $s_n\left(x\right)=\prod _{k=0}^{n-1}(x+k)$ } <wrongoption> $s_n\left(x\right)=x^{\underset{\_}{n}}$ } <wrongoption> $s_n\left(x\right)=1/\prod _{k=0}^{n-1}(1-kx)$ }

Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:} <wrongoption> $\left\{\begin{array}{c}n\\ k\end{array}\right\}=(n-1)\left\{\begin{array}{c}n-1\\ k\end{array}\right\}+\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\}$ , dla $0>k>n$ } <wrongoption> $\left\{\begin{array}{c}n+k\\ k\end{array}\right\}=\left\{\begin{array}{c}n+k-1\\ k\end{array}\right\}+k\left\{\begin{array}{c}n+k-1\\ k-1\end{array}\right\}$ , dla $n>1,k>0$ } <rightoption> $\left\{\begin{array}{c}n+k\\ k\end{array}\right\}=k\left\{\begin{array}{c}n+k-1\\ k\end{array}\right\}+\left\{\begin{array}{c}n+k-1\\ k-1\end{array}\right\}$ , dla $n>1,k>0$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

Niech $a_0=1$ , $a_1=0$ oraz $a_n=\frac{a_{n-2}}{n}$ . Funkcja tworząca $A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ ma postać zwartą:} <wrongoption> $A\left(x\right)=\sin x$ } <wrongoption> $A\left(x\right)=e^{x^2}$ } <rightoption> $A\left(x\right)=e^{x^2/2}$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

999999999999999999999999999999999999999

{article} {../makraT}

0mm

Uzupelnij tytul

Asymptotyka

10mm

Funkcja $n^2\lg n+\frac{n^2\sqrt{n}}{\lg n}$ jest:} <wrongoption> $\mathrm{\Theta }(n^2\lg n)$ <wrongoption> $O(n^2\lg n)$ <wrongoption> $\mathrm{\Theta }{n}^2\sqrt{n}$ <rightoption> $O(\frac{n^2\sqrt{n}}{\lg n})$

Funkcja $\frac{n^9}{{\lg }^{10}n}$ jest:} <wrongoption> $O(n^{\frac{9}{10}})$ <wrongoption> $O(n)$ <rightoption> $O(n^9)$ <rightoption> $\mathrm{\Omega }({\lg }^{10}n)$

Dla $f(n)=2^{\lg n+1}$ oraz $g(n)=\lg 2n-1$ zachodzi:} <wrongoption> $f(x)=\omega (g(x))$ <rightoption> $f(x)=\mathrm{\Omega }(g(x))$ <rightoption> $f(x)=\mathrm{\Theta }(g(x))$ <rightoption> $f(x)=O(g(x))$ <wrongoption> $f(x)=o(g(x))$

Dowolny wielomian $k$-tego stopnia jest:} <rightoption> $\mathrm{\Omega }(n^k)$ <rightoption> $\mathrm{\Theta }(n^k)$ <rightoption> $O(n^k)$ <rightoption> $o(n^{k+\epsilon })$ dla dowolnego $\epsilon >0$

Dla $f(n)=\frac{\lg n}{n}$ oraz $g(n)=\frac{1}{\sqrt{n}}$ zachodzi:} <wrongoption> $f(x)=\omega (g(x))$ <wrongoption> $f(x)=\mathrm{\Omega }(g(x))$ <wrongoption> $f(x)=\mathrm{\Theta }(g(x))$ <rightoption> $f(x)=O(g(x))$ <rightoption> $f(x)=o(g(x))$

Dla $f(x)=x^2$ oraz $g(x)=x^2+\sin x$ zachodzi:} <rightoption> $f(x)=\mathrm{\Omega }(g(x))$ <rightoption> $f(x)=\mathrm{\Theta }(g(x))$ <rightoption> $f(x)=O(g(x))$ <wrongoption> żadne z pozostałych

Dla $T(n)=9T(\frac{n}{3})+\frac{n^2}{\lg n}$:} <wrongoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2)$ <wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2\lg n)$ <wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(\frac{n^2}{\lg n})$ <rightoption> żadne z pozostałych

Dla $T(n)=25T(\frac{n}{4})+\frac{n^2}{\lg n}$} <rightoption> możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^{{\lg }_{4}25})$ <wrongoption> możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(n^2)$ <wrongoption> możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T(n)=\mathrm{\Theta }(\frac{n^2}{\lg n})$ <wrongoption> żadne z pozostałych

Funkcja spełniająca zależność $T(n)=T(\frac{n}{2})+1$ jest:} <rightoption> $\mathrm{\Theta }(\lg n)$ <rightoption> $\mathrm{\Theta }(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\in \mathbb{\mathbb{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\in \mathbb{\mathbb{N}}}$, gdzie $a,b\in \mathbb{\mathbb{N}}$, 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 $p^2+2$ jako ostatnią skreśli:} <wrongoption> $p$ <rightoption> $p^2$ <wrongoption> $p^2+1$ <wrongoption> $p^2+2$

Jeśli $a|bc$ oraz NWD $(a,b)=d$, to} <rightoption> $\frac{a}{d}|c$ <rightoption> $a|cd$ <rightoption> $\frac{a}{d}\perp b$ <rightoption> $\frac{a}{d}\perp \frac{b}{d}$

Liczb pierwszych postaci $n^2-1$, gdzie $n\in \mathbb{\mathbb{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)\perp \frac{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\perp 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\perp n$ oraz $acd{\equiv }_{cn}bcd$, to} <rightoption> $a{\equiv }_{n}b$ <rightoption> $ad{\equiv }_{n}bd$ <rightoption> $acd{\equiv }_{n}bcd$ <wrongoption> $ac{\equiv }_{nd}bc$

Równanie $7x{\equiv }_{91}4$} <wrongoption> nie ma rozwiązania <wrongoption> ma skończenie wiele rozwiązań <wrongoption> zbiór wszystkich jego rozwiązań jest postaci $\{13n+c:n\in N\}$ dla pewnego $c\in \mathbb{\mathbb{N}}$ <rightoption> zbiór wszystkich rozwiązań jest postaci $\{91n+c:n\in \mathbb{\mathbb{N}}\}$ dla pewnego $c\in \mathbb{\mathbb{N}}$

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\cdot n$, gdzie $n\in \mathbb{\mathbb{Z}}$ <rightoption> wszystkie jego rozwiązania są postaci $2007n+2006$

Dla $a<b$ warunek $\phi (a)⩽\phi (b)$ zachodzi jeśli} <wrongoption> $a⩽b$ <rightoption> $a|b$ <wrongoption> $a\perp b$ <rightoption> $a⩽b$ i $b$ jest pierwsza

$16^{49}$ { mod} $25$ wynosi:} <wrongoption> $1$ <wrongoption> $7$ <wrongoption> $14$ <rightoption> $21$

$14^{111}$ { mod} $15$ wynosi:} <wrongoption> $1$ <wrongoption> $3$ <wrongoption> $12$ <rightoption> $14$

Wiedząc, że $2006=2\cdot 17\cdot 59$ oblicz $\mu (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> $2^{n^2}$ <rightoption> $2^{n^2-n}$ <wrongoption> $2^{2^n}$ <wrongoption> $2^{2^n-n}$ <wrongoption> $2^{(\genfrac{}{}{0ex}{}{n}{2})}$

Różnych grafów nieskierowanych bez cykli jednoelementowych w zbiorze $n$-elementowym jest:} <wrongoption> $2^{n^2}$ <wrongoption> $2^{n^2-n}$ <wrongoption> $2^{2^n}$ <wrongoption> $2^{2^n-n}$ <rightoption> $2^{(\genfrac{}{}{0ex}{}{n}{2})}$

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> $\frac{100\cdot 99}{3}$

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

<rightoption> $1000\cdot 1000$
<wrongoption> $1000!$
<wrongoption> $(\genfrac{}{}{0ex}{}{1000}{2})$
<wrongoption> $(\genfrac{}{}{0ex}{}{1000}{50})$
<wrongoption> $(\genfrac{}{}{0ex}{}{2000}{1000})$

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 $K_{50,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 $K_{25,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 ${\mathbf{𝐆}}_1=(V,E_1)$ i ${\mathbf{𝐆}}_2=(V,E_2)$ są grafami niespójnymi o tym samym zbiorze wierzchołków $V$ , to:} <rightoption>graf ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_1$ może być spójny} <wrongoption>graf ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_1$ jest spójny} <rightoption>graf ${\mathbf{𝐆}}_1\cap {\mathbf{𝐆}}_1$ może nie być spójny} <rightoption>graf ${\mathbf{𝐆}}_1\cap {\mathbf{𝐆}}_1$ nie jest spójny}

Graf ${\mathbf{𝐏}}_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 ${\mathbf{𝐏}}_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 $\mathbf{𝐓}$ był drzewem potrzeba i wystarcza, by:} <wrongoption> $\mathbf{𝐓}$ nie zawierał cykli} <rightoption> $\mathbf{𝐓}$ był spójny i miał $\left|V\right|-1$ krawędzi} <rightoption>dowolne dwa wierzchołki grafu $\mathbf{𝐓}$ były połączone dokładnie jedną drogą} <wrongoption>dowolne dwa wierzchołki grafu $\mathbf{𝐓}$ 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 $\mathbf{𝐆}$ jest eulerowski, to:} <wrongoption>graf $\mathbf{𝐆}$ jest hamiltonowski} <rightoption>każdy wierzchołek w grafie $\mathbf{𝐆}$ ma parzysty stopień} <rightoption>graf $\mathbf{𝐆}$ 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 $\mathbf{𝐆}$ jest hamiltonowski, to po usunięciu cyklu Hamiltona graf $\mathbf{𝐆}$ 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ą $\mathrm{deg}v+\mathrm{deg}w\ge 100$ jest hamiltonowski} <wrongoption>w którym dowolne dwa sąsiednie wierzchołki $v$ i $w$ spełniają $\mathrm{deg}v+\mathrm{deg}w\ge 100$ jest hamiltonowski}

Który z warunków wystarcza na to, by w grafie dwudzielnym $\mathbf{𝐆}=(V_1\cup V_2,E)$ istniało pełne skojarzenie $V_1$ z $V_2$ ?} <rightoption>graf $\mathbf{𝐆}$ jest hamiltonowski} <wrongoption>graf $\mathbf{𝐆}$ jest eulerowski} <wrongoption>w grafie $\mathbf{𝐆}$ każdy wierzchołek z $V_1$ ma co najmniej dwu sąsiadów} <rightoption>dowolny zbiór niezależny w ma co najwyżej $\left|V_2\right|$ 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 ${\mathbf{𝐆}}^{*}$ będzie grafem geometrycznie dualnym do grafu płaskiego $\mathbf{𝐆}$ . Podzbiór $C$ zbioru krawędzi grafu $\mathbf{𝐆}$ jest cyklem w grafie $\mathbf{𝐆}$ 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 ${\mathbf{𝐆}}^{*}$ } <rightoption>jest rozcięciem grafu ${\mathbf{𝐆}}^{*}$ }

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> $\chi \left(\mathbf{𝐆}\right)\le {\chi }_s\left(\mathbf{𝐆}\right)+1$ } <wrongoption> $\chi \left(\mathbf{𝐆}\right)\le {\chi }_s\left(\mathbf{𝐆}\right)$ } <wrongoption> $\chi \left(\mathbf{𝐆}\right)\ge {\chi }_s\left(\mathbf{𝐆}\right)+1$ } <wrongoption> $\chi \left(\mathbf{𝐆}\right)={\chi }_s\left(\mathbf{𝐆}\right)$ }

Pełny graf dwudzielny $K_{50,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 $m_{ij}$ oznacza liczbę skierowanych marszrut, nie dłuższych niż $n-1$ , z wierzchołka $v_i$ do $v_j$ w grafie skierowanym $\mathbf{𝐆}=(\{v_1,\dots ,v_n\},E)$ , a $M$ niech będzie macierzą $⟨m_{ij}⟩$ . 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> $m_{ij}>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 $\mathbf{𝐆}$ 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 $\mathbf{𝐆}$ będzie grafem o $10$ wierzchołkach przedstawionym na Rysunku Uzupelnic test alg|, a macierz $M$ , o rozmiarach $9\times 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

$e_0,e_2,e_3,e_6,e_9,e_{12},e_{13},e_{14},e_{15}$ . 

[!ht]

{test_alg} {Graf $\mathbf{𝐆}$ . [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 $\mathbf{𝐆}$ był niezerowy, wystarcza by:} <rightoption>graf $\mathbf{𝐆}$ posiadał cykl Hamiltona} <wrongoption>graf $\mathbf{𝐆}$ posiadał cykl Eulera} <wrongoption>graf $\mathbf{𝐆}$ był spójny} <rightoption>graf $\mathbf{𝐆}$ 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> ${\lambda }_{max}\left(\mathbf{𝐆}\right)=\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ } <rightoption> $\left|{\lambda }_{max}\left(\mathbf{𝐆}\right)\right|\le \mathrm{\Delta }\left(\mathbf{𝐆}\right)$ } <rightoption> ${\lambda }_{max}\left(\mathbf{𝐆}\right)=\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ wtedy i tylko wtedy, gdy któraś spójna składowa grafu $\mathbf{𝐆}$ jest grafem regularnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ } <rightoption> $-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ 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 $\mathbf{𝐆}$ jest regularnym grafem dwudzielnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ }

W grafie regularnym $\mathbf{𝐆}$ o $10$ wierzchołkach stopnia $4$ oraz wartościach własnych ${\lambda }_{min}\left(\mathbf{𝐆}\right)\approx -2,73205$ i ${\lambda }_{max}\left(\mathbf{𝐆}\right)=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ą $\chi \left(\mathbf{𝐆}\right)$ z wartościami własnymi grafu regularnego $\mathbf{𝐆}$ :} <rightoption> $\chi \left(\mathbf{𝐆}\right)\ge 1-\frac{{\lambda }_{max}\left(\mathbf{𝐆}\right)}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}$ } <wrongoption> $\chi \left(\mathbf{𝐆}\right)=1-\frac{{\lambda }_{max}\left(\mathbf{𝐆}\right)}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}$ } <rightoption> $\chi \left(\mathbf{𝐆}\right)\le {\lambda }_{max}\left(\mathbf{𝐆}\right)+1$ } <wrongoption> $\chi \left(\mathbf{𝐆}\right)\ge {\lambda }_{max}\left(\mathbf{𝐆}\right)$ }