Test GR4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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”