Matematyka dyskretna 1/Test 12: Grafy: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu – „ </math>” na „</math>”
 
(Nie pokazano 6 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>\displaystyle n</math>-elementowym jest:
<quiz>Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze <math>n</math>-elementowym jest:
<wrongoption><math>\displaystyle 2^{n^2}</math></wrongoption>
<wrongoption><math>2^{n^2}</math></wrongoption>
<rightoption><math>\displaystyle 2^{n^2-n}</math></rightoption>
<rightoption><math>2^{n^2-n}</math></rightoption>
<wrongoption><math>\displaystyle 2^{2^n}</math></wrongoption>
<wrongoption><math>2^{2^n}</math></wrongoption>
<wrongoption><math>\displaystyle 2^{2^n-n}</math></wrongoption>
<wrongoption><math>2^{2^n-n}</math></wrongoption>
<wrongoption><math>\displaystyle 2^{n \choose 2}</math></wrongoption>
<wrongoption><math>2^{n \choose 2}</math></wrongoption>
</quiz>
</quiz>


<quiz>Różnych grafów nieskierowanych bez cykli jednoelementowych  w zbiorze <math>\displaystyle n</math>-elementowym jest:
 
<wrongoption><math>\displaystyle 2^{n^2}</math></wrongoption>
<quiz>Różnych grafów nieskierowanych bez cykli jednoelementowych  w zbiorze <math>n</math>-elementowym jest:
<wrongoption><math>\displaystyle 2^{n^2-n}</math></wrongoption>
<wrongoption><math>2^{n^2}</math></wrongoption>
<wrongoption><math>\displaystyle 2^{2^n}</math></wrongoption>
<wrongoption><math>2^{n^2-n}</math></wrongoption>
<wrongoption><math>\displaystyle 2^{2^n-n}</math></wrongoption>
<wrongoption><math>2^{2^n}</math></wrongoption>
<rightoption><math>\displaystyle 2^{n \choose 2}</math></rightoption>
<wrongoption><math>2^{2^n-n}</math></wrongoption>
<rightoption><math>2^{n \choose 2}</math></rightoption>
</quiz>
</quiz>


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


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


<quiz>Jaka jest najmniejsza liczba krawędzi w grafie
<quiz>Jaka jest najmniejsza liczba krawędzi w grafie
nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:
nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:
<wrongoption> <math>\displaystyle 99</math></wrongoption>
<wrongoption> <math>99</math></wrongoption>
<rightoption> <math>\displaystyle 97</math></rightoption>
<rightoption> <math>97</math></rightoption>
<wrongoption> <math>\displaystyle 98</math></wrongoption>
<wrongoption> <math>98</math></wrongoption>
<wrongoption> <math>\displaystyle 100</math></wrongoption>
<wrongoption> <math>100</math></wrongoption>
<wrongoption> <math>\displaystyle \frac{100 \cdot 99}{3}</math></wrongoption>
<wrongoption> <math>\frac{100 \cdot 99}{3}</math></wrongoption>
</quiz>
</quiz>


<quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>\displaystyle K_{1000,1000}</math>:
 
<rightoption> <math>\displaystyle 1000 \cdot 1000</math></rightoption>
<quiz>Ile jest krawędzi w pełnym grafie dwudzielnym <math>K_{1000,1000}</math>:
<wrongoption> <math>\displaystyle 1000!</math></wrongoption>
<rightoption> <math>1000 \cdot 1000</math></rightoption>
<wrongoption> <math>\displaystyle 1000 \choose 2</math></wrongoption>
<wrongoption> <math>1000!</math></wrongoption>
<wrongoption> <math>\displaystyle 1000 \choose 50</math></wrongoption>
<wrongoption> <math>1000 \choose 2</math></wrongoption>
<wrongoption> <math>\displaystyle 2000 \choose 1000</math></wrongoption>
<wrongoption> <math>1000 \choose 50</math></wrongoption>
<wrongoption> <math>2000 \choose 1000</math></wrongoption>
</quiz>
</quiz>


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


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


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


<quiz>Pełny graf <math>\displaystyle 100</math>-elementowy:
 
<quiz>Pełny graf <math>100</math>-elementowy:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<rightoption> jest grafem Hamiltonowskim</rightoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<wrongoption> jest spójny</wrongoption>
<wrongoption> jest spójny</wrongoption>
<wrongoption> jest dwudzielny</wrongoption>
<rightoption> jest dwudzielny</rightoption>
<rightoption> jest stukolorowalny</rightoption>
<rightoption> jest stukolorowalny</rightoption>
</quiz>
</quiz>


<quiz>Pełny graf dwudzielny <math>\displaystyle K_{25,25}</math>:
 
<quiz>Pełny graf dwudzielny <math>K_{25,25}</math>:
<rightoption> jest grafem Hamiltonowskim</rightoption>
<rightoption> jest grafem Hamiltonowskim</rightoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<wrongoption> jest grafem Eulerowskim</wrongoption>
<rightoption> zawiera cykl <math>\displaystyle 4</math> wierzchołkach jako podgraf indukowany</rightoption>
<rightoption> zawiera cykl <math>4</math> wierzchołkach jako podgraf indukowany</rightoption>
<wrongoption> zawiera cykl <math>\displaystyle 6</math> wierzchołkach jako podgraf indukowany </wrongoption>
<wrongoption> zawiera cykl <math>6</math> wierzchołkach jako podgraf indukowany </wrongoption>
<rightoption> jest trójkolorowalny</rightoption>
<rightoption> jest trójkolorowalny</rightoption>
</quiz>
</quiz>


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


<quiz>Jeśli  <math>\displaystyle \mathbf{G}_1=\left( V,E_1 \right) </math>  i  <math>\displaystyle \mathbf{G}_2=\left( V,E_2 \right) </math>   
 
są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>\displaystyle V </math> , to:
<quiz>Jeśli  <math>\mathbf{G}_1=\left( V,E_1 \right)</math>  i  <math>\mathbf{G}_2=\left( V,E_2 \right)</math>   
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  może być spójny</rightoption>
są grafami niespójnymi o tym samym zbiorze wierzchołków  <math>V</math> , to:
<wrongoption>graf  <math>\displaystyle \mathbf{G}_1\cup\mathbf{G}_1 </math>  jest spójny</wrongoption>
<rightoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  może być spójny</rightoption>
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  może nie być spójny</rightoption>
<wrongoption>graf  <math>\mathbf{G}_1\cup\mathbf{G}_1</math>  jest spójny</wrongoption>
<rightoption>graf  <math>\displaystyle \mathbf{G}_1\cap\mathbf{G}_1 </math>  nie jest spójny</rightoption>
<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  może nie być spójny</rightoption>
<rightoption>graf  <math>\mathbf{G}_1\cap\mathbf{G}_1</math>  nie jest spójny</rightoption>
</quiz>  
</quiz>  


<quiz>Graf  <math>\displaystyle \mathbf{P}_4 </math>  to graf, który składa się jedynie ze ścieżki  
 
odwiedzającej  <math>\displaystyle 4 </math>  wierzchołki,  
<quiz>Graf  <math>\mathbf{P}_4</math>  to graf, który składa się jedynie ze ścieżki  
czyli  <math>\displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace </math>   
odwiedzającej  <math>4</math>  wierzchołki,  
oraz  <math>\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 </math> .  
czyli  <math>\mathsf{ V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace</math>   
oraz  <math>\mathsf{ 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</math> .  
W grafie spójnym, w którym nie ma  
W grafie spójnym, w którym nie ma  
podgrafu indukowanego izomorficznego do  <math>\displaystyle \mathbf{P}_4 </math> :
podgrafu indukowanego izomorficznego do  <math>\mathbf{P}_4</math> :
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy</rightoption>
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy</rightoption>
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa</rightoption>
<rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa</rightoption>
<wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden</wrongoption>
<wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden</wrongoption>
<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\displaystyle \mathcal{K}_{3} </math></wrongoption>
<wrongoption>każde trzy wierzchołki tworzą klikę  <math>\mathcal{K}_{3}</math></wrongoption>
</quiz>  
</quiz>  


<quiz>Zaznacz zdania prawdziwe:
<quiz>Zaznacz zdania prawdziwe:
<rightoption>Każdy graf pusty jest grafem dwudzielnym.</rightoption>
<rightoption>Każdy graf pusty jest grafem dwudzielnym.</rightoption>
<wrongoption>Każdy graf pełny jest grafem dwudzielnym.</wrongoption>
<wrongoption>Każdy graf pełny jest grafem dwudzielnym.</wrongoption>
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{3} </math>  jest grafem dwudzielnym.</wrongoption>
<wrongoption>Graf  <math>\mathcal{K}_{3}</math>  jest grafem dwudzielnym.</wrongoption>
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{2} </math>  jest grafem dwudzielnym.</rightoption>
<rightoption>Graf  <math>\mathcal{K}_{2}</math>  jest grafem dwudzielnym.</rightoption>
</quiz>  
</quiz>  


<quiz>Zaznacz zdania prawdziwe:
<quiz>Zaznacz zdania prawdziwe:
<rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.</rightoption>
<rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.</rightoption>
<rightoption>Graf  <math>\displaystyle \mathcal{K}_{4} </math>  jest grafem planarnym.</rightoption>
<rightoption>Graf  <math>\mathcal{K}_{4}</math>  jest grafem planarnym.</rightoption>
<wrongoption>Graf  <math>\displaystyle \mathcal{K}_{5} </math>  jest grafem planarnym.</wrongoption>
<wrongoption>Graf  <math>\mathcal{K}_{5}</math>  jest grafem planarnym.</wrongoption>
<wrongoption>Każdy graf dwudzielny jest grafem planarnym.</wrongoption>
<wrongoption>Każdy graf dwudzielny jest grafem planarnym.</wrongoption>
</quiz>  
</quiz>  


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


<quiz>Na to by graf  <math>\displaystyle \mathbf{T} </math>  był drzewem potrzeba i wystarcza, by:
 
<wrongoption> <math>\displaystyle \mathbf{T} </math>  nie zawierał cykli</wrongoption>
<quiz>Na to by graf  <math>\mathbf{T}</math>  był drzewem potrzeba i wystarcza, by:
<rightoption> <math>\displaystyle \mathbf{T} </math>  był spójny i miał  <math>\displaystyle \left\vert V \right\vert-1 </math>  krawędzi</rightoption>
<wrongoption> <math>\mathbf{T}</math>  nie zawierał cykli</wrongoption>
<rightoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  były połączone dokładnie jedną drogą</rightoption>
<rightoption> <math>\mathbf{T}</math>  był spójny i miał  <math>\left\vert V \right\vert-1</math>  krawędzi</rightoption>
<wrongoption>dowolne dwa wierzchołki grafu  <math>\displaystyle \mathbf{T} </math>  leżały na dokładnie jednym cyklu</wrongoption>
<rightoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  były połączone dokładnie jedną drogą</rightoption>
<wrongoption>dowolne dwa wierzchołki grafu  <math>\mathbf{T}</math>  leżały na dokładnie jednym cyklu</wrongoption>
</quiz>
</quiz>

Aktualna wersja na dzień 10:04, 5 wrz 2023

Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze n-elementowym jest:

2n2

2n2−n

22n

22n−n

2(n2)


Różnych grafów nieskierowanych bez cykli jednoelementowych w zbiorze n-elementowym jest:

2n2

2n2−n

22n

22n−n

2(n2)


Zaznacz zdania prawdziwe:

W każdym grafie prostym G=(V;E) relacja E musi być zwrotna.

W grafie nieskierowanym G=(V,E) relacja E jest symetryczna.

Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków.

W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.


Zaznacz zdania prawdziwe dla grafów nieskierowanych:

podgraf indukowany grafu pełnego jest grafem pełnym

każdy graf jest podgrafem jakiegoś grafu pełnego

każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego

graf pełny ma zawsze parzystą liczbę krawędzi

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:

99

97

98

100

100⋅993


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

1000⋅1000

1000!

(10002)

(100050)

(20001000)


W pełnym grafie 100-elementowym:

każde drzewo rozpinające ma 100 krawędzi

dokładnie jedno drzewo rozpinające ma 100 krawędzi

każde drzewo rozpinające ma 99 krawędzi

dokładnie jedno drzewo rozpinające ma 99 krawędzi

nie ma drzew rozpinających


W pełnym grafie dwudzielnym K50,50:

każde drzewo rozpinające ma 50 krawędzi

każde drzewo rozpinające ma 100 krawędzi

każde drzewo rozpinające ma 99 krawędzi

dokładnie jedno drzewo rozpinające ma 99 krawędzi

nie ma drzew rozpinających


W 100 elementowym grafie o trzech składowych spójnych:

jakiś las rozpinający ma 100 krawędzi

jakiś las rozpinający ma 99 krawędzi

jakiś las rozpinający ma 98 krawędzi

jakiś las rozpinający ma 97 krawędzi

może nie być lasu rozpinającego


Pełny graf 100-elementowy:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest spójny

jest dwudzielny

jest stukolorowalny


Pełny graf dwudzielny K25,25:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

zawiera cykl 4 wierzchołkach jako podgraf indukowany

zawiera cykl 6 wierzchołkach jako podgraf indukowany

jest trójkolorowalny


Graf o 2005 wierzchołkach, z których każdy ma stopień 101 :

ma 202505 krawędzi

ma 2106 krawędzi

ma 405010 krawędzi

nie istnieje


Jeśli 𝐆1=(V,E1) i 𝐆2=(V,E2) są grafami niespójnymi o tym samym zbiorze wierzchołków V , to:

graf 𝐆1∪𝐆1 może być spójny

graf 𝐆1∪𝐆1 jest spójny

graf 𝐆1∩𝐆1 może nie być spójny

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 V(𝐏4)={a,b,c,d} oraz E(𝐏4)={{a,b},{b,c},{c,d}} . W grafie spójnym, w którym nie ma podgrafu indukowanego izomorficznego do 𝐏4 :

dowolne dwa punkty leżą w odległości co najwyżej trzy

dowolne dwa punkty leżą w odległości co najwyżej dwa

dowolne dwa punkty leżą w odległości co najwyżej jeden

każde trzy wierzchołki tworzą klikę 𝒦3


Zaznacz zdania prawdziwe:

Każdy graf pusty jest grafem dwudzielnym.

Każdy graf pełny jest grafem dwudzielnym.

Graf 𝒦3 jest grafem dwudzielnym.

Graf 𝒦2 jest grafem dwudzielnym.


Zaznacz zdania prawdziwe:

Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.

Graf 𝒦4 jest grafem planarnym.

Graf 𝒦5 jest grafem planarnym.

Każdy graf dwudzielny jest grafem planarnym.


Graf o 100 wierzchołkach:

jeśli ma 99 krawędzi, to jest drzewem.

jeśli ma 100 krawędzi, to jest drzewem.

jeśli ma 4851 krawędzi, to jest spójny.

jeśli ma 4852 krawędzi, to jest spójny.


Na to by graf 𝐓 był drzewem potrzeba i wystarcza, by:

𝐓 nie zawierał cykli

𝐓 był spójny i miał |V|−1 krawędzi

dowolne dwa wierzchołki grafu 𝐓 były połączone dokładnie jedną drogą

dowolne dwa wierzchołki grafu 𝐓 leżały na dokładnie jednym cyklu

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Test_12:_Grafy&oldid=80826”