LISTA 1 MATEMATYKA DYSKRETNA Matematyka
Dla podanych niżej hipergrafów H = (V, E), rozwiazać zadania 1-10.
¸
a. V = {v1, v2, v3, v4, v5}, E = {{v1, v2, v3}, {v1, v2}, {v1, v3}, {v4, v5}},
b. V = {v1, v2, v3, v4, v5, v6},
E = {{v1, v2, v4}, {v1, v2, v4, v6}, {v2, v3, v5}, {v2, v3, v4, v5, v6}, {v3, v5, v6}, {v5, v6}}.
c. V = {v1, v2, v3, v4, v5}, E = {{v1}, {v1, v3}, {v1, v2, v4}, {v3, v4, v5}, {v3, v5}}.
d. V = {v1, v2, v3, v4, v5, v6, },
E = {{v1, v2, v4, v5}, {v1, v6}, {v2, v3}, {v1, v2, v6}, {v2, v3}, {v4, v5, v6}},
e. V = {v1, v2, v3, v4, v5}, E = {{v1, v2, v3}, {v1, v3, v5}, {v2, v4, v5}, {v1, v3, v4}},
f. V = {v1, v2, v3, v4, v5, v6},
E = {{v1, v2}, {v1, v6}, {v2, v4}, {v2, v5}, {v2, v6}, {v3, v4}, {v3, v5}, {v3, v6}, {v5, v6}}.
g. V = {v1, v2, v3, v4, v5, v6, v7},
E = {{v2}, {v2, v4, v5, v7}, {v2, v3, v5, v6}, {v4, v7}, {v3, v5}, {v5, v6}},
h. V = {v1, v2, v3, v4, v5, v6, v7, v8}, E = {{v1, v2}, {v1, v8}, {v2, v3, v4}, {v3, v5}, {v5, v6, v7, v8}},
i. V = {v1, v2, v3, v4, v5, v6},
E = {{v1, v2, v3}, {v1, v3, v6}, {v2, v3, v4}, {v2, v3, v5}, {v2, v3, v6}, {v3, v4, v5}, {v3, v5, v6}}.
Zad.1 Podać interpretacj¸ geometryczn¸ tych hipergrafów.
e a
Zad.2 Wyznaczyć NH(v3), NH(v5), NH[v2], NH[v6], dH(v2), dH(v4), ´(H), "(H).
Zad.3 Wyznaczyć macierz s¸
asiedztw A(H) oraz macierz incydencji R(H).
Zad.4 OkreÅ›lić, czy wÅ›ród tych hipergrafów s¸ hipergrafy spójne, hipergrafy proste, hiper-
a:
grafy regularne, hipergrafy jednorodne, pseudografy, multigrafy, grafy.
Zad.5 Znalez
ć (o ile istnieje) drog¸ d 4 i 5 oraz cykl d 3 i 4.
e lugości lugości
Zad.6 Wyznaczyć najd a Å›cieżk¸ drog¸ i cykl.
luższ¸ e, e
Zad.7 Wyznaczyć (o ile możliwe) podhipergrafy H = (V , E ), gdzie
1. |V | = |E | = 3, 2. |V | = 4, |E | = 2, 3. |V | = 3, |E | = 5.
Zad.8 Wyznaczyć hipergrafy H[X] oraz H|X dla X = A, B, C, D, jeżeli
A = {v1, v2, v3, v4}, B = {v2, v4, v5}, C = {v3, v5}, D = {v1, v3, v6}.
Zad.9 Wyznaczyć (o ile istnieja) podhipergrafy b¸ ace
¸ ed¸
1. grafami rozpinaj¸ 1-regularnymi, 2. pseudografami rozpinaj¸
acymi acymi,
3. 3-jednorodnymi rozpinajacymi hipergrafami, 4. grafami rz¸ 5 o " d" 2.
¸ edu
Zad.10 Znalez
ć multigrafy przeci¸Ä‡ tych hipergrafów.
e
Definicja. Multigrafem przeci¸Ä‡ hipergrafu H = (V, E) nazywamy multigraf I(H), w którym
e
V (I(H)) = E(H) oraz dwa wierzcho ei, ej multigrafu s¸ po aczone k-kraw¸ równoleg
lki a l¸ edziami lymi
wtedy i tylko wtedy, gdy odpowiedajace im kraw¸ hipergrafu maja dok k elementów
¸ edzie ¸ ladnie
wspólnych.
Zad.11 Dany jest graf G o macierzy incydencji oraz s¸
asiedztw (odpowiednio)
îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ 1 0 1 1 1 1 0 0 śł
ïÅ‚ śł ïÅ‚ śł
1 1 0 0 0 0 0 0 0
ïÅ‚ śł ïÅ‚ śł
0 1 0 1 1 1 1 0
ïÅ‚ śł ïÅ‚ śł
0 1 1 1 0 0 0 0 1
ïÅ‚ śł ïÅ‚ śł
0 1 1 0 1 1 1 0
ïÅ‚ śł ïÅ‚ śł
a. R(G) = ïÅ‚ 0 0 0 0 1 0 0 0 1 śł , b. A(G) = ïÅ‚ śł .
ïÅ‚ śł ïÅ‚ śł
0 1 1 1 0 1 0 0
ïÅ‚ śł ïÅ‚ śł
0 0 0 0 1 1 1 0 0
ïÅ‚ śł ïÅ‚ śł
0 1 1 1 1 0 0 0
ïÅ‚ śł ïÅ‚ śł
0 0 1 0 0 1 0 1 0
ðÅ‚ ûÅ‚ ïÅ‚ śł
ðÅ‚ 0 0 1 1 0 0 0 1 ûÅ‚
0 0 0 1 0 0 1 1 0
0 0 0 0 0 0 1 0
Wyznaczyć macierz s¸
asiedztw oraz macierz incydencji (odpowiednio) grafu G i znalez
ć stopień
każdego wierzcho grafu G.
lka
Zad.12 Znalez
ć nieizomorficzne grafy G - v, maj¸ dany graf G
ac
1. K4 - e oraz dG(v) = 3, 2. P4 *" K1 oraz dG(v) = 2,
3. K1,3 + e oraz dG(v) = 2, 4. C5.
Zad.13 Odtworzyć nieizomorficzne grafy G, majac dany graf G - v
¸
1. K5 - e oraz dG(v) = 2, 2. P5 *" K1 oraz dG(v) d" 1,
3. K1,4 + e oraz dG(v) = 3, 4. C4 oraz dG(v) d" 2.
Zad.14 Sprawdzić, czy istnieje graf, w którym stopnie wierzcho s¸ równe
lków a
1. 5,5,5,5,6,6, 2. 5,5,4,4,3,2, 3. 5,4,3,3,2,1.
Zad.15 Wykazać, że liczba wierzcho o nieparzystym stopniu w dowolnym grafie G jest
lków
zawsze parzysta.
Zad.16 Podać przyk (o ile istnieja)
lady ¸
1. grafu dwudzielnego, który jest regularny,
2. czterech (nieizomorficznych) grafów spójnych, które s¸ 4-regularne,
a
3. wszystkich nieizomorficznych grafów rz¸ 4,
edu
4. wszystkich nieizomorficznych spójnych grafów rz¸ 5,
edu
5. wszystkich nieizomorficznych drzew rz¸ co najwyżej 6.
edu
Zad.17 Wykazać, że graf G lub graf G jest spójny.
Zad.18 Wykazać, że liczba wierzcho w grafie samodope ¸ si¸ (G = G)
lków lniajacym e
wynosi 4k albo 4k + 1. Podać przyk grafów samodope acych si¸ o 4 i 5 wierzcho
lady lniaj¸ e lkach.
Zad.19 Wyznaczyć liczb¸ kraw¸ grafu pe trójdzielnego Kr,s,t = Kr + Ks + Kt.
e edzi lnego
Narysować grafy trójdzielne o 6,7,8 wierzcho
lkach.
Zad.20 Znalez
ć rz¸ rozmiar, minimalny i maksymalny stopieÅ„ nast¸ ¸ grafów
ad, epujacych
1. Km,n, 2. Kn + Km, 3. Cn *" Cn,
4. Pn + Pm, 5. Km *" Kn, 6. (Cn + Cm) + Kr,s,t,
7. (K1,n - e) + mK1, 8. K2m - mK2, 9. (4Kn *" 5Pn) + 6Kn,n,
gdzie mG = G *" G *" ... *" G = *"mG.
m-razy
LISTA 2 MATEMATYKA DYSKRETNA Matematyka
Zad.1 Wyznaczyć (o ile istnieje) homomorfizm nast¸ ¸ par multigrafów
epujacych
1. P3 i P5, 2. C3 i C5, 3. P3 i C4, 4. rys.(1), 5. rys.(2).
Zad.2 Sprawdzić, czy podane multigrafy (rys.(1)-(4)) s¸ izomorficzne.
a
Zad.3 Znalez
ć promieÅ„ r(G), centrum CT (G) i Å›rednic¸ diam(G) nast¸ ¸ grafów
e epujacych
1. G = (V, E), gdzie V = {v1, v2, v3, v4, v5, v6},
E = {{v1, v2}, {v1, v6}, {v2, v4}, {v2, v5}, {v2, v6}, {v3, v4}, {v3, v5}, {v3, v6}, {v5, v6}},
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. Kn, 4. Pn, 5. Cn, 6. Km,n, 7. Cn - e,
8. n-wierzcho
lkowych nieizomorficznych drzew T dla n = 3, 4, 5.
Zad.4 Wykazać, że las F o k-komponentach spójnoÅ›ci posiada |V (F )| - k kraw¸
edzi.
Zad.5 Narysować wszystkie nieizomorficzne drzewa rz¸ 4
edu
1. niezaetykietowane 2. niezaetykietowane z korzeniem 3. zaetykietowane.
Zad.6 Wyznaczyć grup¸ automorfizmów grafu G = (V, E), jeżeli
e
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ć, ile zaetykietowanych drzew na zbiorze wierzcho {1, 2, ..., n} posiada
lków
1. wierzcho stopnia n - 1, 2. wierzcho stopnia n - 2,
lek lek
3. wszystkie wierzcho stopnia 1 lub 2, 4. stopień wierzcho 1 równy jeden.
lki lka
Zad.8 Niech T b¸ drzewem. Pokazać, że dT (v) = 2(n - 1).
edzie
v"V (T )
Zad.9 Wykazać, że w drzewie T rz¸ n, n e" 2 istnieja co najmniej dwa wierzcho wisz¸
edu ¸ lki ace.
Zad.10 Wykazać, że jeżeli ´(G) e" 2, to graf G zawiera cykl.
Zad.11 Znalez
ć kod Prüfera 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 Znalez
ć drzewa o podanych kodach Prüfera
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ć, ile wierzcho ma drzewo pe binarne o danej wysokości h.
lków lne
Zad.14 Zbudować optymalne drzewo binarne dla zbiorów wag i obliczyć 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ć wszystkie drzewa rozpinaj¸ tego grafu.
ace
2. Wyznaczyć zbiór cykli fundamentalnych i przekrojów (kocykli) elementarnych zwiazanych
¸
z wybranym drzewem rozpinajacym.
¸
3. Wygenerować wszystkie cykle i przekroje (kocykle) grafu G.
4. Wyznaczyć liczb¸ cyklomatyczn¸ µ(G) oraz liczb¸ kocyklomatyczn¸ µ"(G).
e a e a
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ć jak algorytm DF S wyznacza drzewo rozpinaj¸ tego grafu oraz wyznaczyć
ace
zbiór cykli fundamentalnych i przekrojów elementarnych zwiazanych z tym drzewem.
¸
2. Pokazać jak algorytm BF S wyznacza drzewo rozpinajace tego grafu oraz wyznaczyć
¸
zbiór cykli fundamentalnych i przekrojów elementarnych zwiazanych z tym drzewem.
¸
5. Korzystaj¸ z algorytmu BF S, wyznaczyć odleg wierzcho grafu G od wierz-
ac lość lków
cho 3 .
lka
Zad.17 Niech T b¸ drzewem rozpinajacym grafu G (G = T ). Udowodnić, że
edzie ¸
1. dowolny przekrój grafu G ma kraw¸ wspóln¸ z T ,
edz
a
2. dowolny cykl grafu G ma kraw¸ wspóln¸ z G - T ,
edz
a
3. graf T + e zawiera cykl dla dowolnej kraw¸ e " E(G - T ).
edzi
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 Gi = (V, Ei) (i = 1, 2, 3), E1 = {{1, 2},
{1, 2}, {2, 3}, {3, 4}}, E2 = {{1, 2}, {1, 3}, {2, 4}, {3, 4}}, E3 = {{1, 3}, {1, 4}, {2, 3}, {2, 4}}.
Wyznaczyć nast¸ ¸ różnice symetryczne grafów G1÷G2, G1÷G3, G2÷G3, G1÷G2÷G3.
epujace
Zad.19 Dany jest graf G = (V, E), gdzie V = {1, 2, 3, 4}, E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}}.
"
Wyznaczyć przestrzenie WG, WC, WC oraz ich bazy i wymiary.
Zad.20 Wyznaczyć liczb¸ cyklomatyczn¸ µ(G) oraz liczb¸ kocyklomatyczn¸ µ"(G) dla
e a e a
Kn, Km,n, Cn, Cn *" Km, K1,n *" Pm *" Kn,n,m, r-regularnego grafu G rz¸ n.
edu
Niech G = (V, E) b¸ multigrafem, a Gj = (V, Ej), j = 1, 2 jego podmultigrafami. Różnic¸
edzie a
symetryczn¸ G1 ÷ G2 nazywamy multigraf G = (V, E1 ÷ E2).
a
Niech |E(G)| = m oraz F Ä…" E. Podzbiorowi F przyporz¸
adkowujemy wektor XF = [x1, ..., xm]
taki, że xi = 1 Ô! ei " F oraz xi = 0 w przeciwnym wypadku. Róznicy symetrycznej multigrafów
odpowiada dodawanie wektorów modulo 2.
Przez WE oznaczmy zbiór wszystkich wektorów odpowiadajacych podzbiorom rodziny 2E, natomiast
¸
"
przez WC (WC ) - podzbiorom kraw¸ roz acznych cykli (przekrojów) multigrafu.
edziowo l¸
Twierdzenie 1. WG = (WE, GF (2), +2, ·2) jest przestrzeni¸ wektorow¸ multigrafu G = (V, E).
a a
Twierdzenie 2. Przestrzeniami wektorowymi multigrafu G = (V, E) s¸
a
" "
przestrzeÅ„ cykli WC = (WC, GF (2), +2, ·2) oraz przestrzeÅ„ przekrojów WC = (WC , GF (2), +2, ·2).