LISTA 1
MATEMATYKA DYSKRETNA
Matematyka
Dla podanych ni˙zej hipergraf´ow H = (V, E), rozwi¸aza´c zadania 1-10.
a. V = {v
1
, v
2
, v
3
, v
4
, v
5
}, E = {{v
1
, v
2
, v
3
}, {v
1
, v
2
}, {v
1
, v
3
}, {v
4
, v
5
}},
b. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
E = {{v
1
, v
2
, v
4
}, {v
1
, v
2
, v
4
, v
6
}, {v
2
, v
3
, v
5
}, {v
2
, v
3
, v
4
, v
5
, v
6
}, {v
3
, v
5
, v
6
}, {v
5
, v
6
}}.
c. V = {v
1
, v
2
, v
3
, v
4
, v
5
}, E = {{v
1
}, {v
1
, v
3
}, {v
1
, v
2
, v
4
}, {v
3
, v
4
, v
5
}, {v
3
, v
5
}}.
d. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, },
E = {{v
1
, v
2
, v
4
, v
5
}, {v
1
, v
6
}, {v
2
, v
3
}, {v
1
, v
2
, v
6
}, {v
2
, v
3
}, {v
4
, v
5
, v
6
}},
e. V = {v
1
, v
2
, v
3
, v
4
, v
5
}, E = {{v
1
, v
2
, v
3
}, {v
1
, v
3
, v
5
}, {v
2
, v
4
, v
5
}, {v
1
, v
3
, v
4
}},
f. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
E = {{v
1
, v
2
}, {v
1
, v
6
}, {v
2
, v
4
}, {v
2
, v
5
}, {v
2
, v
6
}, {v
3
, v
4
}, {v
3
, v
5
}, {v
3
, v
6
}, {v
5
, v
6
}}.
g. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, v
7
},
E = {{v
2
}, {v
2
, v
4
, v
5
, v
7
}, {v
2
, v
3
, v
5
, v
6
}, {v
4
, v
7
}, {v
3
, v
5
}, {v
5
, v
6
}},
h. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, v
7
, v
8
}, E = {{v
1
, v
2
}, {v
1
, v
8
}, {v
2
, v
3
, v
4
}, {v
3
, v
5
}, {v
5
, v
6
, v
7
, v
8
}},
i. V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
E = {{v
1
, v
2
, v
3
}, {v
1
, v
3
, v
6
}, {v
2
, v
3
, v
4
}, {v
2
, v
3
, v
5
}, {v
2
, v
3
, v
6
}, {v
3
, v
4
, v
5
}, {v
3
, v
5
, v
6
}}.
Zad.1 Poda´c interpretacj¸e geometryczn¸a tych hipergraf´ow.
Zad.2 Wyznaczy´c N
H
(v
3
), N
H
(v
5
), N
H
[v
2
], N
H
[v
6
], d
H
(v
2
), d
H
(v
4
), δ(H), ∆(H).
Zad.3 Wyznaczy´c macierz s¸asiedztw A(H) oraz macierz incydencji R(H).
Zad.4 Okre´sli´c, czy w´sr´od tych hipergraf´ow s¸a: hipergrafy sp´ojne, hipergrafy proste, hiper-
grafy regularne, hipergrafy jednorodne, pseudografy, multigrafy, grafy.
Zad.5 Znale´z´c (o ile istnieje) drog¸e dÃlugo´sci 4 i 5 oraz cykl dÃlugo´sci 3 i 4.
Zad.6 Wyznaczy´c najdÃlu˙zsz¸a ´scie˙zk¸e, drog¸e i cykl.
Zad.7 Wyznaczy´c (o ile mo˙zliwe) podhipergrafy H
0
= (V
0
, E
0
), gdzie
1. |V
0
| = |E
0
| = 3,
2. |V
0
| = 4, |E
0
| = 2,
3. |V
0
| = 3, |E
0
| = 5.
Zad.8 Wyznaczy´c hipergrafy H[X] oraz H|
X
dla X = A, B, C, D, je˙zeli
A = {v
1
, v
2
, v
3
, v
4
}, B = {v
2
, v
4
, v
5
}, C = {v
3
, v
5
}, D = {v
1
, v
3
, v
6
}.
Zad.9 Wyznaczy´c (o ile istniej¸a) podhipergrafy b¸ed¸ace
1. grafami rozpinaj¸acymi 1-regularnymi,
2. pseudografami rozpinaj¸acymi,
3. 3-jednorodnymi rozpinaj¸acymi hipergrafami,
4. grafami rz¸edu 5 o ∆ ≤ 2.
Zad.10 Znale´z´c multigrafy przeci¸e´c tych hipergraf´ow.
Definicja. Multigrafem przeci¸e´c hipergrafu H = (V, E) nazywamy multigraf I(H), w kt´orym
V (I(H)) = E(H) oraz dwa wierzchoÃlki e
i
, e
j
multigrafu s¸a poÃl¸aczone k-kraw¸edziami r´ownolegÃlymi
wtedy i tylko wtedy, gdy odpowiedaj¸ace im kraw¸edzie hipergrafu maj¸a dokÃladnie k element´ow
wsp´olnych.
Zad.11 Dany jest graf G o macierzy incydencji oraz s¸asiedztw (odpowiednio)
a. R(G) =
1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0 0
0 0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 1 0
,
b. A(G) =
0 1 0 0 0 0 0 0
1 0 1 1 1 1 0 0
0 1 0 1 1 1 1 0
0 1 1 0 1 1 1 0
0 1 1 1 0 1 0 0
0 1 1 1 1 0 0 0
0 0 1 1 0 0 0 1
0 0 0 0 0 0 1 0
.
Wyznaczy´c macierz s¸asiedztw oraz macierz incydencji (odpowiednio) grafu G i znale´z´c stopie´n
ka˙zdego wierzchoÃlka grafu G.
Zad.12 Znale´z´c nieizomorficzne grafy G − v, maj¸ac dany graf G
1. K
4
− e oraz d
G
(v) = 3,
2. P
4
∪ K
1
oraz d
G
(v) = 2,
3. K
1,3
+ e oraz d
G
(v) = 2,
4. C
5
.
Zad.13 Odtworzy´c nieizomorficzne grafy G, maj¸ac dany graf G − v
1. K
5
− e oraz d
G
(v) = 2,
2. P
5
∪ K
1
oraz d
G
(v) ≤ 1,
3. K
1,4
+ e oraz d
G
(v) = 3,
4. C
4
oraz d
G
(v) ≤ 2.
Zad.14 Sprawdzi´c, czy istnieje graf, w kt´orym stopnie wierzchoÃlk´ow s¸a r´owne
1. 5,5,5,5,6,6,
2. 5,5,4,4,3,2,
3. 5,4,3,3,2,1.
Zad.15 Wykaza´c, ˙ze liczba wierzchoÃlk´ow o nieparzystym stopniu w dowolnym grafie G jest
zawsze parzysta.
Zad.16 Poda´c przykÃlady (o ile istniej¸a)
1. grafu dwudzielnego, kt´ory jest regularny,
2. czterech (nieizomorficznych) graf´ow sp´ojnych, kt´ore s¸a 4-regularne,
3. wszystkich nieizomorficznych graf´ow rz¸edu 4,
4. wszystkich nieizomorficznych sp´ojnych graf´ow rz¸edu 5,
5. wszystkich nieizomorficznych drzew rz¸edu co najwy˙zej 6.
Zad.17 Wykaza´c, ˙ze graf G lub graf G jest sp´ojny.
Zad.18 Wykaza´c, ˙ze liczba wierzchoÃlk´ow w grafie samodopeÃlniaj¸acym si¸e (G = G)
wynosi 4k albo 4k + 1. Poda´c przykÃlady graf´ow samodopeÃlniaj¸acych si¸e o 4 i 5 wierzchoÃlkach.
Zad.19 Wyznaczy´c liczb¸e kraw¸edzi grafu peÃlnego tr´ojdzielnego K
r,s,t
= K
r
+ K
s
+ K
t
.
Narysowa´c grafy tr´ojdzielne o 6,7,8 wierzchoÃlkach.
Zad.20 Znale´z´c rz¸ad, rozmiar, minimalny i maksymalny stopie´n nast¸epuj¸acych graf´ow
1. K
m,n
,
2. K
n
+ K
m
,
3. C
n
∪ C
n
,
4. P
n
+ P
m
,
5. K
m
∪ K
n
,
6. (C
n
+ C
m
) + K
r,s,t
,
7. (K
1,n
− e) + mK
1
,
8. K
2m
− mK
2
,
9. (4K
n
∪ 5P
n
) + 6K
n,n
,
gdzie mG = G ∪ G ∪ ... ∪ G
|
{z
}
m−razy
= ∪
m
G.
LISTA 2
MATEMATYKA DYSKRETNA
Matematyka
Zad.1 Wyznaczy´c (o ile istnieje) homomorfizm nast¸epuj¸acych par multigraf´ow
1. P
3
i P
5
,
2. C
3
i C
5
,
3. P
3
i C
4
,
4. rys.(1),
5. rys.(2).
Zad.2 Sprawdzi´c, czy podane multigrafy (rys.(1)-(4)) s¸a izomorficzne.
Zad.3 Znale´z´c promie´n r(G), centrum CT (G) i ´srednic¸e diam(G) nast¸epuj¸acych graf´ow
1. G = (V, E), gdzie V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
E = {{v
1
, v
2
}, {v
1
, v
6
}, {v
2
, v
4
}, {v
2
, v
5
}, {v
2
, v
6
}, {v
3
, v
4
}, {v
3
, v
5
}, {v
3
, v
6
}, {v
5
, v
6
}},
2. G = (V, E), gdzie V = {1, 2, 3, 4, 5}, E = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {2, 4}, {3, 4}, {4, 5}},
3. K
n
,
4. P
n
,
5. C
n
,
6. K
m,n
,
7. C
n
− e,
8. n-wierzchoÃlkowych nieizomorficznych drzew T dla n = 3, 4, 5.
Zad.4 Wykaza´c, ˙ze las F o k-komponentach sp´ojno´sci posiada |V (F )| − k kraw¸edzi.
Zad.5 Narysowa´c wszystkie nieizomorficzne drzewa rz¸edu 4
1. niezaetykietowane
2. niezaetykietowane z korzeniem
3. zaetykietowane.
Zad.6 Wyznaczy´c grup¸e automorfizm´ow grafu G = (V, E), je˙zeli
1. V = {1, 2, 3, 4, 5, 6}, E = {{1, 2}, {1, 3}, {1, 5}, {2, 4}, {2, 6}, {3, 4}, {3, 5}, {4, 6}},
2. V = {1, 2, 3, 4, 5}, E = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {2, 4}, {3, 4}, {4, 5}},
3. V = {1, 2, ..., 9}, E = {{1, 2}, {2, 3}, {2, 4}, {2, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 9}},
4. V = {1, 2, ..., 10}, E = {{1, 5}, {1, 6}, {1, 7}, {1, 9}, {2, 6}, {3, 6}, {4, 6}, {4, 8}, {4, 10}}.
Zad.7 Obliczy´c, ile zaetykietowanych drzew na zbiorze wierzchoÃlk´ow {1, 2, ..., n} posiada
1. wierzchoÃlek stopnia n − 1,
2. wierzchoÃlek stopnia n − 2,
3. wszystkie wierzchoÃlki stopnia 1 lub 2,
4. stopie´n wierzchoÃlka 1 r´owny jeden.
Zad.8 Niech T b¸edzie drzewem. Pokaza´c, ˙ze
P
v∈V (T )
d
T
(v) = 2(n − 1).
Zad.9 Wykaza´c, ˙ze w drzewie T rz¸edu n, n ≥ 2 istniej¸a co najmniej dwa wierzchoÃlki wisz¸ace.
Zad.10 Wykaza´c, ˙ze je˙zeli δ(G) ≥ 2, to graf G zawiera cykl.
Zad.11 Znale´z´c kod Pr¨ufera dla drzew T = (V, E), gdzie
1. V = {1, 2, ..., 10} oraz E = {{1, 5}, {1, 6}, {1, 7}, {1, 9}, {2, 6}, {3, 6}, {4, 6}, {4, 8}, {4, 10}},
2. V = {1, 2, ..., 9} oraz E = {{1, 3}, {1, 5}, {1, 8}, {2, 3}, {3, 4}, {3, 6}, {3, 7}, {3, 9}}.
Zad.12 Znale´z´c drzewa o podanych kodach Pr¨ufera
1. 4, 7, 2, 7, 4, 2, 4,
2. 4, 4, 4, 4, 4, 4,
3. 8, 2, 6, 1, 9, 9, 1.
Zad.13 Obliczy´c, ile wierzchoÃlk´ow ma drzewo peÃlne binarne o danej wysoko´sci h.
Zad.14 Zbudowa´c optymalne drzewo binarne dla zbior´ow wag i obliczy´c jego wag¸e
1. {1, 3, 4, 6, 9, 13},
2. {2, 4, 5, 8, 13, 15, 18, 25},
3. {1, 1, 2, 3, 5, 8, 13, 21, 34}.
Zad.15 Dany jest graf G = (V, E), gdzie V = {1, 2, 3, 4, 5}, E = {{1, 2}, {1, 3}, {1, 4},
{2, 3}, {3, 4}, {4, 5}}.
1. Narysowa´c wszystkie drzewa rozpinaj¸ace tego grafu.
2. Wyznaczy´c zbi´or cykli fundamentalnych i przekroj´ow (kocykli) elementarnych zwi¸azanych
z wybranym drzewem rozpinaj¸acym.
3. Wygenerowa´c wszystkie cykle i przekroje (kocykle) grafu G.
4. Wyznaczy´c liczb¸e cyklomatyczn¸a µ(G) oraz liczb¸e kocyklomatyczn¸a µ
∗
(G).
Zad.16 Dany jest graf G = (V, E), V = {1, 2, ..., 10}, E = {{1, 2}, {1, 6}, {1, 8}, {2, 5},
{3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 9}, {4, 10}, {5, 6}, {6, 7}, {6, 8}, {7, 8}, {9, 10}}.
1.
Pokaza´c jak algorytm DF S wyznacza drzewo rozpinaj¸ace tego grafu oraz wyznaczy´c
zbi´or cykli fundamentalnych i przekroj´ow elementarnych zwi¸azanych z tym drzewem.
2.
Pokaza´c jak algorytm BF S wyznacza drzewo rozpinaj¸ace tego grafu oraz wyznaczy´c
zbi´or cykli fundamentalnych i przekroj´ow elementarnych zwi¸azanych z tym drzewem.
5.
Korzystaj¸ac z algorytmu BF S, wyznaczy´c odlegÃlo´s´c wierzchoÃlk´ow grafu G od wierz-
choÃlka 3 .
Zad.17 Niech T b¸edzie drzewem rozpinaj¸acym grafu G (G 6= T ). Udowodni´c, ˙ze
1. dowolny przekr´oj grafu G ma kraw¸ed´z wsp´oln¸a z T ,
2. dowolny cykl grafu G ma kraw¸ed´z wsp´oln¸a z G − T ,
3. graf T + e zawiera cykl dla dowolnej kraw¸edzi e ∈ E(G − T ).
Zad.18 Dany jest multigraf G = (V, E), gdzie V = {1, 2, 3, 4}, E = {{1, 2}, {1, 2}, {1, 3},
{1, 4}, {2, 3}, {2, 4}, {3, 4}} oraz jego podmultigrafy G
i
= (V, E
i
) (i = 1, 2, 3), E
1
= {{1, 2},
{1, 2}, {2, 3}, {3, 4}}, E
2
= {{1, 2}, {1, 3}, {2, 4}, {3, 4}}, E
3
= {{1, 3}, {1, 4}, {2, 3}, {2, 4}}.
Wyznaczy´c nast¸epuj¸ace r´o˙znice symetryczne graf´ow G
1
÷G
2
, G
1
÷G
3
, G
2
÷G
3
, G
1
÷G
2
÷G
3
.
Zad.19 Dany jest graf G = (V, E), gdzie V = {1, 2, 3, 4}, E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}}.
Wyznaczy´c przestrzenie W
G
, W
C
, W
C
∗
oraz ich bazy i wymiary.
Zad.20
Wyznaczy´c liczb¸e cyklomatyczn¸a µ(G) oraz liczb¸e kocyklomatyczn¸a µ
∗
(G) dla
K
n
, K
m,n
, C
n
, C
n
∪ K
m
, K
1,n
∪ P
m
∪ K
n,n,m
, r-regularnego grafu G rz¸edu n.
Niech G = (V, E) b¸edzie multigrafem, a G
j
= (V, E
j
), j = 1, 2 jego podmultigrafami. R´o˙znic¸a
symetryczn¸a G
1
÷ G
2
nazywamy multigraf G
0
= (V, E
1
÷ E
2
).
Niech |E(G)| = m oraz F ⊆ E. Podzbiorowi F przyporz¸adkowujemy wektor X
F
= [x
1
, ..., x
m
]
taki, ˙ze x
i
= 1 ⇔ e
i
∈ F oraz x
i
= 0 w przeciwnym wypadku. R´oznicy symetrycznej multigraf´ow
odpowiada dodawanie wektor´ow modulo 2.
Przez W
E
oznaczmy zbi´or wszystkich wektor´ow odpowiadaj¸acych podzbiorom rodziny 2
E
, natomiast
przez W
C
(W
C
∗
) - podzbiorom kraw¸edziowo rozÃl¸acznych cykli (przekroj´ow) multigrafu.
Twierdzenie 1.
W
G
= (W
E
, GF (2), +
2
, ·
2
) jest przestrzeni¸a wektorow¸a multigrafu G = (V, E).
Twierdzenie 2. Przestrzeniami wektorowymi multigrafu G = (V, E) s¸a
przestrze´
n cykli W
C
= (W
C
, GF (2), +
2
, ·
2
) oraz przestrze´
n przekroj´ow W
C
∗
= (W
C
∗
, GF (2), +
2
, ·
2
).