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

).