Matematyka dyskretna - grafy - zadania.pdf
(
109 KB
)
Pobierz
3931361 UNPDF
LISTA1 MATEMATYKADYSKRETNA Matematyka
Dlapodanychni˙zejhipergraf´ow
H
=(
V;E
)
;
rozwi¸aza´czadania1-10.
a.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
g;E
=
ffv
1
;v
2
;v
3
g;fv
1
;v
2
g;fv
1
;v
3
g;fv
4
;v
5
gg;
b.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
g;
E
=
ffv
1
;v
2
;v
4
g;fv
1
;v
2
;v
4
;v
6
g;fv
2
;v
3
;v
5
g;fv
2
;v
3
;v
4
;v
5
;v
6
g;fv
3
;v
5
;v
6
g;fv
5
;v
6
gg:
c.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
g;E
=
ffv
1
g;fv
1
;v
3
g;fv
1
;v
2
;v
4
g;fv
3
;v
4
;v
5
g;fv
3
;v
5
gg:
d.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
;g;
E
=
ffv
1
;v
2
;v
4
;v
5
g;fv
1
;v
6
g;fv
2
;v
3
g;fv
1
;v
2
;v
6
g;fv
2
;v
3
g;fv
4
;v
5
;v
6
gg;
e.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
g;E
=
ffv
1
;v
2
;v
3
g;fv
1
;v
3
;v
5
g;fv
2
;v
4
;v
5
g;fv
1
;v
3
;v
4
gg;
f.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
g;
E
=
ffv
1
;v
2
g;fv
1
;v
6
g;fv
2
;v
4
g;fv
2
;v
5
g;fv
2
;v
6
g;fv
3
;v
4
g;fv
3
;v
5
g;fv
3
;v
6
g;fv
5
;v
6
gg:
g.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
;v
7
g;
E
=
ffv
2
g;fv
2
;v
4
;v
5
;v
7
g;fv
2
;v
3
;v
5
;v
6
g;fv
4
;v
7
g;fv
3
;v
5
g;fv
5
;v
6
gg;
h.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
;v
7
;v
8
g;E
=
ffv
1
;v
2
g;fv
1
;v
8
g;fv
2
;v
3
;v
4
g;fv
3
;v
5
g;fv
5
;v
6
;v
7
;v
8
gg;
i.
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
g;
E
=
ffv
1
;v
2
;v
3
g;fv
1
;v
3
;v
6
g;fv
2
;v
3
;v
4
g;fv
2
;v
3
;v
5
g;fv
2
;v
3
;v
6
g;fv
3
;v
4
;v
5
g;fv
3
;v
5
;v
6
gg:
Zad.1Poda´cinterpretacj¸egeometryczn¸atychhipergraf´ow.
Zad.2Wyznaczy´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.3Wyznaczy´cmacierzs¸asiedztw
A
(
H
)orazmacierzincydencji
R
(
H
).
Zad.4Okre´sli´c,czyw´sr´odtychhipergraf´ows¸a:hipergrafysp´ojne,hipergrafyproste,hiper-
grafyregularne,hipergrafyjednorodne,pseudografy,multigrafy,grafy.
Zad.5Znale´z´c(oileistnieje)drog¸edÃlugo´sci4i5orazcykldÃlugo´sci3i4.
Zad.6Wyznaczy´cnajdÃlu˙zsz¸a´scie˙zk¸e,drog¸eicykl.
Zad.7Wyznaczy´c(oilemo˙zliwe)podhipergrafy
H
0
=(
V
0
;E
0
)
;
gdzie
1.
jV
0
j
=
jE
0
j
=3, 2.
jV
0
j
=4
;jE
0
j
=2, 3.
jV
0
j
=3
;jE
0
j
=5.
Zad.8Wyznaczy´chipergrafy
H
[
X
]oraz
Hj
X
dla
X
=
A;B;C;D
,je˙zeli
A
=
fv
1
;v
2
;v
3
;v
4
g;B
=
fv
2
;v
4
;v
5
g;C
=
fv
3
;v
5
g;D
=
fv
1
;v
3
;v
6
g
.
Zad.9Wyznaczy´c(oileistniej¸a)podhipergrafyb¸ed¸ace
1.grafamirozpinaj¸acymi1-regularnymi, 2.pseudografamirozpinaj¸acymi,
3.3-jednorodnymirozpinaj¸acymihipergrafami, 4.grafamirz¸edu5o¢
·
2.
Zad.10Znale´z´cmultigrafyprzeci¸e´ctychhipergraf´ow.
Definicja.
Multigrafemprzeci¸e´chipergrafuH
=(
V;E
)nazywamymultigraf
I
(
H
),wkt´orym
V
(
I
(
H
))=
E
(
H
)orazdwawierzchoÃlki
e
i
;e
j
multigrafus¸apoÃl¸aczone
k
-kraw¸edziamir´ownolegÃlymi
wtedyitylkowtedy,gdyodpowiedaj¸aceimkraw¸edziehipergrafumaj¸adokÃladnie
k
element´ow
wsp´olnych.
Zad.11Danyjestgraf
G
omacierzyincydencjiorazs¸asiedztw(odpowiednio)
a
:R
(
G
)=
2
6
6
6
6
6
6
6
6
6
6
6
4
100000000
110000000
011100001
000010001
000011100
001001010
000100110
3
7
7
7
7
7
7
7
7
7
7
7
5
;
b
:A
(
G
)=
2
6
6
6
6
6
6
6
6
6
6
6
6
6
4
01000000
10111100
01011110
01101110
01110100
01111000
00110001
00000010
3
7
7
7
7
7
7
7
7
7
7
7
7
7
5
:
Wyznaczy´cmacierzs¸asiedztworazmacierzincydencji(odpowiednio)grafu
G
iznale´z´cstopie´n
ka˙zdegowierzchoÃlkagrafu
G
.
Zad.12Znale´z´cnieizomorficznegrafy
G¡v
,maj¸acdanygraf
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.13Odtworzy´cnieizomorficznegrafy
G
,maj¸acdanygraf
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.14Sprawdzi´c,czyistniejegraf,wkt´orymstopniewierzchoÃlk´ows¸ar´owne
1.5,5,5,5,6,6, 2.5,5,4,4,3,2, 3.5,4,3,3,2,1.
Zad.15Wykaza´c,˙zeliczbawierzchoÃlk´owonieparzystymstopniuwdowolnymgrafie
G
jest
zawszeparzysta.
Zad.16Poda´cprzykÃlady(oileistniej¸a)
1.grafudwudzielnego,kt´oryjestregularny,
2.czterech(nieizomorficznych)graf´owsp´ojnych,kt´ores¸a4-regularne,
3.wszystkichnieizomorficznychgraf´owrz¸edu4,
4.wszystkichnieizomorficznychsp´ojnychgraf´owrz¸edu5,
5.wszystkichnieizomorficznychdrzewrz¸educonajwy˙zej6.
Zad.17Wykaza´c,˙zegraf
G
lubgraf
G
jestsp´ojny.
Zad.18Wykaza´c,˙zeliczbawierzchoÃlk´owwgrafiesamodopeÃlniaj¸acymsi¸e(
G
=
G
)
wynosi4
k
albo4
k
+1.Poda´cprzykÃladygraf´owsamodopeÃlniaj¸acychsi¸eo4i5wierzchoÃlkach.
Zad.19Wyznaczy´cliczb¸ekraw¸edzigrafupeÃlnegotr´ojdzielnego
K
r;s;t
=
K
r
+
K
s
+
K
t
.
Narysowa´cgrafytr´ojdzielneo6,7,8wierzchoÃlkach.
Zad.20Znale´z´crz¸ad,rozmiar,minimalnyimaksymalnystopie´nnast¸epuj¸acychgraf´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
2
m
¡mK
2
, 9.(4
K
n
[
5
P
n
)+6
K
n;n
,
gdzie
mG
=
G[G
[
:::[G
| {z }
m¡
razy
=
[
m
G
.
LISTA2 MATEMATYKADYSKRETNA Matematyka
Zad.1Wyznaczy´c(oileistnieje)homomorfizmnast¸epuj¸acychparmultigraf´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.2Sprawdzi´c,czypodanemultigrafy(rys.(1)-(4))s¸aizomorficzne.
Zad.3Znale´z´cpromie´n
r
(
G
),centrum
CT
(
G
)i´srednic¸ediam(
G
)nast¸epuj¸acychgraf´ow
1.
G
=(
V;E
),gdzie
V
=
fv
1
;v
2
;v
3
;v
4
;v
5
;v
6
g;
E
=
ffv
1
;v
2
g;fv
1
;v
6
g;fv
2
;v
4
g;fv
2
;v
5
g;fv
2
;v
6
g;fv
3
;v
4
g;fv
3
;v
5
g;fv
3
;v
6
g;fv
5
;v
6
gg
,
2.
G
=(
V;E
),gdzie
V
=
f
1
;
2
;
3
;
4
;
5
g;E
=
ff
1
;
2
g;f
1
;
4
g;f
2
;
3
g;f
2
;
5
g;f
2
;
4
g;f
3
;
4
g;f
4
;
5
gg
,
3.
K
n
, 4.
P
n
, 5.
C
n
, 6.
K
m;n
, 7.
C
n
¡e
,
8.
n
-wierzchoÃlkowychnieizomorficznychdrzew
T
dla
n
=3
;
4
;
5.
Zad.4Wykaza´c,˙zelas
F
o
k
-komponentachsp´ojno´sciposiada
jV
(
F
)
j¡k
kraw¸edzi.
Zad.5Narysowa´cwszystkienieizomorficznedrzewarz¸edu4
1.niezaetykietowane 2.niezaetykietowanezkorzeniem 3.zaetykietowane.
Zad.6Wyznaczy´cgrup¸eautomorfizm´owgrafu
G
=(
V;E
),je˙zeli
1.
V
=
f
1
;
2
;
3
;
4
;
5
;
6
g;E
=
ff
1
;
2
g;f
1
;
3
g;f
1
;
5
g;f
2
;
4
g;f
2
;
6
g;f
3
;
4
g;f
3
;
5
g;f
4
;
6
gg
,
2.
V
=
f
1
;
2
;
3
;
4
;
5
g;E
=
ff
1
;
2
g;f
1
;
4
g;f
2
;
3
g;f
2
;
5
g;f
2
;
4
g;f
3
;
4
g;f
4
;
5
gg
,
3.
V
=
f
1
;
2
;:::;
9
g;E
=
ff
1
;
2
g;f
2
;
3
g;f
2
;
4
g;f
2
;
5
g;f
5
;
6
g;f
5
;
7
g;f
5
;
8
g;f
6
;
9
gg
,
4.
V
=
f
1
;
2
;:::;
10
g;E
=
ff
1
;
5
g;f
1
;
6
g;f
1
;
7
g;f
1
;
9
g;f
2
;
6
g;f
3
;
6
g;f
4
;
6
g;f
4
;
8
g;f
4
;
10
gg
.
Zad.7Obliczy´c,ilezaetykietowanychdrzewnazbiorzewierzchoÃlk´ow
f
1
;
2
;:::;ng
posiada
1.wierzchoÃlekstopnia
n¡
1
;
2.wierzchoÃlekstopnia
n¡
2
;
3.wszystkiewierzchoÃlkistopnia1lub2
;
4.stopie´nwierzchoÃlka1r´ownyjeden.
Zad.8Niech
T
b¸edziedrzewem.Pokaza´c,˙ze
P
v2V
(
T
)
d
T
(
v
)=2(
n¡
1)
:
Zad.9Wykaza´c,˙zewdrzewie
T
rz¸edu
n;n¸
2istniej¸aconajmniejdwawierzchoÃlkiwisz¸ace.
Zad.10Wykaza´c,˙zeje˙zeli
±
(
G
)
¸
2,tograf
G
zawieracykl.
Zad.11Znale´z´ckodPr¨uferadladrzew
T
=(
V;E
),gdzie
1.
V
=
f
1
;
2
;:::;
10
g
oraz
E
=
ff
1
;
5
g;f
1
;
6
g;f
1
;
7
g;f
1
;
9
g;f
2
;
6
g;f
3
;
6
g;f
4
;
6
g;f
4
;
8
g;f
4
;
10
gg
,
2.
V
=
f
1
;
2
;:::;
9
g
oraz
E
=
ff
1
;
3
g;f
1
;
5
g;f
1
;
8
g;f
2
;
3
g;f
3
;
4
g;f
3
;
6
g;f
3
;
7
g;f
3
;
9
gg
.
Zad.12Znale´z´cdrzewaopodanychkodachPr¨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.13Obliczy´c,ilewierzchoÃlk´owmadrzewopeÃlnebinarneodanejwysoko´sci
h:
Zad.14Zbudowa´coptymalnedrzewobinarnedlazbior´owwagiobliczy´cjegowag¸e
1.
f
1
;
3
;
4
;
6
;
9
;
13
g;
2.
f
2
;
4
;
5
;
8
;
13
;
15
;
18
;
25
g;
3.
f
1
;
1
;
2
;
3
;
5
;
8
;
13
;
21
;
34
g:
Zad.15Danyjestgraf
G
=(
V;E
)
;
gdzie
V
=
f
1
;
2
;
3
;
4
;
5
g;E
=
ff
1
;
2
g;f
1
;
3
g;f
1
;
4
g;
f
2
;
3
g;f
3
;
4
g;f
4
;
5
gg
.
1.Narysowa´cwszystkiedrzewarozpinaj¸acetegografu.
2.Wyznaczy´czbi´orcyklifundamentalnychiprzekroj´ow(kocykli)elementarnychzwi¸azanych
zwybranymdrzewemrozpinaj¸acym.
3.Wygenerowa´cwszystkiecykleiprzekroje(kocykle)grafu
G
.
4.Wyznaczy´cliczb¸ecyklomatyczn¸a
¹
(
G
)orazliczb¸ekocyklomatyczn¸a
¹
¤
(
G
).
Zad.16Danyjestgraf
G
=(
V;E
)
;V
=
f
1
;
2
;:::;
10
g;E
=
ff
1
;
2
g;f
1
;
6
g;f
1
;
8
g;f
2
;
5
g;
f
3
;
4
g;f
3
;
5
g;f
3
;
6
g;f
4
;
5
g;f
4
;
9
g;f
4
;
10
g;f
5
;
6
g;f
6
;
7
g;f
6
;
8
g;f
7
;
8
g;f
9
;
10
gg
.
1.Pokaza´cjakalgorytm
DFS
wyznaczadrzeworozpinaj¸acetegografuorazwyznaczy´c
zbi´orcyklifundamentalnychiprzekroj´owelementarnychzwi¸azanychztymdrzewem.
2.Pokaza´cjakalgorytm
BFS
wyznaczadrzeworozpinaj¸acetegografuorazwyznaczy´c
zbi´orcyklifundamentalnychiprzekroj´owelementarnychzwi¸azanychztymdrzewem.
5.Korzystaj¸aczalgorytmu
BFS;
wyznaczy´codlegÃlo´s´cwierzchoÃlk´owgrafu
G
odwierz-
choÃlka3.
Zad.17Niech
T
b¸edziedrzewemrozpinaj¸acymgrafu
G
(
G6
=
T
)
:
Udowodni´c,˙ze
1.dowolnyprzekr´ojgrafu
G
makraw¸ed´zwsp´oln¸az
T
,
2.dowolnycyklgrafu
G
makraw¸ed´zwsp´oln¸az
G¡T
,
3.graf
T
+
e
zawieracykldladowolnejkraw¸edzi
e2E
(
G¡T
)
:
Zad.18Danyjestmultigraf
G
=(
V;E
)
;
gdzie
V
=
f
1
;
2
;
3
;
4
g;E
=
ff
1
;
2
g;f
1
;
2
g;f
1
;
3
g;
f
1
;
4
g;f
2
;
3
g;f
2
;
4
g;f
3
;
4
gg
orazjegopodmultigrafy
G
i
=(
V;E
i
)(
i
=1
;
2
;
3)
;E
1
=
ff
1
;
2
g;
f
1
;
2
g;f
2
;
3
g;f
3
;
4
gg;E
2
=
ff
1
;
2
g;f
1
;
3
g;f
2
;
4
g;f
3
;
4
gg;E
3
=
ff
1
;
3
g;f
1
;
4
g;f
2
;
3
g;f
2
;
4
gg
.
Wyznaczy´cnast¸epuj¸acer´o˙znicesymetrycznegraf´ow
G
1
¥G
2
;G
1
¥G
3
;G
2
¥G
3
;G
1
¥G
2
¥G
3
:
Zad.19Danyjestgraf
G
=(
V;E
)
;
gdzie
V
=
f
1
;
2
;
3
;
4
g;E
=
ff
1
;
2
g;f
1
;
3
g;f
1
;
4
g;f
2
;
3
gg:
Wyznaczy´cprzestrzenieW
G
;
W
C
;
W
C
¤
orazichbazyiwymiary.
Zad.20Wyznaczy´cliczb¸ecyklomatyczn¸a
¹
(
G
)orazliczb¸ekocyklomatyczn¸a
¹
¤
(
G
)dla
K
n
;K
m;n
;C
n
;C
n
[K
m
;K
1
;n
[P
m
[K
n;n;m
;r
-regularnegografu
G
rz¸edu
n
.
Niech
G
=(
V;E
)b¸edziemultigrafem,a
G
j
=(
V;E
j
)
;j
=1
;
2jegopodmultigrafami.
R´o˙znic¸a
symetryczn¸aG
1
¥G
2
nazywamymultigraf
G
0
=(
V;E
1
¥E
2
).
Niech
jE
(
G
)
j
=
m
oraz
FµE
.Podzbiorowi
F
przyporz¸adkowujemywektor
X
F
=[
x
1
;:::;x
m
]
taki,˙ze
x
i
=1
,e
i
2F
oraz
x
i
=0wprzeciwnymwypadku.R´oznicysymetrycznejmultigraf´ow
odpowiadadodawaniewektor´owmodulo2.
Przez
W
E
oznaczmyzbi´orwszystkichwektor´owodpowiadaj¸acychpodzbioromrodziny2
E
,natomiast
przez
W
C
(
W
C
¤
)-podzbioromkraw¸edzioworozÃl¸acznychcykli(przekroj´ow)multigrafu.
Twierdzenie1.W
G
=(
W
E
;GF
(2)
;
+
2
;¢
2
)
jestprzestrzeni¸awektorow¸amultigrafuG
=(
V;E
)
.
Twierdzenie2.
PrzestrzeniamiwektorowymimultigrafuG
=(
V;E
)
s¸a
przestrze´ncykli
W
C
=(
W
C
;GF
(2)
;
+
2
;¢
2
)
orazprzestrze´nprzekroj´ow
W
C
¤
=(
W
C
¤
;GF
(2)
;
+
2
;¢
2
)
.
Plik z chomika:
Minnie_
Inne pliki z tego folderu:
kod Huffmana.PDF
(94 KB)
Intro.PDF
(294 KB)
Final.PDF
(1248 KB)
entropia informacji.PDF
(87 KB)
C3.doc
(41 KB)
Inne foldery tego chomika:
Algebra
Algebra liniowa
Analiza Funkcjonalna
Analiza matematyczna
Analiza Regresji
Zgłoś jeśli
naruszono regulamin