Matematyka dyskretna 1/Test 12: Grafy

From Studia Informatyczne

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

\displaystyle 2^{n^2}

\displaystyle 2^{n^2-n}

\displaystyle 2^{2^n}

\displaystyle 2^{2^n-n}

\displaystyle 2^{n \choose 2}


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

\displaystyle 2^{n^2}

\displaystyle 2^{n^2-n}

\displaystyle 2^{2^n}

\displaystyle 2^{2^n-n}

\displaystyle 2^{n \choose 2}


Zaznacz zdania prawdziwe:

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

W grafie nieskierowanym \displaystyle G= \left( V,E \right) relacja \displaystyle 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:

\displaystyle 99

\displaystyle 97

\displaystyle 98

\displaystyle 100

\displaystyle \frac{100 \cdot 99}{3}


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

\displaystyle 1000 \cdot 1000

\displaystyle 1000!

\displaystyle 1000 \choose 2

\displaystyle 1000 \choose 50

\displaystyle 2000 \choose 1000


W pełnym grafie \displaystyle 100-elementowym:

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

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

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

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

nie ma drzew rozpinających


W pełnym grafie dwudzielnym \displaystyle K_{50,50}:

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

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

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

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

nie ma drzew rozpinających


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

jakiś las rozpinający ma \displaystyle 100 krawędzi

jakiś las rozpinający ma \displaystyle 99 krawędzi

jakiś las rozpinający ma \displaystyle 98 krawędzi

jakiś las rozpinający ma \displaystyle 97 krawędzi

może nie być lasu rozpinającego


Pełny graf \displaystyle 100-elementowy:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest spójny

jest dwudzielny

jest stukolorowalny


Pełny graf dwudzielny \displaystyle K_{25,25}:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

zawiera cykl \displaystyle 4 wierzchołkach jako podgraf indukowany

zawiera cykl \displaystyle 6 wierzchołkach jako podgraf indukowany

jest trójkolorowalny


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

ma \displaystyle 202505 krawędzi

ma \displaystyle 2106 krawędzi

ma \displaystyle 405010 krawędzi

nie istnieje


Jeśli \displaystyle \mathbf{G}_1=\left( V,E_1 \right) i \displaystyle \mathbf{G}_2=\left( V,E_2 \right) są grafami niespójnymi o tym samym zbiorze wierzchołków \displaystyle V , to:

graf \displaystyle \mathbf{G}_1\cup\mathbf{G}_1 może być spójny

graf \displaystyle \mathbf{G}_1\cup\mathbf{G}_1 jest spójny

graf \displaystyle \mathbf{G}_1\cap\mathbf{G}_1 może nie być spójny

graf \displaystyle \mathbf{G}_1\cap\mathbf{G}_1 nie jest spójny


Graf \displaystyle \mathbf{P}_4 to graf, który składa się jedynie ze ścieżki odwiedzającej \displaystyle 4 wierzchołki, czyli \displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace oraz \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 \displaystyle \mathbf{P}_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ę \displaystyle \mathcal{K}_{3}


Zaznacz zdania prawdziwe:

Każdy graf pusty jest grafem dwudzielnym.

Każdy graf pełny jest grafem dwudzielnym.

Graf \displaystyle \mathcal{K}_{3} jest grafem dwudzielnym.

Graf \displaystyle \mathcal{K}_{2} jest grafem dwudzielnym.


Zaznacz zdania prawdziwe:

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

Graf \displaystyle \mathcal{K}_{4} jest grafem planarnym.

Graf \displaystyle \mathcal{K}_{5} jest grafem planarnym.

Każdy graf dwudzielny jest grafem planarnym.


Graf o \displaystyle 100 wierzchołkach:

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

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

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

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


Na to by graf \displaystyle \mathbf{T} był drzewem potrzeba i wystarcza, by:

\displaystyle \mathbf{T} nie zawierał cykli

\displaystyle \mathbf{T} był spójny i miał \displaystyle \left\vert V \right\vert-1 krawędzi

dowolne dwa wierzchołki grafu \displaystyle \mathbf{T} były połączone dokładnie jedną drogą

dowolne dwa wierzchołki grafu \displaystyle \mathbf{T} leżały na dokładnie jednym cyklu