c Tomá² Madaras 2007
Cvi£enie 2 Izomorzmus, sledy, ´ahy, cesty, súvislos´
Pojmy na zopakovanie:
izomorzmus grafov, dokazovanie neizomorfnosti grafov
sledy, ´ahy, cesty, kruºnice
súvislos´ v grafoch
artikulácia grafu, most grafu
DMM1b
c Tomá² Madaras 2007
Úlohy v rámci cvi£enia
1
2
3
4
5
Rozhodnite, £i existuje graf s postupnos´ou stup¬ov vrcholov
(8, 8, 7, 7, 7, 6, 5, 5, 4, 4, 4, 3, 2, 1, 1). Ak áno, zostrojte ho.
Nájdite izomorzmus medzi danými dvoma grafmi:
Graf G sa nazýva autokomplementárny, ak G je izomorfný so
svojim komplementom G. Dokáºte, ºe ak G je
autokomplementárny s n vrcholmi, tak n ≡ 0 ( mod 4) alebo
n ≡ 1 ( mod 4).
Dokáºte, ºe ak |V (G)| = n a δ(G) > n2 , tak G je súvislý
graf.
Dokáºte, ºe ak ∆(G) ≤ 3 a G ∼
6 K2 , tak G má artikuláciu
=
práve vtedy, ke¤ má most. Uo¬káºte, ºe analogické tvrdenie
neplatí, ak ∆(G) ≥ 4.
DMM1b
c Tomá² Madaras 2007
Úlohy na samostatnú prácu ²tandardné
1
2
3
4
5
Nájdite najmen²í moºný príklad (t.j. s minimálnym po£tom
vrcholov) dvoch súvislých neizomorfných grafov s rovnakou
postupnos´ou stup¬ov vrcholov.
Dokáºte, ºe znázornené tri grafy nie sú navzájom izomorfné:
Dokáºte, ºe G alebo G je súvislý.
Dokáºte, ºe ak v grafe G existuje u − v -sled pre u, v ∈ V (G),
tak v G existuje aj u − v -cesta.
Ur£te po£et ´ahov d¨ºky 4 v grafe K4 .
DMM1b
c Tomá² Madaras 2007
Úlohy na samostatnú prácu nad²tandardné
1
2
3
4
5
Rozhodnite, £i existuje bipartitný graf s postupnos´ou stup¬ov
vrcholov (6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3). Ak áno, zostrojte
ho.
Nech A = {d1 , d2 , . . . , dk } je mnoºina prirodzených £ísel,
1 ≤ d1 < d2 < · · · < dk . Ukáºte, ºe A je mnoºina stup¬ov
vrcholov nejakého súvislého grafu (v grafe môºe by´ viac
vrcholov rovnakého stup¬a di ).
Nájdite v²etky autokomplementárne grafy na 4, 5 a 6
vrcholoch.
Ur£te po£et najdlh²ích ciest v grafe Kn,n .
Nech v je vrchol súvislého grafu G taký, ºe hN (v)i je súvislý.
Dokáºte, ºe graf G − v je súvislý.
DMM1b
Download

Cvičenie 2