Test GR4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

8888888888888888888888888888888888888888888888

999999999999999999999999999999999999999

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