Feladatok, amelyek gr´ afokkal oldhat´ ok meg 1) A k¨ onigsbergi hidak probl´ em´ aja (Euler-f´ ele probl´ ema) a
b
d c
A megfelel˝ o gr´ af:
d
J
J
J
a
b
J
J J c
2) Egy sz´ orakoztat´ o feladat (Hamilton-f´ ele probl´ ema) Helyezz¨ uk el az 1,2,3, . . . , 9 sz´ amokat egy k¨ or¨ on u ´gy, hogy b´ armelyik k´et szomsz´edos sz´ am o ¨ sszege ne legyen oszthat´ o sem 3-mal, sem 5-tel ´ es sem 7-tel. 1 6 8
9
2
3 9
7
2
5
8
4 4 6
5
3 7
1
1
3) M´ eg egy sz´ orakoztat´ o feladat Egy legal´ abb hat szem´elyb˝ ol a ´ll´ o csoportban mindig van h´ arom, akik k¨ olcs¨ on¨ osen ismerik egym´ ast vagy h´ arom, akik egy´ a ltal´ a n nem ismerik egym´ a st. x2
x1
x3 x4 x5 x6
Sz´ınezz¨ uk ki az xi ´es xj k¨ oz¨ otti ´elt pirossal ha xi ´es xj ismerik egym´ ast, ´es sz´ınezz¨ uk ki k´ekkel, ha nem ismerik egym´ ast. A feladat ´ıgy is megfogalmazhat´ o: ha egy legal´ abb hatpont´ u gr´ af b´ armelyik k´et pontja piros vagy k´ek ´ellel van o ¨sszek¨ otve, akkor van a gr´ afban vagy piros vagy k´ek h´ aromsz¨ og. x1 legal´ abb h´ arom ponttal ugyanolyan sz´ın˝ u ´ellel van o ¨sszek¨ otve (piros vagy k´ek). Legyenek ezek: x2 , x3 , x4 ´es legyen mindegyik ´el piros. Ha x2 ´es x3 piros ´ellel van o ¨sszek¨ otve, akkor van a gr´ afban piros h´ aromsz¨ og. Ugyanez a ´ll az x 2 ´es x4 , valamint az x3 ´es x4 pontokra is. (Ezek a piros h´ aromsz¨ ogek x1 , x2 , x3 vagy x1 , x2 , x4 vagy x1 , x3 , x4 ). Ha egyik eset sem a ´ll fenn, akkor a fenti ´elek mindegyike k´ek, teh´ at ekkor van k´ek h´ aromsz¨ og (x2 , x3 , x4 ). ´ Ertelmez´ esek A × B = {(a, b) | a ∈ A, b ∈ B} rendezett elemek halmaza A ⊗ B = {{a, b} | a ∈ A, b ∈ B vagy a ∈ B, b ∈ A} rendezetlen elemek halmaza Megjegyz´es: {a, b} nem halmaz, mivel a ´es b nem felt´etlen¨ ul k¨ ul¨ onb¨ oz˝ oek.
2
A gr´ af gr´ af G = (V, E, G), ahol V a sz¨ ogpontok (vagy cs´ ucsok vagy pontok ) halmaza, E az ´elek halmaza ´es G : E →V ⊗V Ha V = ∅, akkor u ¨res gr´ afr´ ol besz´el¨ unk. Haszn´ aljuk a k¨ ovetkez˝ o jel¨ ol´est: G = (V (G), E(G), G(G)). n = |V | a G gr´ af rendje m = |E| a G gr´ af nagys´ aga G egy (n, m) gr´ af Ha G(e1 ) = G(e2 ) akkor e1 ´es e2 p´ arhuzamos ´elek (t¨ obbsz¨ or¨ os ´elek). Ha G(e) = {a, a} aakor e hurok. Ha G(e) = {a, b}, akkor a ´es b az e ´ellel vannak o ¨sszek¨ otve, a ´es b szomsz´edosak (e illeszkedik a-hoz ´es b-hez) Az a ´es b sz¨ ogpontokat o ¨sszek¨ ot˝ o ´elek halmaza: G −1 (a, b) = {e ∈ E | G(e) = {a, b}}. Legyen x a G egy sz¨ ogpontja. sz¨ ogpontok halmaza:
NG (x) vagy N (x) az x-szel szomsz´edos
NG (x) = {y ∈ V (G) | ∃e ∈ E(G), G(e) = {x, y}} vagy NG (x) = {y ∈ V (G) | G −1 (x, y) 6= ∅.} A G gr´ afban az x sz¨ ogponthoz illeszked˝ o (nem hurok) ´elek halmaza: IG (x) = {e ∈ E(G)|∃y ∈ V (G), y 6= x, G(e) = {x, y}} Az x-hez illeszked˝ o hurok´elek halmaza: LG (x) = {e ∈ E(G)|G(e) = {x, x}} Az x sz¨ ogpont foka, amelynek jel¨ ol´ese ϕ(x), az x-hez illeszked˝ o ´elek sz´ ama (A hurkot k´etszer sz´ am´ıtjuk). ϕ(x) = |IG (x)| + 2|LG (x)|. Ha ϕ(x) = 0, akkor x izol´ alt sz¨ ogpont. Ha ϕ(x) = 1, akkor x v´egpont vagy lev´el. A t¨ obbsz¨ or¨ os ´el ´es hurok n´elk¨ uli gr´ afot egyszer˝ u gr´ afnak nevezz¨ uk. A G egyszer˝ u gr´ afban |G −1 (a, b)| ≤ 1 minden a, b ∈ V ´es G −1 (a, a) = ∅ minden a ∈ V , ´ıgy G(e) = {a, b} helyett haszn´ alhatjuk az {a, b} jel¨ ol´est az egyetlen ´elre. Ebben az esetben a gr´ af jel¨ ol´ese: G = (V, E). 3
Az egyszer˝ u gr´ afban az x foka (ϕ(x) vagy ϕG (x) egyenl˝ o az NG (x) halmaz elemsz´ am´ aval:: ϕ(x) = |NG (x)|. P´ eld´ ak. # 1m aa ea 5 a a a m 2 G1 gr´ af e1 e2 e3 e4 e6 5m m 4m e7 3 " V (G1 ) = {1, 2, 3, 4, 5}, E(G1 ) = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }, G(e1 ) = G(e2 ) = G(e3 ) = {1, 4}, G(e4 ) = {2, 4}, G(e5 ) = {2, 1}, G(e6 ) = {2, 3}, G(e7 ) = {3, 4}. deg(1) = 4, deg(2) = 3, deg(3) = 2, deg(4) = 5, deg(5) = 0. a b
c
e
d
G2 egyszer˝ u gr´ af
V (G2 ) = {a, b, c, d, e}, E(G2 ) = {a, c}, {a, d}, {b, c}, {b, e}, {b, d}{e, d}
Ha egy gr´ afban minden sz¨ ogpont foka ugyananyi (r), akkor a gr´ af regul´ aris vagy r-regul´ aris.A k¨ o vetkez˝ o gr´ af (7,14) 4-regul´ aris gr´ af.
4
Ha egy egyszer´ u gr´ afban b´ armelyik k´et sz¨ ogpont szomsz´edos, akkor az teljes gr´ af. Az n sz¨ ogpont´ u teljes gr´ af jel¨ ol´ese: Kn . j j
j
K1
K2
j
j
j
K3
j
j j
K4
j j
j
j
K5
j
j
A G = (V , E) egyszer˝ u gr´ af komplementuma a G = (V, E) egyszer˝ u gr´ afnak, ha V = V ´es E = {a, b} | {a, b} 6∈ E . 1m
5m
2m
4m
3m
G
1m 2m B B 5m BB 3m 4m G
Ha a G gr´ af n sz¨ ogpont´ u, akkor E(G) ∪ E(G) = E(Kn ). A G1 ´es G2 egyszer˝ u gr´ afok izomorfak ha l´etezik egy φ : V (G1 ) → V (G2 ) bijekti´ıv f¨ uggv´eny u ´gy hogy ha {a, b} ∈ E(G1 ), akkor {φ(a), φ(b)} ∈ E(G2 ). Tetsz˝ oleges gr´ afokra is ´ertelemzhetj¨ uk az izomorfizmust. A G 1 ´es G2 gr´ afok izomorfak, ha l´etezik agy φ : V (G1 ) → V (G2 ) bijekt´ıv f¨ uggv´eny, amelyre |G1−1 (a, b)| = |G2−1 (φ(a), φ(b))| minden a, b ∈ V (G1 ). P´ elda izomorf gr´ afokra
5
1
2
3
a
b
c
x6
x5
G1
x1
x4 G2
x2 x3
A φ f¨ oggv´eny a k¨ ovetkez˝ o: x φ(x)
1 x1
2 x5
3 x3
a x2
b x6
c x4
Izomorf gr´ afokban ϕ(x)=ϕ φ(x) minden x ∈ V (G1 ). Ir´ any´ıtott gr´ af
ir´ any´ıtott gr´ af ~ = (V, E, G), ~ ahol G V sz¨ ogpontok (vagy cs´ ucsok vagy pontok ) halmaza, E ir´ any´ıtott ´elek halmaza ´es G~ : E → V × V e1 R e2 a b A A e3A e4 eA5 A A U A e U A e 6 7 e c d e8 * A fenti ir´ any´ıtott gr´ afban az e1 ´es e2 p´ arhuzamosak, de e6 ´es e8 nem. ~ egy ir´ Legyen G any´ıtott gr´ af. ~ | G~−1 (x, y) 6= ∅} N be (y) = {x ∈ V (G) ~ G
ki ~ ~ −1 (y, z) 6= ∅} NG ~ (y) = {z ∈ V (G) | G
Az x be-foka az x-be befut´ o ´elek sz´ ama, az x ki-foka az x-b˝ ol kifut´ o ´elek sz´ ama. Egyszer˝ u ir´ any´ıtott gr´ afokra: Az x be-foka: ϕbe (x) = |N be (x)| 6
´es az x ki-foka: ϕki (x) = |N ki (x)|.
Gr´ afok ´ abr´ azol´ asa 1) – ´ertelmez´es szerint 2) – geometriai a ´br´ azol´ as 3) – szomsz´eds´ agi m´ atrix G = (E, V, G), V = {x1 , x2 , . . . , xn } A = (aij )i,j=1,n szomsz´eds´ agi m´ atrix, ahol −1 |G (xi , xj )| if i 6= j aij = 2|G −1 (xi , xj )| if i = j P´elda:
x1
J
J
J
x2
ϕ(xi ) =
n X
x3
J
0 1 A= 1 1
J J x4
1 0 2 0
1 2 0 2
1 0 2 0
aij , minden i = 1, 2, . . . , n
j=1
Az egyszer˝ u gr´ af szomsz´eds´ agi m´ atrix´ aban csupa 0 ´es 1 szerepelnek. Ir´ any´ıtott gr´ af eset´eben a defin´ıci´ o ugyanaz. 4) – illeszked´esi m´ atrix G = (E, V, G), V = {x1 , x2 , . . . , xn }, E = {e1 , e2 , . . . , em } B = (bij )i=1,n,j=1,m , 1 2 bij = 0
ha xi illeszkedik ej -hez ´es ej nem hurok ha xi illeszkedik ej -hez ´es ej hurok ha xi nem illeszkedik ej -hez
7
J
J e1 e2 eJ 3
J
J J
x1
3 e7
2
e6
x
e4
e5
x
x1 B = x2 x3 x4
x4
e1 1 1 0 0
e2 1 0 1 0
e3 1 0 0 1
e4 0 1 1 0
e5 0 0 1 1
e6 0 1 1 0
e7 0 0 1 1
∗
x1
x3
x3
∗
5) – list´ ak a) x1 x2 x3 x4
x2 x1 x1 x1
x3 x3 x2 x3
x4 x3 x2 x3
x4
x4
–l´ ancolt list´ ak b) x2
x3
x4
∗
x3 4
x4 7
x1 12
x1
x3
x3
∗
x1
x2
x2
x4
x4
c) x2 1
x3
x3
x1
x2
Tulajdons´ agok: 1) G = (V, E, G), |E(G)| = m, akkor
x2
x4
x4
x1
X
ϕ(x) = 2m.
x3
x3
x∈V (G)
2) A p´ aratlan fok´ u sz¨ ogpontok sz´ ama p´ aros. 3) Minden egyszer˝ u gr´ afban van legal´ abb k´et azonos fok´ u sz¨ ogpont. Bizony´ıt´ as a skatulyaelvvel. Ha |V (G)| = n, akkor a foksz´ amok csak 0, 1, . . . , n − 2 vagy 1, 2, . . . , n − 1 lehetnek.
8
∗
