Debreceni Egyetem
Természettudományi Kar
Matematikai Intézet

Szakdolgozat

Gráfok címkézéseinek
vizsgálata
készítette:

Juhász Gyula

témavezet®: Dr. Tengely Szabolcs

Debrecen, 2016

Tartalomjegyzék

Tartalomjegyzéki

1 Bevezet®

3

2 Alapvet® deníciók és tételek

5

3 Graceful gráfok és graceful címkézés

11

2.1. A gráfok, fa gráfok és páros gráfok . . . . . . . . . . . . . . . . . .
3.1. Graceful címkézés, illetve címkézés teljes gráfok és fák esetén

5. . . 114 Különleges gráfok, konstrukciók és Sage implementáció

19

Irodalomjegyzék

47

4.1.
4.2.
4.3.
4.4.

Graceful double-wheel gráf konstrukciója . . . . . . . . . . . . . . .
Graceful caterpillar gráf konstrukciója . . . . . . . . . . . . . . . .
Graceful n-szeresen összetett teljes páros gráf konstrukciója . . . .
Graceful pendant gráf konstrukciója . . . . . . . . . . . . . . . . .

i

19
30
32
37

Köszönetnyilvánítás

Köszönetet szeretnék mondani Dr. Tengely Szabolcs témavezet®mnek, akinek
segítsége nélkül nem jöhetett volna létre ezen dolgozat. Valamint köszönettel
tartozom családomnak és barátaimnak, akik mindig mellettem voltak és támogattak.

11. Bevezet®

A matematikában, azon belül a gráfelméletben a mai napig még mindig rengeteg amegválaszolandó kérdés. Ilyen kérdésekre bukkanunk, hogyha el kezdjük vizsgálni
a gráfok címkézéseit, f®leg a 20. század egyik címkézési problémáját, a graceful
címkézést.
Ezeket a gráfokat már több mint 40 éve vizsgálják, amióta 1967-ben Alexander
Rosa publikálta [11]. Egy gráfot gracefulnak nevezünk, ha a csúcsait fel tudjuk úgy
címkézni egész {0, . . . , e} értékekkel, hogy minden egyes élnek különböz® legyenaz az értéke, amit a végpontok abszolút különbségéb®l számolunk ki.
Ez egy nagyon szép és egyben érdekes címkézési formula, ami felvet néhány
kérdést. Vajon minden gráfnak létezik graceful címkézése? Van olyan gráfosztály,
amire nem teljesül? Tudunk-e olyan algoritmust adni, amely bizonyos gráfok esetén, a csúcsok növelésével is helytálló, azaz ha egy három csúcsú fa gráfra igazaz állítás, akkor az n csúcsúra is igaz lesz? Ezeket a kérdéseket tanulmányozzák,
tanulmányozták a gráfelméletbe, de mire is jó, hogy egy gráfnak létezik graceful
címkézése?
A graceful gráfokat f®leg a kriptográában használják, de a csillagászatban, akristálytanban vagy a röntgennél is felhasználják ®ket [5].
Viszont a gráfelmélet ezen részén sokan próbálkoznak új gráfok létrehozásábanis, így megismerkedhetünk a double-wheel gráfokkal vagy a caterpillar gráfokkal,
amik például úgy keletkeztek, hogy próbálták a fa gráfokról belátni, hogy graceful, de mivel nem tudták belátni, ezért a fa gráfokat el kezdték osztályozni. Ígyrengetek osztályról tudunk a fák esetén beszélni, például a caterpillar gráfokról,
super-caterpillar gráfokról, spider gráfokról vagy lobster gráfokról.
Így a dolgozat célja az, hogy bemutassam a graceful címkézést, a fa gráfok bizonyos
osztályait, rájuk vonatkozó tételeit, illetve különleges graceful gráfok címkézéseit.

32. Alapvet® definíciók és tételek

A legels® fejezetben néhány alapvet® kérdésre szeretnék választ adni, mint például
mi az a gráf. Ezenkívül néhány alapvet® deníciót, tételt és a bizonyítását is szeretnék ismertetni, amiket a graceful gráfok esetén érdemes tudni, és amik közül
használni is fogok egy párat a graceful gráfok ismertetésekor.

2.1. A gráfok, fa gráfok és páros gráfok

2.1.1. Deníció. Legyen V 6= ∅ és E véges halmazok, ϕ : E → P1,2 (V ) == {A ⊆ V ||A| = 1 vagy 2}.
Ekkor G = (V, E, ϕ)-t irányítatlan gráfnak, V elemeit a G gráf csúcsainak, E
elemeit a G gráf éleinek nevezzük. Ha ϕ(e) = {v, w}, ahol e ∈ E , akkor azt
mondjuk, hogy a v és w az e él végpontjai.
Ha E = ∅, akkor a gráfot üresgráfnak nevezzük.

2.1.2. Deníció. Legyen G = (V, E, ϕ) egy véges gráf. Ha |ϕ(e)| = 1, akkore ∈ E -t hurokélnek nevezzük. Az e1 , e2 ∈ E párhuzamos élek, ha ϕ(e1 ) = ϕ(e2 ).
Ha a gráf nem tartalmaz sem hurokélt és párhuzamos életeket sem, akkor a G
gráfot egyszer¶nek nevezzük.

2.1.3. Deníció. Egy G = (V, E, ϕ) véges gráf, egy v ∈ V (G) fokszámán a v-re
illeszked® élek számát értjük. Ha a gráfban szerepel hurokél is, azokat a fokszám
számoláskor 2-szer számoljuk. Jele: d(v).

2.1.1. Tétel (Kézfogási-tétel). Legyen G = (V, E, ϕ) véges gráf. Ekkor
Xd(v) = 2 · |E(G)|.

v∈V (G)

2.1.1. Megjegyzés. Azaz, a fokszámok összege ugyanannyi, mint az élek számánaka duplája.

Bizonyítás. Egy élt a fokszámösszegbe 2-szer számolunk bele, ugyanígy számoljuk
mindkét végpontjánál is. Ha a gráf tartalmaz hurokélt is, akkor is igaz a tétel.

1. Következmény. Egy G gráfban a fokszámok összege mindig páros.
5

6

FEJEZET 2.

ALAPVET DEFINÍCIÓK ÉS TÉTELEK

2. Következmény. Egy G gráfban a páratlan fokú csúcsok száma páros.
Bizonyítás. Valóvan, av∈V (G) d(V ) összeget fel lehet bontani két külön részre,a páros és a páratlan fokú csúcsokra. Azaz,
X
X
X
d(V ) = 2·|E|.
d(V )+
d(v) =v ∈ V (G)Pv ∈ V (G) d(V ) ≡ 0 (mod 2)v ∈ V (G) d(V ) ≡ 1 (mod 2)

Ebb®l azonnal látszik, hogy a jobb oldalon az els® d(V ) tagjainak a száma páros, ésmivel páratlan sok páratlan szám összege páratlan, ezért a második d(V ) tagjainak
a száma is csak páros lehet.

2.1.4. Deníció. Legyen G = (V, E, ϕ) véges gráf. Ha a gráf egyszer¶ és bármely
két különböz® csúcsa szomszédos egymással, akkor a gráfot teljesnek nevezzük.
Jele: Kn .
2.1.2. Tétel. Legyen G = (V, E, ϕ) egy n csúcsú teljes gráf. Ekkor éleinek száma:n · (n − 1).
2

Bizonyítás. Egy n csúcsú teljes gráfban minden csúcs fokszáma n − 1, így a fokszámok összege n · (n − 1). Így a kézfogási-tétel szerint az élek száma n·(n−1).
2

2.1.5. Deníció. Legyen G = (V, E, ϕ) egyszer¶, véges gráf. Ekkor G komplementere az a G véges, egyszer¶ gráf, amire az teljesül, hogy V (G) = V (G) és
G-ben két csúcs pontosan akkor szomszédosak, ha G-ben nem szomszédosak.
2.1.2. Megjegyzés. Tehát a G és G teljes gráfot alkot együtt.

2.1.6. Deníció. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = n+1 és |E(G)| = n.

Ekkor (v0 , e1 , v1 , e2 , v2 , . . . , vn−1 , en , vn )-t sétának nevezzük,
ha v0 , v1 , v2 , . . . , vn−1 , vn ∈ V , e1 , e2 , . . . , en ∈ E és ϕ(ei ) = {vi−1 , vi }, ahol
i = 1, . . . , n. A séta nyílt, ha v0 6= vn , ellenben zárt, ha v0 = vn . Illetve a séta
hossza, a benne szerepl® élek száma.

2.1.7. Deníció. Egy sétát vonalnak nevezünk, ha a benne szerepl® élek külön-böz®ek. Egy séta út, ha nincs benne ismétl®d® csúcs és él. Illetve egy séta kör,ha zárt és nincs benne ismétl®d® él és csúcs sem, kivéve a kiinduló és az utolsó
csúcs egyezését.

2.1.8. Deníció. Egy G = (V, E, ϕ) véges gráf összefügg®, ha bármely két különböz® csúcsa között vezet út.

2.1.9. Deníció. Legyen G = (V, E, ϕ) véges, összefügg® gráf. A v, w ∈ V (G), v 6=
6= w csúcsok távolságán az ®ket összeköt® út hosszát értjük. Továbbá v és v távolsága legyen 0. Jele: d(v, w).

2.1.

A GRÁFOK, FA GRÁFOK ÉS PÁROS GRÁFOK

7

2.1.3. Tétel. Legyen G = (V, E, ϕ) véges, összefügg® gráf.
i ∀ v, w ∈ V (G) : d(v, w) ≥ 0 és d(v, w) = 0 ⇐⇒ v = w.
ii ∀ v, w ∈ V (G) : d(v, w) = d(w, v).
iii ∀ v, w, z ∈ V (G) : d(v, w) + d(w, z) ≥ d(v, z).
Bizonyítás. A bizonyítás során négy esetet különböztetünk meg.
1.eset Ha v = w,akkor d(v, v) + d(v, z) = d(v, z).
2.eset Ha w = z ,akkor d(v, z) + d(z, z) = d(v, z).
3.eset Ha v = z ,akkor d(z, w) + d(w, z) = 2 · d(w, z) ≥ 0 = d(w, z).
4.eset Ha v, w, z páronként különböz® csúcsok, akkor vegyük a v és w között egyd(v, w) hosszú utat, ugyanígy w és z között egy d(w, z) hosszú utat. F¶zzükössze ezt a két utat, így kapunk v és w között egy d(v, w) + d(w, z) hosszú
sétát. Ebb®l a sétából hagyjuk el az ismétl®d® éleket. Ekkor v és z között
legfeljebb egy d(v, w) + d(w, z) hosszú utat kapunk. Ekkor a v és z közötti legrövidebb út hossza, a d(v, z), ami legfeljebb d(v, w) + d(w, z) hosszú
lehetséges.

