1
MATEMATYKA DYSKRETNA - KOLOKWIUM 2 GRUPA A
RACHUNKI+KRÓTKIE WYJAŚNIENIA! NA TEJ KARTCE!
KAŻDA DODATKOWA KARTKA TO MINUS 1 PUNKT!
Imię i nazwisko ........................... ......... Nr indeksu ..............
1. (3p.) Znajdz
drzewo o kodzie Prufera 2153
2. (2p.) Korzystając z algorytmu Prima znajdz
minimalne drzewo spi-
nające. Z opisu (rysunku) musi być jasne, w jakiej kolejności w drzewie
pojawiały się kolejne wierzchołki.
3. (3p). Ile jest grafów symetrycznych, bez pętli i krawędzi wielokrotnych,
o 6 wierzchołkach i 10 krawędziach? Grafy izomorficzne traktujemy jako
różne.
4. (2p.) Ile co najmniej wyrazów niezerowych ma macierz sąsiedztwa
grafu spójnego o n wierzchołkach?
2
5. (3p.) Określ wartość logiczną zdań (Prawda- Fałsz) Drzewo oznacza
tu zawsze drzewo o więcej niż jednym wierzchołku.
a) każde drzewo T jest grafem dwudzielnym;
b) liczba chromatyczna każdego drzewa T (kolorowanie wierzchołków)
wynosi 2;
c) nie każde drzewo T jest grafem planarnym;
d) indeks chromatyczny (kolorowanie krawędzi) każdego drzewa T wy-
nosi 2;
Punkt za każdą poprawną odpowiedz
POWYŻEJ pierwszej!
6. (2p.) Wyjaśnij, dla jakich n graf Kn,n jest: a) eulerowski, b) hamilto-
nowski?
7. (3p.) Korzystając ze wzoru Eulera wykaż, ze graf kostki czterowymia-
rowej (czterowymiarowy odpowiednik sześcianu) nie jest planarny.
3
MATEMATYKA DYSKRETNA - KOLOKWIUM 2 GRUPA B
RACHUNKI+KRÓTKIE WYJAŚNIENIA! NA TEJ KARTCE!
KAŻDA DODATKOWA KARTKA TO MINUS 1 PUNKT!
Imię i nazwisko ........................... ......... Nr indeksu ..............
1. (3p.) Określ wartość logiczną zdań (Prawda- Fałsz). Drzewo oznacza
tu zawsze drzewo o więcej niż jednym wierzchołku.
a) każde drzewo T ma wierzchołki stopnia 1;
b) indeks chromatyczny (kolorowanie krawędzi) każdego drzewa T wy-
nosi 2;
c) liczba chromatyczna każdego drzewa T (kolorowanie wierzchołków)
wynosi 2;
d) żadne drzewo nie jest grafem eulerowskim;
Punkt za każdą poprawną odpowiedz
POWYŻEJ pierwszej!
2. (2p.) Wyjaśnij, dla jakich n graf Kn jest: a) eulerowski, b) hamilto-
nowski?
3. (2p.) Korzystając z algorytmu Kruskala znajdz
minimalne drzewo
spinające. Z opisu (rysunku) musi być jasne, w jakiej kolejności w drzewie
pojawiały się kolejne krawędzie.
4
4. (3p). Ile jest grafów symetrycznych, bez pętli i krawędzi wielokrotnych,
o 7 wierzchołkach? Grafy izomorficzne traktujemy jako różne.
5. (2p.) Ile co najwyżej wyrazów niezerowych ma macierz sąsiedztwa
grafu acyklicznego o n wierzchołkach?
6. (3p.) Znajdz
drzewo o kodzie Prufera 4542
7. (3p.) Korzystając ze wzoru Eulera wykaż, że wielościan foremny, któ-
rego każda ściana jest pięciokątem, a w wierzchołku stykają się trzy
pięciokąty, musi być dwunastościanem.
5
MATEMATYKA DYSKRETNA - KOLOKWIUM 2 GRUPA C
RACHUNKI+KRÓTKIE WYJAŚNIENIA! NA TEJ KARTCE!
KAŻDA DODATKOWA KARTKA TO MINUS 1 PUNKT!
Imię i nazwisko ........................... ......... Nr indeksu ..............
1. (3p.) Znajdz
drzewo nietykietowane o kodzie 000110011101.
2. (2p.) Korzystając z algorytmu Prima znajdz
minimalne drzewo spi-
nające. Z opisu (rysunku) musi być jasne, w jakiej kolejności w drzewie
pojawiały się kolejne wierzchołki.
3. (3p). Przypomnijmy, że turniej to graf pełny, w którym każdej krawę-
dzi przypisany jest zwrot w jedna albo drugą stronę. Ile jest turniejów
na zbiorze {1, 2, ...., 6}?
4. (2p.) Ile co najmniej wyrazów niezerowych ma macierz incydencji
grafu spójnego o n wierzchołkach?
6
5. (3p.) Określ wartość logiczną zdań (Prawda- Fałsz). Drzewo oznacza
tu zawsze drzewo o więcej niż jednym wierzchołku.
a) każdy graf dwudzielny jest drzewem;
b) nie każde drzewo T jest grafem dwudzielnym;
c) liczba chromatyczna (kolorowanie wierzchołków) każdego grafu Cn
wynosi 2;
d) indeks chromatyczny (kolorowanie krawędzi) grafu Kn wynosi n.
Punkt za każdą poprawną odpowiedz
POWYŻEJ pierwszej!
6. (2p.) Wyjaśnij, dla jakich n graf K4,n jest: a) eulerowski, b) hamilto-
nowski?
7. (3p.) Korzystając ze wzoru Eulera wykaż, ze graf K3,3 nie jest planar-
ny.
7
MATEMATYKA DYSKRETNA - KOLOKWIUM 2 GRUPA D
RACHUNKI+KRÓTKIE WYJAŚNIENIA! NA TEJ KARTCE!
KAŻDA DODATKOWA KARTKA TO MINUS 1 PUNKT!
Imię i nazwisko ........................... ......... Nr indeksu ..............
1. (2p.) Wyjaśnij, dla jakich n graf K3,n jest: a) eulerowski, b) hamilto-
nowski?
2. (3p.) Narysuj kod zerojedynkowy podanego drzewa, startując z wy-
różnionego wierzchołka, w kierunku przeciwnym do ruchu wskazówek
zegara.
3. (2p.) Korzystając z algorytmu Kruskala znajdz
minimalne drzewo
spinające. Z opisu (rysunku) musi być jasne, w jakiej kolejności w drzewie
pojawiały się kolejne krawędzie.
4. (3p). Ile jest grafów symetrycznych, bez krawędzi wielokrotnych (ale
mogą być pętle), o 7 wierzchołkach i 10 krawędziach? Grafy izomorficzne
traktujemy jako różne.
8
5. (3p.) Korzystając ze wzoru Eulera wykaż, że wielościan foremny, któ-
rego kazda ściana jest trójkątem, a w wierzchołku styka się po pięć trój-
kątów, musi być dwudziestościanem.
6. (2p.) Ile co najwyżej wyrazów niezerowych ma macierz incydencji
grafu acyklicznego o n wierzchołkach?
7. (3p.) Określ wartość logiczną zdań (Prawda- Fałsz) Drzewo oznacza
tu zawsze drzewo o więcej niż jednym wierzchołku.
a) każdy graf spójny ma przynajmniej jeden wierzchołek stopnia parzy-
stego;
b) każde drzewo T ma wierzchołki stopnia 1;
c) indeks chromatyczny (kolorowanie krawędzi) każdego drzewa T wynosi
2;
c) liczba chromatyczna każdego drzewa T (kolorowanie wierzchołków)
wynosi 2.
Punkt za każdą poprawną odpowiedz
POWYŻEJ pierwszej!