Matematyka dyskretna 1/Test 12: Grafy

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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


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


Zaznacz zdania prawdziwe:

W każdym grafie prostym relacja musi być zwrotna.

W grafie nieskierowanym relacja 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:


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


W pełnym grafie -elementowym:

każde drzewo rozpinające ma krawędzi

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

każde drzewo rozpinające ma krawędzi

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

nie ma drzew rozpinających


W pełnym grafie dwudzielnym :

każde drzewo rozpinające ma krawędzi

każde drzewo rozpinające ma krawędzi

każde drzewo rozpinające ma krawędzi

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

nie ma drzew rozpinających


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

jakiś las rozpinający ma krawędzi

jakiś las rozpinający ma krawędzi

jakiś las rozpinający ma krawędzi

jakiś las rozpinający ma krawędzi

może nie być lasu rozpinającego


Pełny graf -elementowy:

jest grafem Hamiltonowskim

jest grafem Eulerowskim

jest spójny

jest dwudzielny

jest stukolorowalny


Pełny graf dwudzielny :

jest grafem Hamiltonowskim

jest grafem Eulerowskim

zawiera cykl wierzchołkach jako podgraf indukowany

zawiera cykl wierzchołkach jako podgraf indukowany

jest trójkolorowalny


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

ma krawędzi

ma krawędzi

ma krawędzi

nie istnieje


Jeśli i są grafami niespójnymi o tym samym zbiorze wierzchołków , to:

graf może być spójny

graf jest spójny

graf może nie być spójny

graf nie jest spójny


Graf to graf, który składa się jedynie ze ścieżki odwiedzającej wierzchołki, czyli oraz . W grafie spójnym, w którym nie ma podgrafu indukowanego izomorficznego do  :

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ę


Zaznacz zdania prawdziwe:

Każdy graf pusty jest grafem dwudzielnym.

Każdy graf pełny jest grafem dwudzielnym.

Graf jest grafem dwudzielnym.

Graf jest grafem dwudzielnym.


Zaznacz zdania prawdziwe:

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

Graf jest grafem planarnym.

Graf jest grafem planarnym.

Każdy graf dwudzielny jest grafem planarnym.


Graf o wierzchołkach:

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

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

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

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


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

nie zawierał cykli

był spójny i miał 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