2.1.10. Deníció. Legyen G = (V, E, ϕ) véges gráf. A G gráfot fának nevezzük,

ha összefügg® és körmentes. Ha a G gráf csak összefügg®, abban az esetben agráfot erd®nek nevezzük.

2.1.4. Tétel. Minden fa és minden erd® egyszer¶ gráf.
Bizonyítás. Legyen G = (V, E, ϕ) véges gráf. Ha G fa, akkor körmentes, így nem
tartalmaz egy és két hosszú kört, ezáltal nincs benne sem hurokél, sem párhuzamosél.

2.1.5. Tétel. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf, |V (G)| ≥ 2. A G gráf,
pontosan akkor fa, ha G bármely két különböz® csúcsa között pontosan egy út vezet.
Bizonyítás. El®ször legyen G egy fa. Ekkor G összefügg®, így bármely két különböz® csúcsa között legalább egy út vezet. Tegyük fel, hogy v ,w ∈ V (G) különböz®
csúcsok között legalább két út vezet. Ez a két út valahol szétágazik, majd újraösszeér. A két útszakasz egy kört alkot, ami nem lehetséges fa esetén.
Tegyük fel, most G-ben bármely két különböz® csúcs között pontosan egy út vezet,
így azonnal következik, hogy G összefügg®. Ha G-ben lenne kör, akkor annak két
csúcsa között két út is vezetne a kör egyik illetve másik oldalán.

8

FEJEZET 2.

ALAPVET DEFINÍCIÓK ÉS TÉTELEK

2.1.6. Tétel. Legyen G = (V, E, ϕ) véges gráf. Ha G fa, |V (G)| ≥ 2, akkor G-ben
van legalább két els®fokú csúcs.

Bizonyítás. Vegyük a G gráfban a leghosszabb utat. A körmentesség miatt v0
nem szomszédos sem v2 , . . . , vn -nel. S®t v0 nem szomszédos az úton bármelyik
kívül elhelyezked® csúccsal sem, mert elé rakva, még hosszabb utat kapnánk, ígya v0 egyetlen szomszédja v1 , így d(v0 ) = 1. Hasonlóan alakul, hogy d(vn ) = 1.

2.1.7. Tétel. Legyen G = (V, E, ϕ) véges gráf. Ha G fa, akkor |V (G)| == |E(G)| + 1.

Bizonyítás. A tételt |V (G)| szerinti teljes indukcióval látjuk be. |V (G)| = 1 esetén|E(G)| = 0, így |V (G)| = |E(G)| + 1, ami igaz.
Tegyük fel, hogy |V (G)| ≥ 2 és G-nél kevesebb csúcsú fára igaz az állítás. Ekkor
létezik olyan v csúcsa, ami els®dleges, azaz ∃ v ∈ V (G) : d(v) = 1. Ekkor G − v
is fa, mert kevesebb csúcsa van, így alkalmazható rá a felvetés.
|V (G − v)| = |E(G − v)| + 1 → |V (G)| − 1 = (|E(G)| − 1) − 1.
Azaz |V (G)| = |E(G)| + 1.

2.1.11. Deníció. Legyen G = (V, E, ϕ) véges gráf. A G gráf feszít® fája vagy
feszít® erdeje olyan feszít® részgráf, ami fa vagy erd®.

2.1.8. Tétel. Legyen G = (V, E, ϕ) véges gráf. A G gráfban pontosan akkor vanfeszít® fa, ha a gráf összefügg®.

Bizonyítás. El®ször tegyük fel, hogy G-ben van feszít® fa, akkor a feszít® fában
is van bármely csúcsból, bármely csúcsba vezet® út, így G-ben is, tehát G összefügg®.
Tegyük fel most, hogy G összefügg®. Ha vannak töröljük a hurokéleket, úgy hogya gráf még összefügg® maradjon. Ezt addig folytatjuk míg lehet. Így a végs® gráf
minimálisan összefügg®, tehát fa. Mivel élek törlésével jutottunk ide, ezért feszít®
gráf, és így feszít® fa.

2.1.9. Tétel. Minden gráfban van feszít® erd®.
Bizonyítás. Az el®z® tétel miatt minden komponensnek van feszít® gráfja, amikígy együtt a gráf feszít® erdejét alkotják.

2.1.12. Deníció. Egy G véges gráfot páros gráfnak nevezünk, ha ∃ A, B ⊆⊆ V (G), hogy A 6= ∅, B 6= ∅, A ∩ B = ∅, A ∪ B = V (G) és G mindenélének az egyik végpontja A-beli, másik B -beli. Ezeket az A és B osztályokat
csúcsosztályoknak nevezzük.

2.1.10. Tétel. Minden legalább két csúcsú erd® páros gráf.

2.1.

A GRÁFOK, FA GRÁFOK ÉS PÁROS GRÁFOK

9

Bizonyítás. El®ször tegyük fel, hogy az erd®k összefügg®k, tehát fák. Ezt csúcsok
száma szerinti teljes indukcióval lehet bebizonyítani. Ha |V (G)| = 2, akkor az
egyik csúcs legyen A-beli, másik B -beli. Ekkor ez páros gráf.
Tegyük fel, hogy |V (G)| ≥ 3 és az ennél kisebb csúcsokra is igaz az állítás. Ekkor
G-nek van els®fokú csúcsa, legyen ez v . Alkalmazzuk az indukciós feltevést (G−v)re. Ekkor G − v páros gráf, tehát csúcsai jól osztályozhatóak. Ha v szomszédja
A-beli, akkor v -t vegyük bele a B csúcsosztályba. Ha v egyetlen szomszédja
B -beli, akkor tegyük bele v -t az A csúcsosztályba. Ezzel megadtunk a G fa csúcsainak egy megfelel® osztályozását. Így a G gráf páros gráf.
Tegyük fel, hogy a G erd® nem összefügg®. Ha G üres gráf, akkor kerüljön azegyik csúcs az egyik csúcsosztályba, míg a másik csúcs a másik csúcsosztályba.
Ha G nem üres, akkor G-nek van legalább két csúcsú komponense. A legalább
két csúcsú komponensekre alkalmazható a bizonyítás el®z® része, így azok csúcsai megfelel®en osztályozhatóak. Ezen osztályozások egyesítésével a legalább két
csúcsú komponensek alkotta részgráf csúcsai osztályozva vannak. A kimaradó
esetleges izolált csúcsokat tegyük bele valamelyik csúcsosztályba.

2.1.11. Tétel. Legyen G = (V, E, ϕ) véges gráf, ahol |V (G)| ≤ 2. A G gráf,
pontosan akkor páros gráf, ha benne minden kör páros hosszúságú.

Bizonyítás. Legyen G egy páros gráf, ahol jelölje A és B a csúcsosztályokat. Ekkor
egy köre felváltva tartalmaz A és B -beli csúcsokat, így a hossza páros lesz.
Legyen most G egy gráf, ahol |V (G)| ≥ 2, amiben minden kör páros hosszúságú
is. Vegyük a G gráf egy feszít®erdejét. Ami a fenti tétel alapján páros gráf, így a
csúcshalmazát megfelel® módon lehet osztályozni. Így az élekre teljesül az, hogy
az egyik csúcs az egyik csúcsosztályba, míg a másik csúcs a másik csúcsosztályba
található. Legyen ezután e ∈ E(G), ami nincs a feszít®erd®ben. Tekintsük Gnek azt a komponensét, amihez e tartozik. Ennek a komponensnek feszít®gráfja
a fenti feszít®erd® egyik komponense. Ez a fa maximálisan körmentes, ezért ebehúzásával keletkezik benne kör. Mivel minden kör páros hosszúságú és a többi
éle feszít®gráfban van, ezért a kör csúcsai felváltva A és B -beliek, ezért e egyik
végpontja A-ban van, míg másik végpontja B -ben van. Tehát G páros gráf.

2.1.13. Deníció. Egy páros gráfot, A és B csúcsosztályokkal teljes páros gráf-

nak nevezünk, ha egyszer¶ és ∀ A-beli csúcs szomszédos ∀ B -beli csúccsal. Ha|A| = m és |B| = n, akkor a teljes páros gráfot Km,n -nel jelöljük.

3. Graceful gráfok és graceful
címkézés

A bevezet® deníciók és tételek után, végre ebben a fejezetben választ kaphatunk,hogy milyen gráfok ezek a bizonyos graceful gráfok, mi a lényege a graceful
címkézésnek, illetve hogy milyen alapvet® feltételeknek kell teljesülni-e ahhoz,
hogy egy gráf graceful legyen. Továbbá ismertetni fogom a graceful gráfok egyik
legfontosabb sejtését is.

3.1. Graceful címkézés, illetve címkézés teljes gráfok és
fák esetén

A graceful címkézés Solomon W. Golomb nevéhez f¶z®dik, de els®ként Alexander
Rosa cikkében olvashatunk a graceful gráfok problémáiról, de Rosa cikkében egy
másik nevet használ ezekre a címkézésekre, mégpedig a β -címkézést.

3.1.1. Deníció. Legyen G = (V, E, ϕ) véges gráf. Ekkor a G gráf csúcsainak

a címkézésén, egy olyan bijektív Ψ leképezést értünk, ahol a V (G) elemeit, nem
negatív egész számokkal feleltetjük meg. Hasonlóan beszélhetünk így élek címkézéseir®l is.

3.1.2. Deníció. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = n, |E(G)| = m,v, w ∈ V (G) és az v , w csúcsokat a e ∈ E(G) él köti össze. A G gráfnak létezik
graceful címkézése, ha van olyan V (G) → {0, . . . , m} injektív függvény, hogy ∀ e:|f (v) − f (w)|különböz®. Ekkor E(G) = {1, 2, . . . , m}.

3.1.1. Lemma. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = m és |E(G)| = n. Ha
a G gráf gracful, akkor m ≤ n + 1.
3.1.1. Tétel. Legyen G = (V, E, ϕ) véges, teljes gráf és |V (G)| = n. Ha n == 2,3,4, akkor a G gráfnak van graceful címkézése. Ha n > 4, akkor a G gráfnak

nincs graceful címkézése.

11

12

FEJEZET 3.

GRACEFUL GRÁFOK ÉS GRACEFUL CÍMKÉZÉSBizonyítás. El®ször legyen |E(G)| = m, ami teljes gráf esetén m = n2 ≥≥ 10. Indirekt, tegyük fel, hogy a G gráfnak van graceful címkézése. Legyen
V (G) ⊆ {0, 1, . . . , m}, továbbá legyen az éleknek a címkéi különböz® egész számok
1-tól m-ig.
Jelöljük a G gráfnak a 0 és az m csúcs címkéit összeköt® élét m-mel (|m−0| = m).
Annak érdekében, hogy egy él címkéje m − 1 legyen, vagy 1-nek vagy m − 1-nek
kell lenni-e a csúcs címkézésének (|(m − 1) − 0 = m − 1| vagy |m − 1| == m − 1). Így bármely G graceful gráf esetén, amelynek m éle van, úgy minden
ai csúcs címkéje kicserélhet® m − ai -val, úgy hogy az élek címkézése nem változik.
Így az általánosság megszorítása nélkül meg tudjuk változtatni az 1 csúcs címkéjét
az m − 1 csúcs címkéjével.
Jelölje a G gráfnak az egyik él címkéjét m − 2. Ez az él címke pedig, az m − 1
és az m csúcscímkézett csúcsokat összeköt® élnek a címkéje lesz. (|(m − 1) − 1| =m − 2). Ha két él címkézés is 1 lenne, akkor az egyik a 0 és az 1 csúcsok között
helyezkedne el, míg a másik az m és az m − 1 csúcsok között. Ha egy csúcs
címkéje 2 lenne , akkor az m − 2 él kötné össze ®t az m csúcs címkével jelölt
csúccsal (|m − 2| = m − 2), de újra lenne 2 olyan él címke, aminek a címkéje 1
lenne, az egyik a 0 és az 1 csúcs között lenne, a másik az 1 és a 2 csúcs között
szerepelne. Ekkor a csúcsok címkéi 0, 1, m − 2 és m, míg az élek címkéi 1, 2,
m−3, m−2, m−1 és m. Annak érdekében, hogy egy él címkéje m−4 legyen, kellhogy legyen egy negyedik csúcs címke. Legyen ezért a következ® csúcs címkéje 2.
Ekkor azonban lenne két olyan él címke, aminek a távolsága 2 lenne, ez a két él
pedig a 2 és a 0 , illetve az m és az m − 2 él közötti élek lennének. Ha n = 5,
akkor következ®t kell tenni. (Pontosan 5 csúcs címkénk van). Azonban, ebben
az esetben m = 10, és így lesz m − 6 = 4 él címke, így van olyan él címkézés,ahol két különböz® él címkéje megegyezik. Így n = 5 esetén nincs jó címkézés.
Most vizsgáljuk meg azokat az eseteket, ahol n > 5. Ebben az esetben m > 10 és
4 < m − 6, így ilyenkor nem lesz él ismétl®dés. Ekkor azonban a következ® csúcs
címkéink lesznek: 0, 1, 4, m − 2, m. Illetve a következ® él címkéink lesznek: 1, 2,
3, 4, m − 6, m − 4, m − 3, m − 2, m − 1, m.
Azonban nincs olyan módszer, ahol az él címkéje m − 5 legyen, mert minden
választás szerint, kapunk olyan élcímkézést, amely legalább egy csúcscímkézést
tartalmaz, amit viszont így már nem lehet használni. Adjuk hozzá az m − 5 csúcs
címkét és az m − 6 él címkét. Továbbá adjuk hozzá az m − 4 csúcs címkét, amib®laz él az m − (m − 4)-b®l adódik, azaz 4 lesz. Így az m − 1 csúcs címke esetén, az él
az (m − 1) − 1-b®l adódik, ami m − 2 lesz. Nem lehet már hozzárendelni a 3 csúcs
címkét, amib®l az él a 3 − 1 = 2 adódna. Végül rendeljük az utolsó csúcshoz az
5 csúcs címkét. Ez viszont nem lehetséges, mivel két olyan élt kaptunk, aminek
a felirata 1 lesz. Így egy ellentmondást kaptunk, így n ≥ 5 esetén a G gráf már
nem lesz graceful.

3.1.

GRACEFUL CÍMKÉZÉS, ILLETVE CÍMKÉZÉS TELJES GRÁFOK ÉS FÁK

ESETÉN13

3.1.2. Tétel. Legyen G = (V, E, ϕ) véges gráf, |E(G)| = m. Ha a G gráfban vanzárt Euler-vonal és m ≡ 1 (mod 4) vagy m ≡ 2 (mod 4), akkor a G gráf nem
graceful gráf.

Bizonyítás. Tegyük, fel indirekt, hogy a G gráf mégis graceful, úgy hogy tartalmaz
zárt Euler-vonalat és m ≡ 1 (mod 4) vagy m ≡ 2 (mod 4). Összegezzünk minden
PmPegyenl® (m+1)·mei él címkére. Ekkor m.
i=1 i, ami
i=1 ei =2Pm
Ha m ≡ 1 vagy m ≡ 2 (mod 2), akkor
e
≡
1
(mod
2). Azonban, egy
i=1 itetsz®legesen körön, mondjuk v1 , v2 ,. . . , vn , v1 , az élek címkézése |v1 − v2 | , . . . ,|vm −v1 |, és mivel y abszolút értéke (mod 2)-ben kongruens y -nal, ezért az abszolút
Pértéket elhagyhatjuk, így m−1
i=1 |vi − vi+1 | + |vm − v1 | kapjuk. Amit, ha tovább
Pm−1
számolunk i=1 (vi − vi+1 ) + vm − v1 ≡ 0 (mod 2) kapjuk. Ami ellentmondás,P
mert mi=1 ei ≡ 1 (mod 2), ami állításunkat igazolja.

3.1.3. Tétel. Legyen G = (V, E, ϕ) véges gráf. Ha a G gráf út gráf, akkor a G
gráf graceful.

Bizonyítás. A bizonyítás konstrukcióval történik, azaz egy címkézést adunk, hogyan
lehet egy G gráfot, ami út gráf, elcímkézni úgy, hogy graceful legyen. Legel®ször
is a gráf legels® csúcsának a címkéje legyen 0 és minden más páratlan csúcsnak acímkéjét 1-gyel növeljük. A második csúcsnak a címkéje legyen s és minden más
páros csúcsnak a címkéb®l vonjunk ki 1-et. Így s + 1 csúcsúnk van, és az {0, 1,. . . ,s + 1} halmazból felcímkézzük a csúcsokat. Így az els® esetben {0, 1, . . . , 2s },míg a második esetben { (s+2)
2 , . . . , s} lesz a két halmaz, amib®l a csúcsokat felcímkézzük. Ez a konstrukció helyes, így az állításunkat beláttuk.
Amikor Alexander Rosa el kezdte vizsgálni a gráfoknak a graceful címkézéseit,
felvet®dött az a kérdés, hogy vajon minden gráf graceful-e, vagy vannak-e a gráfoknak egy olyan osztálya, ami biztosan az. Ringel és Kotzig is Rosa után el
kezdett vizsgálódni a graceful "jelenséggel" és kialakult egy sejtés bennük.
3.1.1. Sejtés (Ringel-Kotzig sejtés). Minden fának létezik graceful címkézése.
Sok ember próbálkozott ezt a sejtést belátni, de ez az 50 éves probléma még
a mai napig is csak egy sejtés maradt. Azonban Rosa és társai, ezen sejtés
belátásához el kezdték a fa gráfokat még jobban elemezni. Így elkezdték a fákat
bizonyos tulajdonságok alapján külön osztályokba sorolni, így beszélhetünk ma
már csillag gráfokról, caterpillar gráfokról, super-caterpillar gráfokról, lobster gráfokról, spider gráfokról.

3.1.3. Deníció. Egy gráf levelén, olyan csúcsot értünk, amelynek a fokszáma
pontosan 1.

3.1.4. Deníció. Az út gráf, olyan speciális fa gráf, amelynek pontosan két
csúcsa levél.

14

FEJEZET 3.

GRACEFUL GRÁFOK ÉS GRACEFUL CÍMKÉZÉS

3.1.5. Deníció. A caterpillar fa gráf, olyan speciális fa gráf, amely egy központiútból áll és tetsz®leges számú levél csatlakozik az úthoz.

3.1.1. Megjegyzés. A caterpillar gráf deníciójából, azonnal következik, hogy |V (G)| ≥≥ 2. Ha |V (G)| ≥ 3, akkor a caterpillar gráfnak létezik központi útja. Illetve, habizonyos leveleket eltávolítunk a gráfból, akkor egy út gráfot kapunk.
A most következ® tétel, a caterpillar gráfok graceful tulajdonságáról szól, amita kés®bbiek folyamán felhasználok a graceful caterpillar gráf megalkotásához.

3.1.4. Tétel. Minden caterpillar fa gráfnak van graceful címkézése.
Bizonyítás. Legyen G egy caterpillar gráf, ahol |V (G)| = n. Ha n ≤ 2, akkor Gútjának a hossza 1, ami caterpillar gráf. Így feltehetjük, hogy a csúcsok száma
nagyobb vagy egyenl® háromnál, és továbbá feltesszük, hogyha a G gráfból leveleket törlünk, akkor az U utat kapjuk meg, ami v0 , v1 , . . . , vk . Mivel n ≥ 3, ezért
az U utunk legalább egy csúccsal rendelkezik. Továbbá válasszuk szét a csúcsokat
az alábbiak szerint:

X = {x | x ∈ V (G), d(v0 , x) ≡ 0 (mod 2)}
Y = {y | y ∈ V (G), d(v0 , y) ≡ 1 (mod 2)} = V (G) − X.
Ez azt jelenti ,hogy vi ∈ X ha i páros, és vi ∈ Y , ha i páratlan. Legyen v0 címkéjen, v0 szomszédainak címkéje 1, 2, 3,. . . , ahol a legnagyobb címkével ellátott csúcs
legyen v1 . Rendeljük hozzá az n − 1, n − 2, n − 3 címkéket a v1 szomszédjaihoz,
kivéve v0 -hoz, és a legnagyobb címke legyen v2 . Miután v2i is megkapja a címkéjét,rendeljünk növekv® számokat a szomszédaihoz, kivéve a v2i−1 -hez, úgy hogy alegkisebb nem használt címkével címkézünk. Végül a legnagyobb megmaradt
címkét hozzárendeljük a v2i+1 csúcsokhoz. Ezután a szomszédait címkézzük úgy
a v2i+1 -nek (kivéve a v2i csúcsokat), hogy a legnagyobb számú megmaradó címkét
csökken® sorrendben kiosszuk a csúcsoknak. Végül a legkisebb megmaradt címkét
hozzárendeljük a v2i+2 csúcsokhoz. Ezen az alapon történ® címkézés során, azösszes címkénk elfogyott az X és az Y halmazokból, így az összes csúcsnak van
címkézése, ráadásul a csúcsok címkézése különböz® lesz. Legyen li a vi csúcs
címkéje, és így l1 < l3 < . . . és l0 > l2 > . . . . Legyen i páros, és ha i ∈/ {0, k}akkor a szomszédai a vi csúcsának a címkézése legyen li−1 , li−1 + 1, . . . , li+1 és az
indukált él címkék így li − li+1 , li − li+1 − 1, . . . , li+1 lesznek. Ha i páratlan, akkor
i 6= k , így a vi szomszédainak a címkéi li−1 , li−1 +1, . . . , li+1 lesznek és az indukált
él címkék pedig li−1 − li , li−1 + 1 − li , . . . , li + 1 − li lesznek. v0 szomszédainak acímkézése 1, 2, . . . , l1 lesz, míg vk szomszédainak címkéi lk−1 , lk−1 + 1, . . . , lk − 1lesznek, ha k páros, és lk + 1, lk + 2, . . . , lk+1 , ha k páratlan. Könnyen láthatóebb®l, hogy az n − 1 él címke mind különböz® lesz, és a legnagyobb n − 1, míg alegkisebb 1 lesz. Így ez egy alkalmas graceful címkézés.

3.1.

GRACEFUL CÍMKÉZÉS, ILLETVE CÍMKÉZÉS TELJES GRÁFOK ÉS FÁK

ESETÉN15

3.1.6. Deníció. Legyen adva egy caterpillar gráf. Ha a caterpillar gráf bárme-lyik csúcsához több levél is csatlakozik, akkor a gráfunkat lobster gráfnak nevezzük.
Ezekr®l a gráfokról érdemes tudni, hogy 1979-ben Bermond azt sejtette, hogy
minden lobster gráf graceful. Azonban nem tudta bebizonyítani, és ez csak egy
sejtés maradt. 2008-ban Mishra és Panigrahi be tudták látni, hogy minden olyan
lobster gráf, amelyiknek az átmér®je legalább öt az már graceful [7]. Illetve egy
másik osztályáról is be tudták látni, hogy az is graceful. Tehát a lobster gráfoknak
a graceful címkézése, még mindig nyitott kérdés.

3.1.7. Deníció. Egy fa gráfot, szimmetrikus fának nevezünk, ha a fa minden
szintjén ugyanannyi csúcsot találunk.

3.1.5. Tétel. Minden szimmetrikus fának van graceful címkézése.
3.1.2. Megjegyzés. A tétel bizonyítását a [7] cikkben olvashatjuk, melyet teljes
indukcióval látnak be.

3.1.8. Deníció. Egy fa gráfot, csillag gráfnak nevezünk, ha k + 1 csúcsa van és

a k + 1 csúcsból, pontosan k db levél van.

3.1.3. Megjegyzés. Az utak és a csillagok is egyszer¶ caterpillar gráfok. Az út
esetén a caterpillar gráfnak pontosan két levele van, míg a csillagnál legalább két
levél mindig van, és a központi útvonala hossza 0.

3.1.9. Deníció. Legyen G = (V, E, ϕ) véges gráf. Ekkor a G gráf átmér®jén, aleghosszabb út hosszát érjük, amit diam(G)-vel szokás jelölni.

3.1.6. Tétel. Legyen G = (V, E, ϕ) véges fa gráf, illetve diam(G) = d és 1 ≤ d ≤≤ 3. Ekkor a G fa gráf, caterpillar fa gráf.

Bizonyítás. Tegyük fel, hogy a G gráfnak az átmér®je i, ahol i ∈ {1, 2, 3}. Ha
i = 1, akkor egyértelm¶, hogy a G gráf a két csúcsú teljes gráf.
Ha i = 2, akkor legyen P = v0 v1 v2 a leghosszabb út a G gráfban. Ekkor azonban
v0 és v2 levelek, különben az út hosszabb lenne. Így, ha y egy másik csúcs lenne,
akkor az y és a v1 csúcs között is lenne út, viszont az nem megy át a v0 és
v1 csúcsokon. Viszont v0 hozzáadásával tudjuk növelni az út hosszát. Mivel
két hosszúságú a leghosszabb út, ez viszont azt jelenti, hogy y -t a v1 -hez kellhozzácsatolni. Így G egy csillag lesz, ami caterpillar gráf, tehát készen vagyunk.
Végül, ha i = 3, akkor legyen P = v0 v1 v2 v3 a leghosszabb út G-ben. Az megint
világos, hogy v0 és v3 lesznek a levelek, mert akkor a P utat lehetne növelni.
Ha létezik egy y csúcs G-ben, akkor létezni-e kell egy y -ból induló útnak, ami
nem tartalmaz más csúcsot a P útból. Ez azt jelenti, hogy létezni kell egy olyanútnak ami y -ból indul és v1 vagy v2 -ben ér véget. Tegyük fel, hogy az út v1 -ben

16

FEJEZET 3.

GRACEFUL GRÁFOK ÉS GRACEFUL CÍMKÉZÉSvégz®dik, de v2 -re is ugyanez a bizonyítás. Ha az út y -ból v1 -ben nem csak egyéllel csatlakozik, akkor létezni-e kell egy olyan útnak, amelynek hossza legalább
négy, a v2 és v3 csúcsokkal együtt. Így bármely olyan y csúcs esetén, ami nincs
rajta a P úton, az csak egy éllel csatlakozhat a v1 -hez vagy a v2 -höz. Így a gráfunk
csak caterpillar gráf lehet.

3.1.7. Tétel. Minden G = (V, E, ϕ) véges fa gráf, ahol diam(G) = 4 teljesül, az
graceful gráf.

3.1.8. Tétel. Minden G = (V, E, ϕ) véges fa gráf, ahol diam(G) = 5 teljesül, az
graceful gráf.

3.1.4. Megjegyzés. A két tétel bizonyítását a [7] cikkben olvashatjuk, melyet acikkben található, 20-as lemma segítségével bizonyítottak.

3.1.10. Deníció. Egy G gráfot spider fa gráfnak nevezünk, ha fa gráf és pontosan egy olyan csúcsa van, amelyiknek fokszáma nagyobb, mint 2. Ha létezik,
ilyen csúcs, akkor ezt a csúcsot elágazási pontnak nevezzük, illetve a spider gráfban az elágazási pontból induló különböz® hosszúságú utakat nevezzük a spider
gráf lábainak.

3.1.9. Tétel. Legyen G = (V, E, ϕ) véges spider gráf s darab lábbal, amelyeknek

hossza {n, n + 1}, ahol n > 1. Ekkor a G gráfnak létezik graceful címkézése.

3.1.5. Megjegyzés. A tétel bizonyítása a [7] cikkben olvasható, mely egy konstruktív bizonyítás.

3.1.10. Tétel. Egy spider gráf, ami 3 útból vagy 4 útból áll, az graceful.
3.1.6. Megjegyzés. A tétel bizonyítását a [5] tanulmányában olvashatjuk, mely a
3.16-os lemmát használja fel a bizonyítás során.

3.1.11. Tétel. Legyen G = (V, E, ϕ) véges spider gráf p útból. Ha az utak mindegyike, k hosszúságú, ahol k ∈ N, akkor a spider gráf graceful.

3.1.7. Megjegyzés. A tétel bizonyítását a [5] tanulmányban olvashatjuk.
3.1. ábra. Caterpillar gráf és csillag gráf

3.1.

GRACEFUL CÍMKÉZÉS, ILLETVE CÍMKÉZÉS TELJES GRÁFOK ÉS FÁK

17

ESETÉN3.2. ábra. Spider gráf

3.1.11. Deníció. Legyen G = (V, E, ϕ) véges gráf.

A G gráfot recracker
gráfnak nevezzük, ha egy tetsz®leges n hosszú útból áll és az úton lév® összes
csúcs, egy éllel van összekötve, pontosan egy különböz® csillag gráfhoz.

3.1.12. Tétel. Minden recracker gráfnak van graceful címkézése.
3.1.8. Megjegyzés. A bizonyítást szintén a [7] cikkben olvashatjuk.
Végül a legfontosabb tétel és egyben ennek a résznek a záró tétele megmutatja,
hogy a fa gráfokon belül is, mennyi az a maximális csúcs, amir®l már be tudták
látni, hogy a gráfnak létezik graceful címkézése.

3.1.13. Tétel. Minden fa amelynek legfeljebb 27 csúcsa van, annak létezik graceful
címkézése.

Ezt a tételt Aldred és McKay bizonyította be számítógép használhatával, melynek menetét a [3] és [5] tanulmányokban olvashatjuk.

4. Különleges gráfok,konstrukciók és Sage
implementáció

Ebben a fejezetben szeretnék megmutatni pár eléggé különleges gráfot, amiket anevük alapján is el tudunk már képzelni. Ezek a gráfok mind gracefullak, így egy
program segítségével meg lehet konstruálni ezeket az egyszer¶ gráfokat. Ehhez
segítségül a Sage programcsomagot használom, amelyhez könnyen hozzá lehet
jutni az interneten, és a programozás nem annyira bonyolult, mint más programnyelvek esetén. A Sage a Python nyelvet használja, amely egy magas szint¶
programozási nyelv, de a legnagyobb el®nye mégis az, hogy a nyelv folyamatosan
fejl®dik.

4.1. Graceful double-wheel gráf konstrukciója

4.1.1. Deníció. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = n. Wheel gráfnak
nevezünk egy gráfot, ha a központi csúcsa minden csúccsal össze van kötve, atöbbi csúcs viszont csak a központi csúcshoz vezet® él kivételével, pontosan két
csúccsal van összekötve. Jele: Wn .

4.1.2. Deníció. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = 2 · N + 1, ahol Nazon csúcsok száma, amik egyes körökön helyezkednek el. Double-wheel gráfról
beszélünk, hogyha a körön lév® összes csúcs csatlakozik a központi csúcshoz, ahol
a központi csúcs egyik körön sem helyezkedik el. Jele: DWN .

19

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

20

IMPLEMENTÁCIÓ

4.1. ábra. Wheel gráf (W10 ) és double-wheel gráf(DW10 )Vegyük els®ként a double-wheel gráfokat, amiket az alábbi feltételek szerint
tudunk megkonstruálni.
Legyen N a körökön lév® csúcsok száma és xi az a csúcs, ahol az i-edik csúcs
címkéje ezen a bels® körön van. Továbbá legyen yj az a csúcs, ahol a j -edik csúcs
címkéje a második (küls®) körön van, végül z legyen a központi csúcs egy címkéje.
A javasolt konstrukció során két esetet különböztetünk meg, attól függ®en, hogy
milyen az N paritása. Mindkét esetben legyen a központi csúcs (z ) címkéje 0.
Továbbá a csúcsok címkézései a két körön az alábbiak szerint legyenek deniálva:Ha N páros és N ≥ 4:


i


 4·N −3−i
xi

4·N



4·N −2









4·N −4N +jyj
3·N −1−j
4·N −1
2·N, ha i páratlan és 1 ≤ i ≤ N − 3, ha i páros és 2 ≤ i ≤ N − 2, ha i = N − 1, ha i = N.
, ha j = 1, ha j páratlan és 3 ≤ j ≤ N − 3, ha j páros és 2 ≤ j ≤ N − 2, ha j = N − 1, ha j = N.

4.1.

GRACEFUL DOUBLE-WHEEL GRÁF KONSTRUKCIÓJA

21

Ha N páratlan és N ≥ 5:
i ,ha i páratlan és 1 ≤ i ≤ N − 2 4 · N + 1 − i ,ha i páros és 2 ≤ i ≤ N − 3xi
2 · N ,ha i = N − 1
2 · N + 4 ,ha i = N.

4·N





 2·N +2+jyj
2·N +1−j
3·N +2
2·N +2,ha j = 1
,ha j páratlan és 3 ≤ j ≤ N − 2,ha j páros és 2 ≤ j ≤ N − 3,ha j = N − 1,ha j = N.

Az itt látható programkód, az el®z® feltételeknek az implementálása, ami egyszer¶en pár darab for ciklussal, és pár darab if paranccsal készült. Így kapunk
egy tömböt, melyben szerepelni fognak a graceful címkézés során felhasznált csúcscímkék.

def Labels(n):L=[]if n % 2 == 0 and 4<=n :for i in range(1,n+1):
if i==n:L.insert(len(L),4*n-2)
elif i==n-1:
L.insert(len(L),4*n)elif i % 2 <>0 and 1<=i and i<=n-3:
L.insert(len(L),i)
elif i % 2 ==0 and 2<=i and i<=n-2:
L.insert(len(L),4*n-3-i)
for j in range(1,n+1):
if j==1:
L.insert(len(L),4*n-4)
elif j % 2 <>0 and 3<=j and j<=n-3:
L.insert(len(L),n+j)
elif j % 2 ==0 and 2<=j and j<=n-2:
L.insert(len(L),3*n-1-j)elif j==n-1 :L.insert(len(L),4*n-1)
elif j==n:L.insert(len(L),2*n)elif n % 2 <> 0 and n>=5:

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

22

IMPLEMENTÁCIÓ

for k in range(1,n+1):
if k==n-1:
L.insert(len(L),2*n)elif k==n:L.insert(len(L),2*n+4)
elif k % 2 <>0 and 1<=k and k<=n-2:
L.insert(len(L),k)elif k % 2 == 0 and 2<=k and k<=n-3:
L.insert(len(L),4*n+1-k)
for l in range(1,n+1):
if l==1:
L.insert(len(L),4*n)elif l % 2 <>0 and 3<=l and l<=n-2:
L.insert(len(L),2*n+2+l)
elif l % 2 ==0 and 2<=l and l<=n-3:
L.insert(len(L),2*n+1-l)
elif l==n-1:
L.insert(len(L),3*n+2)
elif l==n:L.insert(len(L),2*n+2)
return L

4.1.

GRACEFUL DOUBLE-WHEEL GRÁF KONSTRUKCIÓJA

23

A double-wheel gráf szomszédsági mátrixát használjuk fel a gráf konstrukciójához, mert a mátrixokat könny¶ kezelni. Ami egy 9 csúcsú gráfnál a következ®képpen néz ki, de a programunkban is egy hasonló mátrix van leprogramozva, csak
a program bármilyen n-re képes ezt megkonstruálni.
A double-wheel gráf szomszédsági mátrixa a következ® képpen nézz ki:



0
 0


 1

 0

 0

 0


 1

 0
1

0
0
0
1
0
0
0
1
1

1
0
0
0
1
0
0
0
1

0
1
0
0
0
1
0
0
1

0
0
1
0
0
0
1
0
1

0
0
0
1
0
0
0
1
1

1
0
0
0
1
0
0
0
1

0
1
0
0
0
1
0
0
1

def adjmatrix_row(n,i):row=[]
I1 = I2 = 0
if i < 2:
I1 = 2 + i
I2 = 2 * n - (2 - i)elif i > (2 * n - 3):
I1 = i - (2 * n - 2)
I2 = 2 * n - 4 + I1
else:
I1 = i - 2
I2 = I1 + 4
for j in range(2*n):
if j == I1 or j == I2:
row.insert(j, 1)
else:
row.insert(j, 0)
row.insert(len(row), 1)
return row
def dwgraf_adjmatrix(a):M=Matrix(2 * a + 1)
if a > 2:
for i in range(2 * a):aktRow=adjmatrix_row(a, i)M.set_row(i, aktRow)
lastRow = []


1
1 


1 

1 

1 

1 


1 

1 
0

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

24

IMPLEMENTÁCIÓ

for i in range(a * 2):
lastRow.insert(len(lastRow), 1)
lastRow.insert(len(lastRow), 0)
M.set_row(M.nrows()-1, lastRow)
return M
Végül már csak a gráf megrajzoltatása és a címkézése maradt hátra. A megrajzoltatása a draw függvénnyel történik. Ebben a függvényben a szomszédsági
mátrix alapján megkonstruáljuk a gráfot, viszont ügyelni kell a csúcsok elhelyezkedésére. Ha nem pozicionáljuk a csúcsokat, akkor igaz, hogy a szomszédsági
mátrix alapján minden csúcs jó csúccsal van összekötve, de nem kör alakú gráfokat
kapunk. A csúcsok pozíciójának a megadása a következ®képpen zajlik. A nulla
csúcscímkével ellátott csúcs, mindig a központi csúcs legyen, aminek a helyét x ésy koordinátákkal adjuk meg. Így a nullás címke a [0, 0] lesz, azaz ® lesz középen.
A további csúcsok x koordinátáját (6 − (−1)i ) · f loat(cos(( 2·π2·n ) · i) képlettel számolhatjuk ki. Az y -t is hasonlóképpen tudjuk számolni, csak abban az esetben akoszinusz függvény helyett a szinusz függvényt használunk.
Már csak a címkézés van hátra, amit a deníció alapján írunk be, majd a feltételeket
hozzárendeljük, és megkapjuk az eljárást a graceful double-wheel gráfok megkonstruálásához.

def DW(n):R=Labels(n)
T1=[]
T2=[]
for k in range(len(R)/2):
T1.insert(len(T1),R[k])T2.insert(len(T2),R[len(R)-1-k])
draw(n, T1, T2)
def draw(n, T1, T2):
F=Graph(dwgraf_adjmatrix(n))
T=[]
for i in range(len(T1)):
T.insert(len(T),T1[i])T.insert(len(T),T2[i])T.insert(len(T),0)
from math import sin, cos, pi
pos_dict = {}for i in range(len(T)-1):
x = (6-(-1)^i)*float(cos(((2*pi)/(2*n))*i))y = (6-(-1)^i)*float(sin(((2*pi)/(2*n))*i))
pos_dict[T[i]] = [x,y]4.1.

GRACEFUL DOUBLE-WHEEL GRÁF KONSTRUKCIÓJA

pos_dict[T[len(T)-1]]=[0,0]F.relabel( [ T[i] for i in range(F.order()) ],inplace=True)for u,v,l in F.edges(): F.set_edge_label(u,v,abs(u-v))
pl = F.graphplot(pos=pos_dict,edge_labels=True,
edge_color='green',vertex_colors='yellow',
vertex_size=300,graph_border=True)pl.show(figsize=8)
html('<h3>Double-Wheel Graceful graph</h3>')@interactdef _(n=slider(4,25,1,1,'Adja meg a gráf köreinek a csúcsszámát!',True)):[DW(n)]

25

FEJEZET 4.

26KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGEIMPLEMENTÁCIÓ

4.2. ábra. Páros double-wheel gráf címkézéssel (DW20 )4.3. ábra. Páratlan double-wheel gráf címkézéssel (DW15 )4.1.

GRACEFUL DOUBLE-WHEEL GRÁF KONSTRUKCIÓJA

27

A double-wheel gráfok esetén az algoritmus még barátságosnak is mondható, defelvet®dhet az a kérdés, hogy mi van, ha nem csak két körünk van, hanem három,azaz triple-wheel gráf esetén. A triple-wheel gráfok esetén szeretnék egy másik
programot is felhasználni, mégpedig a MiniZinc programot. A program egyedi
nyelvvel bír, egyszer¶bb például, mint a Sage programcsomag. A programmal f®leg különböz® optimalizálási feladatokat tudunk elvégezni, de segítségünkre van,ha szeretnénk triple-wheel gráfokat vizsgálni.
Els®ként írni kell egy programot, ami a deníción alapul, tehát a csúcsokat megszámozzuk és ,amelyik csúcsból él vezet ki egy másik csúcsba, azoknak a csúcsok
címkéjének az abszolút különbségét vesszük. A k1, k2, k3 az inputok, ahol meg
kell adni, hogy egy körön hány darab csúcs helyezkedjen el. A mi esetünkben mostlegyen mindegyik körön három-három csúcs. Az m érték jelenti az élek számát,az n pedig jelentse a csúcsok számát. Ami a MiniZinc nyelvén a következ®:

include "globals.mzn";
int: k1 = 3;
int: k2 = 3;
int: k3 = 3;
int: m = 2*k1+2*k2+2*k3;
int: n = k1+k2+k3+1;
array[1..n] of var 0..m: nodes;
array[1..m] of var 1..m: edges;
solve :: int_search(nodes, first_fail, indomain_min, complete) satisfy;
constraint
forall(a in 1..k1+k2+k3)(
abs(nodes[1]-nodes[a+1]) = edges[a])/\abs(nodes[2]-nodes[k1+1]) = edges[k1+k2+k3+1]/\
forall(a in k1+k2+k3+2..2*k1+2*k2+k3)(
abs(nodes[a-k1-k2-k3]-nodes[a-k1-k2-k3+1]) = edges[a])/\abs(nodes[k1+2]-nodes[k1+k2+1]) = edges[2*k1+2*k2+1]/\
abs(nodes[k1+k2+2]-nodes[k1+k2+k3+1]) = edges[2*k1+2*k2+k3+1]/\

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

28

IMPLEMENTÁCIÓ

forall(a in 2*k1+2*k2+k3+2..2*k1+2*k2+2*k3)(
abs(nodes[a-k1-k2-k3]-nodes[a-k1-k2-k3+1]) = edges[a])/\all_different(edges)/\
all_different(nodes);
output["nodes: " ++ show(nodes) ++ "\n"];A válasz pedig a következ®:

Ez az üzenet azt jelenti, hogy az általunk készített program nem talált, olyan
számsorozatot, amelynél minden él különböz® lenne. Mivel a T W3 gráf esetén,nem követeltünk meg semmilyen feltételt sem, csak a deníciót használtuk, kijelenthet®, hogy a T W3 esetén nincs jó graceful címkézés.
Most vizsgáljuk meg, azt az esetet, amikor minden körön négy darab csúcs található. Ebben az esetben viszont létezik megoldás. S®t ha azt is megköveteljük,
hogy a központi csúcs címkéje legyen 0, és a k1 körön legyen az 1-es csúcscímke,akkor is van megoldás.
Körök

1. csúcs

2. csúcs

3. csúcs

4. csúcs

1. kör
2. kör
3. kör

1
15
11

20
5
18

23
17
2

9
21
24

Körök

1. csúcs

2. csúcs

3. csúcs

4. csúcs

1. kör
2. kör
3. kör

1
15
14

18
12
22

13
16
2

24
6
21

Ez a két táblázat azt mutatja meg, hogy a körökön mely csúcscímkék helyezkedik
el. A 0 címke azért nem szerepel a táblázatban, mert az a központi csúcs. Ez
csak két megoldás a T W4 gráfra, de ezeken kívül is számos megoldás létezik.

4.1.

GRACEFUL DOUBLE-WHEEL GRÁF KONSTRUKCIÓJA

29

Hasonló a helyzet, hogyha olyan gráfot nézünk, amelyiknek bár két kereke van,de a kerekeken a csúcsok száma nem egyezik meg. Ebben az esetben csak két
körünk lesz, k1 és k2, az n és az m ugyanúgy az élek, illetve a csúcsok számát
jelöli. Ha megnézzük a 2 − 2, 2 − 3, 3 − 3 eseteket, akkor azt tapasztaljuk, hogy
nincs graceful címkézés, mert a UNSATISFIABLE feliratot kaptuk vissza. Viszont
megvizsgálva a 3 − 4 esetet már kapunk megoldásokat.

A program futtatása el®tt, megköveteljük, hogy a központi csúcs címkéje legyen
0, míg az els® körön az egyes számú címke szerepeljen, a második körön pedig a
legnagyobb címke szerepeljen. Tehát ebben az esetben is létezik graceful címkézés.
Ha a csúcsok számát növeljük, azt tapasztaljuk, hogy kis n-re létezik graceful
címkézés különböz® double-wheel gráfok esetén. Ugyanez mondható ki, triplewheel gráfok esetén is.

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

30

IMPLEMENTÁCIÓ

4.2. Graceful caterpillar gráf konstrukciója

A második gráf osztályunk, azok a caterpillar gráfok lesznek. A program készítése
során els®ként a caterpillar gráfnál használt központi utat konstruáltam meg,
majd a program a felhasználó által beírt számok alapján, hozzákapcsol annyi
levelet a csúcsokhoz, ahová és amennyit a felhasználó szeretne.
4.4. ábra. Caterpillar gráf adott levelekkel

def CaterpillarGraph(T):G = Graph()G.add_path(range(len(T))[0:len(T)])
vc=len(G.get_vertices())
for i in range(len(T)):
for j in range(T[i]):G.add_edge(i,vc)
vc=vc+1
return G
A címkézés, az el®z® fejezetben található (Minden caterpillar gráf graceful)tétel bizonyítása szerint történik, ahol konstrukció alapján bizonyítottuk be állításunkat.

def CaterpillarLabels(T):under=-1
over=-1
leaves=[]4.2.

GRACEFUL CATERPILLAR GRÁF KONSTRUKCIÓJA

31

mainpath=[]for i in range(len(T)):
over=over+1+T[i]join=overfor i in range(len(T)):
mainpath.insert(len(mainpath),join)
if i % 2 != 0:
for j in range(T[i]):over=over-1
leaves.insert(len(leaves),over)
over=over-1
join=overelse:
for j in range(T[i]):under=under+1
leaves.insert(len(leaves),under)
under=under+1
join=under
return mainpath+leaves
Szintén, mint a double-wheel gráfok során láthattuk, az alábbi programkód annyit
csinál, hogy kirajzoltatja a gráfot, a tömbben szerepl® címkékkel felcímkézi, ésláthatóvá teszi nekünk a gráfot. A D.show() résznél rengeteg lehet®ségünk van agráfokat szerkeszteni, meg lehet adni a csúcsok és élek színét, vagy hogy hogyan
helyezkedjen el a gráf.

def Caterpillar(N):
D=CaterpillarGraph(N)
T=CaterpillarLabels(N)D.relabel( [ T[i] for i in range(D.order()) ], inplace=True)for u,v,l in D.edges(): D.set_edge_label(u,v,abs(u-v))
D.show(edge_labels=True,layout='tree',tree_orientation='down',
tree_root=0,
vertex_colors='yellow',figsize=7)Caterpillar([2,7,2,2,2,3])

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

32

IMPLEMENTÁCIÓ

4.5. ábra. Caterpillar gráf címkézéssel

4.3. Graceful n-szeresen összetett teljes páros gráf konstrukciója

Most vizsgáljuk meg, hogy páros gráfok esetén, hogy alakul a címkézés. A konstrukció során, nem csak a páros gráfokat tudjuk leprogramozni, úgy hogy gracefulak legyenek, hanem egy olyan gráfot is tudunk készíteni vele, aminek van egy
központi csúcsa, és ez a csúcs az összes adott teljes páros gráfnak az egyik csúcsa.
Ezt a gráf típust nevezzük n-szeren összetett teljes páros gráfnak.

def BigArrayOk(T):if len(T) == 0:
return true
if len(T) > 1:
return false
if T[0][1] > 2:
return false
return true
def ArraySort(T):for i in range(1, len(T)):
val = T[i]

4.3.

GRACEFUL N-SZERESEN ÖSSZETETT TELJES PÁROS GRÁFKONSTRUKCIÓJA

j = i - 1
while (j >= 0) and (T[j] < val):
T[j+1] = T[j]j = j - 1
T[j+1] = val
return T
def ArrayDupes(T):count_dict = {}dupes=[]
for i in range(len(T)):
count_dict[T[i]] = 0
for i in range(len(T)):
count_dict[T[i]] = count_dict[T[i]] + 1
for i in count_dict:if count_dict[i] > 1:
dupes.insert(len(dupes),[i,count_dict[i]])return dupes
def ArraySum(T):a=0
for i in range(len(T)):
a=a+T[i]return a

33

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

34

IMPLEMENTÁCIÓ

4.6. ábra. 2-szeresen összetett teljes páros gráf

4.7. ábra. 3-szorosan összetett teljes páros gráf

A konstrukció során, minden ilyen jelleg¶ gráfot meg lehet alkotni, viszont
lesznek olyan gráfok, amik nem lesznek graceful tulajdonságúak. Ahhoz, hogy
legyen graceful címkézése a gráfnak, ahhoz az kell, hogy a teljes páros gráfok
közül maximum kett® legyen izomorf egymással. Ha több ilyen izomorf gráfot isösszekapcsolunk, vagy 3-at, vagy 2-2-t, akkor a gráfot nem lehet graceful címkékkel
ellátni.

def BigGraphLabels(T):L=[]dupes=ArrayDupes(T)if BigArrayOk(dupes):
print("Van lehet®ség a címkézésre!")if len(dupes) < 1:
dupes.insert(len(dupes),[-1,-1])lastedge=0

4.3.

GRACEFUL N-SZERESEN ÖSSZETETT TELJES PÁROS GRÁFKONSTRUKCIÓJA

L.insert(len(L),0)i=0
while i < len(T):L.insert(len(L),T[i])if T[i] == dupes[0][0]:L.insert(len(L),1)i = i + 1
i = i + 1
i=0while i < len(T):lastedge = lastedge+T[i]+1
for j in range(T[i]):L.insert(len(L),lastedge+j)
if T[i] == dupes[0][0]:lastedge = lastedge+T[i]+1
for j in range(T[i]):L.insert(len(L),lastedge+(2*j))i = i + 1
i = i + 1
lastedge=L[len(L)-1]
else:
print("Nincs lehet®ség a címkézésre!")for i in range(ArraySum(T)+PartSum(T,0)):L.insert(len(L),i)
return L
def PosDictCalc(T,L):
R=20
r=10
n=ArraySum(T)pos_dict = {}pos_dict[L[0]]=[0,0]m=0.0
for i in range(len(T)):
m=m+T[i]/2
x = R*float(cos(((2*pi)/n)*m))y = R*float(sin(((2*pi)/n)*m))
pos_dict[L[i+1]] = [x,y]m=m+T[i]/2
for i in range(n):x = r*float(cos(((2*pi)/n)*i))y = r*float(sin(((2*pi)/n)*i))

35

FEJEZET 4.

36KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGEIMPLEMENTÁCIÓ

pos_dict[L[i+PartSum(T,0)]] = [x,y]return pos_dict
def PartSum(T,a):n=len(T)+1
for i in range(a):n=n+T[i]return n
def BipartGraf(L):G = Graph(len(L)+1)
for i in range(len(L)):
k=PartSum(L,i)
for j in range(L[i]):G.add_edge(0,k+j)
G.add_edge(i+1,k+j)
return G
def Bipart(L):
L=ArraySort(L)D = BipartGraf(L)Labels=BigGraphLabels(L)D.relabel( [ Labels[i] for i in range(D.order()) ], inplace=True)for u,v,l in D.edges(): D.set_edge_label(u,v,abs(u-v))
pos_dict=PosDictCalc(L,Labels)
pl = D.graphplot(pos=pos_dict,edge_labels=True,
edge_color='black',vertex_colors='yellow',vertex_size=300,graph_border=True)pl.show(figsize=8)
Bipart([4,3,3,3])
Ebben a programrészben, a címkézési eljárás látható, illetve az átláthatóság
miatt a pozíció is meg lett adva. Ha olyan gráfot adunk meg, amiben több izomorf
gráf is összekapcsolódik, azoknál az eseteknél is kirajzolja a gráfot, de kapunk együzenetet, hogy a gráfhoz nincs lehet®ség graceful címkézésre.

4.4.

GRACEFUL PENDANT GRÁF KONSTRUKCIÓJA

37

4.8. ábra. Címkézés sikeres, illetve sikertelen esetben

4.4. Graceful pendant gráf konstrukciója

Az utolsó gráf, amit szemléltetni fogok, az a pendant gráf, ahol a pendant magyarul medált jelent. Nevét a gráf kinézetér®l kapta, ami egy medálhoz hasonlít, de
itt is, mint a többi esetben, nem medál gráfként fogom nevezni, hanem maradoka pendant gráfnál.

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

38

IMPLEMENTÁCIÓ

4.4.1. Deníció. Legyen G = (V, E, ϕ) véges gráf,|V (G)| = 2 · n. A G gráfot

pendant gráfnak nevezzük, ha egy zárt út minden csúcsához, pontosan egy csúcs
csatlakozik, amikb®l más él nem húzható.

4.4.2. Deníció. Legyen G = (V, E, ϕ) véges gráf, |V (G)| = 2 · n. A G pendantgráf graceful címkézése:

1. els®fajú, ha a 0. és a 2 · n. címkék a zárt úton helyezkednek el
2. másodfajú, ha a 2 · n. címke szomszédos a 0. címkével és a 0. címke a zártúton van, a 2 · n. címke pedig nincs az úton3. harmadfajú, ha a 2 · n címke a zárt úton van és szomszédja a 0 csúcs nincsa zárt úton.
4.9. ábra. 20 és 12 csúcsú pendant gráf

4.4.

GRACEFUL PENDANT GRÁF KONSTRUKCIÓJA

39

4.4.1. Tétel. Legyen f : N → N ∪ 0, és legyen G = (V, E, ϕ) véges pendantgráf, ahol a zárt út csúcsai a {v1 , . . . , vn } halmazból kerülnek ki, míg a maradék
csúcsok a {ui , . . . , un } halmazból kerülnek ki. Ha az ui és vj szomszédosak, akkor
i = j -vel.
Ha n ≡ 4 (mod 8) és n > 12, akkor a G gráfnak van graceful címkézése, ami
els®fajú és a következ®képpen adható meg:







0
2·n−i+1
f (vi ) =

i+2



i

, ha i = n, ha i páratlan és 1 ≤ i ≤ n − 1, ha i = n2 , n2 + 2, . . . , n − 2, ha i páros és 2 ≤ i ≤ n2 − 2.


2·n−1





1



n

+
1

2




2
·
n
−
i+1

f (uj ) =
i+6



i+5





i
+4




2·n−i−1
i+2, ha j = n, ha j = n − 1, ha j = n − 23·n, ha j = 3·n
4 + 1, 4 + 3 . . . , n − 43·n, ha j = 3·n
4 , 4 + 2, . . . , n − 33·n, ha j = 4 − 1, ha j = n2 − 1, n2 + 1, . . . , 3·n
4 −2
3·n, ha j páros és 2 ≤ j ≤ 4 − 3, ha j páratlan és 1 ≤ j ≤ n2 − 3

4.4.2. Tétel. Legyen f : N → N ∪ 0, és legyen G = (V, E, ϕ) véges pendantgráf, ahol a zárt út csúcsai a {v1 , . . . , vn } halmazból kerülnek ki, míg a maradék
csúcsok a {ui , . . . , un } halmazból kerülnek ki. Ha az ui és vj szomszédosak, akkor
i = j -vel.
Ha n ≡ 3 (mod 16) és n > 19, akkor a G gráfnak van graceful címkézése, ami
els®fajú és a következ®képpen adható meg:







0
2·n−i+1
f (vi ) =

i+2



i

, ha i = n, ha i páratlan és 1 ≤ i ≤ n − 2
n+1, ha i = n+1
2 , 2 + 2, . . . , n − 1, ha i páros és 2 ≤ i ≤ n+1
2 − 2.

FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

40

IMPLEMENTÁCIÓf (uj ) =


2·n−1





1



n+1



2 +1



n+2





2
·
n
−
i−1


 2·n−i+2

2·n−i−72·n−i+1





i+2




2·n−i−1





i+4



i+2

, ha j = n, ha j = n − 1, ha j = n − 2, ha j = n − 3, ha j = 3·n−1
4+1, ha j = 3·n−1
4
3·n−1, ha j = 4 − 2, 3·n−1+ 2...,n − 7
4
3·n−1, ha j = 3·n−1+
4,+ 8, . . . , n − 5
4
4
3·n−1
3·n−1
, ha j = 4 + 3, 4 + 5, . . . , n − 4, ha j páros és 2 ≤ j ≤ 3·n−1
−4
4
n+1
n+1
, ha j = 2 − 1, 2 + 1, . . . , 3·n−1−1
4, ha j páratlan és 1 ≤ j ≤ n+1−
3
2

4.4.3. Tétel. Legyen f : N → N ∪ 0, és legyen G = (V, E, ϕ) véges pendant gráf,ahol a zárt út csúcsai a {v1 , . . . , vn } halmazból kerülnek ki, míg a maradék csúcsok a {ui , . . . , un } halmazból kerülnek ki. Ha az ui és vj szomszédosak, akkor
i = j -vel.
Ha n ≡ 11 (mod 16) és n > 27, akkor a G gráfnak van graceful címkézése, ami
els®fajú és a következ®képpen adható meg:
0 , ha i = n 2 · n − i + 1 , ha i páratlan és 1 ≤ i ≤ n − 2
f (vi ) =n+1
i + 2 , ha i = n+1

2 , 2 + 2, . . . , n − 1
i , ha i páros és 2 ≤ i ≤ n+1
2 − 2.

2·n−1





1



n+1


2 +1




n+4




n





 2·n−i−1
f (uj ) =2·n−i+2
2·n−i−7
2·n−i+1




i+2





2
·
n
−
i−1




i+4



i+2

, ha j = n, ha j = n − 1, ha j = n − 2, ha j = n − 3, ha j = n − 5, ha j = 3·n−1
4, ha j = 3·n−1
+1
4
3·n−1
+ 2...,n − 9, ha j = 4 − 2, 3·n−1
4
3·n−1
3·n−1
, ha j = 4 + 4, 4 + 8, . . . , n − 7, ha j = 3·n−1+ 3, 3·n−1+ 5, . . . , n − 444, ha j páros és 2 ≤ j ≤ 3·n−1
−4
4
n+1
n+1
, ha j = 2 − 1, 2 + 1, . . . , 3·n−1−1
4n+1, ha j páratlan és 1 ≤ j ≤ 2 − 3Ezen tételek bizonyítását a [2] folyóiratban olvashatjuk, de a tételeket felhasználva a Sage programcsomag segítségével el lehet készíteni egy olyan programot, mely mind a három tétel feltételeit tartalmazza és elkészíti a címkéket,4.4.

GRACEFUL PENDANT GRÁF KONSTRUKCIÓJA

41

majd kirajzoltatja a pendant gráfot. Ha olyan esetet adunk meg, mely egyik
tételt se tudja alkalmazni, úgy egy hibaüzenetet kapunk.

def Labels(n):L=[]if n % 8 == 4 and n>=12:
for i in range(1,n+1):
if i == n:L.insert(len(L),0)
elif i % 2 == 0 and i<(n+1)/2-2:
L.insert(len(L),i)
elif i % 2 <> 0 and i<n:L.insert(len(L),2*n-i+1)
elif n/2<=i<=n-2 and i % 2 == 0:
L.insert(len(L),i+2)
for i in range(1,n+1):
if i == n:L.insert(len(L),2*n-1)
elif i == n-1:
L.insert(len(L),1)
elif i == n-2:
L.insert(len(L),n/2+1)
elif i == 3*n/4-1:
L.insert(len(L),i+5)
elif 3*n/4+1<=i<=n-3 and i % 2 == 0:
L.insert(len(L),2*n-i+1)
elif 3*n/4<=i<=n-2 and i % 2 <> 0:
L.insert(len(L),i+6)
elif n/2-1<=i<=3*n/4-1 and i % 2 <> 0:
L.insert(len(L),i+4)
elif 2<=i<=3*n/4-2 and i % 2 == 0:
L.insert(len(L),2*n-i-1)
elif 1<=i<=n/2-2 and i % 2 <> 0:
L.insert(len(L),i+2)
elif n % 16 == 3 and n>=19:
for i in range(1,n+1):
if i == n:L.insert(len(L),0)
elif i % 2 == 0 and i<=(n+1)/2-2:
L.insert(len(L),i)
elif i % 2 <> 0 and i<=n-2:
L.insert(len(L),2*n-i+1)

FEJEZET 4.

42KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGEIMPLEMENTÁCIÓ

elif (n+1)/2<=i<=n-1 and i % 2 == 0:
L.insert(len(L),i+2)
for i in range(1,n+1):
if i == n:L.insert(len(L),2*n-1)
elif i == n-1:
L.insert(len(L),1)
elif i == n-2:
L.insert(len(L),(n+1)/2+1)
elif i == n-3:
L.insert(len(L),n+2)
elif i == (3*n-1)/4:
L.insert(len(L),2*n-i-1)
elif i == (3*n-1)/4+1:
L.insert(len(L),2*n-i+2)
elif (3*n-1)/4-2<=i<=n-7 and i % 2 == 0:
L.insert(len(L),2*n-i-7)
elif (3*n-1)/4+4<=i<=n-5 and i % 2 == 0:
L.insert(len(L),2*n-i+1)
elif (3*n-1)/4+3<=i<=n-4 and i % 2 <> 0:
L.insert(len(L),i+2)
elif 2<=i<=(3*n-1)/4-4 and i % 2 == 0:
L.insert(len(L),2*n-i-1)
elif (n+1)/2-1<=i<=(3*n-1)/4-1 and i % 2 <>0:
L.insert(len(L),i+4)
elif 1<=i<=(n+1)/2-3 and i % 2 <> 0:
L.insert(len(L),i+2)
elif n % 16 == 11 and n>=27:
for i in range(1,n+1):
if i == n:L.insert(len(L),0)
elif i % 2 == 0 and i<=(n+1)/2-2:
L.insert(len(L),i)
elif i % 2 <> 0 and i<=n-2:
L.insert(len(L),2*n-i+1)
elif (n+1)/2<=i<=n-1 and i % 2 == 0:
L.insert(len(L),i+2)
for i in range(1,n+1):
if i == n:L.insert(len(L),2*n-1)
elif i == n-1:

4.4.

GRACEFUL PENDANT GRÁF KONSTRUKCIÓJA

43

L.insert(len(L),1)
elif i == n-2:
L.insert(len(L),(n+1)/2+1)
elif i == n-3:
L.insert(len(L),n+4)
elif i == n-5:
L.insert(len(L),n)elif i == (3*n-1)/4:
L.insert(len(L),2*n-i-1)
elif i == (3*n-1)/4+1:
L.insert(len(L),2*n-i+2)
elif (3*n-1)/4-2<=i<=n-9 and i % 2 == 0:
L.insert(len(L),2*n-i-7)
elif (3*n-1)/4+4<=i<=n-7 and i % 2 == 0:
L.insert(len(L),2*n-i+1)
elif (3*n-1)/4+3<=i<=n-4 and i % 4 <> 0 and i % 2 <> 0:
L.insert(len(L),i+2)
elif 2<=i<=(3*n-1)/4-4 and i % 2 == 0:
L.insert(len(L),2*n-i-1)
elif (n+1)/2-1<=i<=(3*n-1)/4-1 and i % 2 <>0:
L.insert(len(L),i+4)
elif 1<=i<=(n+1)/2-3 and i % 2 <> 0:
L.insert(len(L),i+2)
return L
def PendantGraph(n):G=Graph()G.add_vertices(range(2*n))for i in range(n):G.add_edge(i,n+i)
if i != 0:
G.add_edge(i-1,i)else:
G.add_edge(n-1,i)return G
A címkézés után, a következ® programkód a pendant gráfot alkotja meg. Lényege,
hogy tetsz®legesen vesz fel 2 · n darab csúcsot, majd élekkel köti össze ®ket, hogy
egy zárt utat kapjunk, és a maradék csúcsokat pedig különböz® úton található
csúcsokhoz köti éllel.

def PendantGraph(n):G=Graph()FEJEZET 4.

KÜLÖNLEGES GRÁFOK, KONSTRUKCIÓK ÉS SAGE

44

IMPLEMENTÁCIÓ

G.add_vertices(range(2*n))for i in range(n):G.add_edge(i,n+i)
if i != 0:
G.add_edge(i-1,i)else:
G.add_edge(n-1,i)return G
def Pendant(n):F=PendantGraph(n)L=Labels(n)draw(F, L)
Végül R1 és R2 segítségével, megadjuk az elhelyezkedését a csúcsoknak, úgyhogy R1 és R2 jelenti a kör sugarát.

def draw(G, L):
R1=20
R2=25
pos_dict = {}for i in range(len(L)/2):
x=R1*float(cos(((2*pi)/(len(L)/2))*i))y=R1*float(sin(((2*pi)/(len(L)/2))*i))
pos_dict[L[i]] = [x,y]for i in range(len(L)/2,len(L)):
x=R2*float(cos(((2*pi)/(len(L)/2))*i))y=R2*float(sin(((2*pi)/(len(L)/2))*i))
pos_dict[L[i]] = [x,y]G.relabel( [ L[i] for i in range(G.order()) ], inplace=True)for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
pl = G.graphplot(pos=pos_dict,edge_labels=True,
edge_color='green',vertex_colors='yellow',
vertex_size=300,graph_border=True)pl.show(figsize=7)
Pendant(20)4.4.

GRACEFUL PENDANT GRÁF KONSTRUKCIÓJA

45

4.10. ábra. 20 csúcsú pendant gráf graceful címkézése

A tételek érdekességei az, ha az ember meggyeli, hogy mi történik az
n = 12, n = 19 és n = 27 esetekben, akkor ha leprogramozza szépen a feltételeket,
akkor észreveheti, hogy a tétel azokban az esetben is helytálló. Azonban, ez nem
lehetséges, mert a számítógép nem veszi észre, hogy a feltételek ütköznek, ígylesz olyan i érték, amire két érték is helyes. Ezt azonban a számítógép nem írjafelül, és csak az els® értéket adja vissza. Például az els® tétel esetében, az n = 12
esetén, i = n − 2 és i = 3·n
4 + 1 is lehetséges. Mivel a számítógép ugye az els®
feltételt nézi meg, az n = 12 esetén 12
2 + 1 = 7 címkét kapjuk meg.

Irodalomjegyzék[1]

Ronan Le Bras, Carla P. Gomes, and Bart Selman: Double-Wheel Graphs
Are Graceful, Computer Science Department, Cornell University, UnitedStates of America 2013.
http://www.cs.cornell.edu/~lebras/publications/
LeBras2013Double.pdf.

[2]

Alessandra Graf: A new graceful labeling for pendant graphs, Aequat.math,vol. 87, pp. 135-145, 2014.
http://link.springer.com/article/10.1007$\%$2Fs00010-012-0184-4.

[3]

Aldred, R.E.L.; McKay, Brendan D. : Graceful and harmonious labellingsof trees., Bulletin of the Institute of Combinatorics and its Applications 23:
69-72, 1998.
http://users.cecs.anu.edu.au/~bdm/papers/graceful.pdf[4]Gallian, Joseph A.: A dynamic survey of graph labeling, Electronic Journalof Combinatorics 5: Dynamic Survey 6, 43 pp. , 1998.
http://www.combinatorics.org/ojs/index.php/eljc/article/
viewFile/DS6/pdf[5]Charles Michael Cavalier: Graceful labelings, Louisiana State University,
United States of America, 2006.
http://people.math.sc.edu/czabarka/Theses/Graceful.pdf[6]

G. Sethuraman: On graceful graphs: One vertex unions of non-isomorphic
complete bipartite graphs, Indian J. Pure Appl. Math. 32, No.7, 975-980 ,2001.
http://www.dli.gov.in/data$\_$copy/upload/INSA/INSA$\_$1/
20005b06$\_$975.pdf[7]

Elina Robeva: An extensive survey of graceful trees, [Undergraduate Honours
thesis], Stanford University, United States of America 2011.
http://mathematics.stanford.edu/wp-content/uploads/2013/08/
Robeva-Honors-Thesis-2011.pdf[8]

W. A. Stein et al.: Sage Mathematics Software (Version 7.1), The Sage Development Team, 2016, http://www.sagemath.org.
47

48

[9]

IRODALOMJEGYZÉKTurjányi Sándor: Bevezetés a kombinatórikába és a gráfelméletbe, mobiDIÁK
könyvtár, Debreceni Egyetem, Informatikai Kar, 2005.
http://www.inf.unideb.hu/oktatas/mobidiak/Turjanyi_Sandor/Bev.
_a_komb._es_a_grafelmeletbe/1.pdf[10] Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997.
[11] Rosa, A.: On certain valuations of the vertices of a graph. Theory of Graphs(Internat. Symposium, Rome, July 1966), pp. 349-355. Gordan and Breach,
New York; Dunod, Paris, 1967.
https://www.researchgate.net/publication/244474213_On_certain_
valuations_of_the_vertices_of_a_graph_Theory_of_Graphs[12] N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, G. Tack.:
Towards a Standard CP Modelling Language. In Bessi£re (ed.), ThirteenthInternational Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science 4741, pp. 529543. Springer-Verlag,
Providence, RI, USA, Sept. 2007.
http://www.gecode.org/paper.html?id=NethercoteStuckeyEa:CP:2007