Debreceni Egyetem
Természettudományi és Technológiai Kar
Matematikai Intézet

Diplomamunka

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

Juhász Gyula
témavezet®: Dr. Tengely Szabolcs

Debrecen, 2020

Tartalomjegyzék

Tartalomjegyzéki

1 Bevezet®

3

2 Graceful címkézés keresése5

3 Hadamard-mátrixok és graceful címkézés

11

4 Speciális graceful körgráfok implementálása

17

5 Speciális graceful fagráfok, és álrács gráfok implementálása

63

Irodalomjegyzék

83

2.1. Deníciók és fontosabb állítások . . . . . . . . . . . . . . . . . . . .
2.2. Backtrack-algoritmus és a graceful címkézés . . . . . . . . . . . . .

5
6

3.1. Hadamard-mátrixok . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2. Egyszer¶sített Hadamard-mátrixok . . . . . . . . . . . . . . . . . . 13
4.1. Cn gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Bn,n gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Gn gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Medál gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Álkerék gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Sín gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7. Ct (Cn ) gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8. Sárkány gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.9. Körgráfok párhuzamos húrokkal . . . . . . . . . . . . . . . . . . . .
4.10. Körgráfok cikk-cakk húrokkal . . . . . . . . . . . . . . . . . . . . .
5.1. Csillag gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Pók gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Petárda gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. Álrács gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

17
19
22
28
32
35
40
45
50
56
63
64
72
76

KöszönetnyilvánításEl®ször szeretnék köszönetet mondani a családomnak, akik az egyetemi éveim
alatt mindig mellettem voltak, és támogattak a legnehezebb napokon is.
Továbbá, szeretnék köszönetet mondani Dr. Tengely Szabolcs témavezet®mnek,
akinek segítsége nélkül nem jöhetett volna létre ezen dolgozat.
Végül, szeretnék köszönetet mondani a Debreceni Egyetem Matematikai Intézetében
dolgozó valamennyi oktatónak lelkiismeretes munkájukért.

11. Bevezet®

1967-ben Alexander Rosa cikkében [1] találkozhattunk el®ször a graceful címkézés
fogalmával, amelyet még β -címkézésként találhatunk meg ebben a cikkben. Egy
gráfnak egy címkézése β -címkézés, hogyha létezik olyan injektív f csúcscímkézés,és bijektív g élcímkézés, hogy minden e = uv ∈ E esetén |f (u) − f (v)| = g(e) .

Vagyis, egy élnek a címkéje, a rá illeszked® csúcsok címkéinek abszolút értékben
vett különbsége, ahol az élek címkéi mind különböz®ek. Solomon W. Golomb
már ezt a címkézést, graceful címkézésként említi az 1972-ben megjelent "How tonumber a graph" cikkében [2].
Azonban az évek során a kutatók számos új deníciót, és tételt alkottak meg,amelyek közül talán E.K.Gnang tétele volt a legjelent®sebb. Gnang 2019-ben
kiadott publikációjában [3], a fagráfok esetén adott egy általános bizonyítást agraceful címkézés létezésére. Ezen eredmény ellen®rzése, jelen pillanatban is folyamatban van.
Ahogy múltak az évek, újabb gráfcsaládokról látták be, hogy létezik graceful
címkézésük, viszont a gráfok sokasága miatt, még mindig vannak olyan gráfcsaládok, amelyekr®l nem tudni, hogy létezik-e graceful címkézésük. Ilyenkor viszont
felmerül a kérdés, hogy egy adott gráfcsalád esetén, létezik-e olyan csúcscímkézés,amelyet ki lehet terjeszteni az egész gráfcsaládra.
Az el®z® dolgozatomhoz hasonlóan, a diplomamunkám során is speciális gráfoknak
az implementálását t¶ztem ki célul, illetve olyan gráfoknak a címkézését vizsgáltam, amelyekr®l eddig csak sejteni lehetett, hogy létezik graceful címkézése. Az
implementálás részét minden esetben a SageMath programcsomagban [4] végeztem
el, viszont néhány algoritmust az alap Java programozási nyelv segítségével próbáltam megalkotni. A vizsgált gráfcsaládok között szerepelnek továbbra is a fagráfok, illetve speciális körgráfok, de szeretnék egy olyan gráfcsaládot is bemutatni,
amelynél nem feltétlen követelmény például, hogy összefügg® legyen a gráf. Viszont az implementálások során fontos, hogy a formulák precízen legyenek leírva acikkekben. Így a cikkek feldolgozása során nem csak az implementálásra kellett gyelnem, hanem a formulák helyességére is. Sok esetben a helyes programeszközök
használata után derült ki, hogy néhány cikk esetében elírások, hiányosságok vannak. Így ezen esetekben a formulákat javítani kellett. Például javításra szorultaka Gn gráfok, a medál gráfok, a Ct Cn gráfok, a sárkány gráfok, a párhuzamos
húrokkal rendelkez® körgráfok, illetve a pók gráfok formulái is.
3

4

FEJEZET 1.

BEVEZETA dolgozatom írása során viszont egy érdekes gondolatom támadt a gráfok konstrukciója során. Amikor régebben egy mátrixot implementálni szerettem volna,el®ször is megnéztem annak a gráfnak a szomszédsági mátrixát, hogy milyen tulajdonságokkal rendelkezik. A szomszédsági mátrix egy bináris mátrix, amelyr®la graceful címkézés miatt feltesszük, hogy a f®átlójában csak nullák szerepelnek,
hiszen graceful címkézés során csak azoknak a gráfoknak van graceful címkézése,
amelyek egyszer¶ gráfok. Ekkor támadt az az ötletem, hogy mi történne akkor,
hogyha én egy gráf szomszédsági mátrixaként a Hadamard-mátrixot venném némi
módosítással. Ennek eredményeit is szeretném bemutatni ebben a dolgozatban,
amelyet megel®z egy kisebb kódelméleti ismertet®.

2. Graceful címkézés kereséseEl®ször is ebben a fejezetben néhány alapvet® deníciót, illetve tételt szeretnék
ismertetni, amelyek nélkül nehezen értelmezhet® maga a graceful címkézés. A
tételek és deníciók után, egy rövid eljárást szeretnék bemutatni, amely soránbármilyen gráf esetén megállapítható, hogy az adott gráfnak létezik-e graceful
címkézése, vagy sem. Viszont ez az eljárás csak kis csúcsszámú gráfok esetén
használható, hiszen az eljárást nagyban meghatározza az éleknek, és a csúcsoknak
a száma.

2.1. Deníciók és fontosabb állítások
2.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 az összes v ∈ |V (G)|
csúcshoz hozzárendelünk különböz® nemnegatív egész számokat.
Egy gráf éleinek címkézésén egy olyan ∆ bijektív leképezést értünk, ahol az összes
e ∈ |E(G)| élhez hozzárendelünk különböz® nemnegatív egész számokat.

2.1.2. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf, ahol |V (G)| = n,|E(G)| = m. Ha van olyan f : V (G) → {0, . . . , m} injektív függvény, hogybármely e ∈ E(G) esetén az|f (v) − f (w)| (v, w ∈ V (G))értékek különböz®ek, akkor ezt az f függvényt a G gráf graceful címkézésének
nevezzük. Ekkor az élek címkéinek a halmaza: {1, . . . , m}.

2.1.1. Lemma. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf, |V (G)| = m és|E(G)| = n. Ha a G gráf gracful, akkor m ≤ n + 1.

2.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.
Megjegyzés. Továbbá, érdemes megjegyezni, hogy az évek során egyre több ember
vizsgálta a fagráfok graceful címkézéseit. Alexander Rosa "On certain valuationsof the vertices of a graph" cikkében [1] már bebizonyította néhány fagráfcsaládról, hogy graceful gráfok, viszont nem tudott olyan tételt megfogalmazni, ami

56

FEJEZET 2.

GRACEFUL CÍMKÉZÉS KERESÉSE

azt állítja, hogy minden fa graceful. Pár évtizeddel kés®bb, viszont a további fagráfcsaládok sikeres vizsgálata során, Ringel és Kotzig sejtésként fogalmazta meg,hogy minden fának van graceful címkézése. Ezt Ringel-Kotzig-Rosa sejtésnek,
vagy más néven "A graceful fák sejtésének" nevezték.
Azonban 2019-ben E.K.Gnang, a Purdue Egyetem professzora, "On graceful andharmonious labelings of trees" munkájában [3] adott egy bizonyítást a fagráfok
graceful tulajdonságaival kapcsolatosan, véges testek segítségével.

2.1.2. Tétel. Legyen G véges, egyszer¶ gráf, |V (G)| ≤ 4. Ekkor a G gráfnak van
graceful címkézése.
Megjegyzés. Ha a gráfnak pontosan 5 csúcsa van, akkor csak a C5 -nek és a K5 -nek

nincs graceful címkézése.

2.1.3. Deníció. Legyen adott egy G egyszer¶ gráf, ahol |V (G)| = {v1 , . . . , vm }.

A G gráfból képzett M (G) egyszer¶ gráfot, a G gráf Mycielski-gráfjának nevezzük, ha csúcsai V (G) ∪ {u1 , . . . , um } ∪ {w}, és egy vi ∈ V (G) csúcs pontosan
azokkal a csúcsokkal szomszédos, amivel G-ben is szomszédos volt. Továbbá, havi szomszédos volt vj -vel, akkor az Mycielski-gráfban vi legyen szomszédos uj -vel,és ui legyen szomszédos vj -vel. Végül, w legyen szomszédos az összes ui csúccsal,
ahol i = 1, . . . , m.
Megjegyzés. Belátható, hogy egy nemüres, egyszer¶ gráfnak és a Mycielski-gráfjának

a maximális klikkmérete megegyezik, illetve a gráfnak egy k darab színnel történ®
csúcsszínezése esetén a Mycielski-gráfjának k + 1 darab színnel már van jó csúcsszínezése. Továbbá, ha 2 ≤ a ≤ b, akkor létezik olyan egyszer¶ gráf, amelynek amaximális klikkmérete éppen a, míg a színezéseinek a száma b.

2.2. Backtrack-algoritmus és a graceful címkézés
A backtrack-algoritmus, vagy más néven visszalépéses-megoldáskeres® algoritmus
az egyik legegyszer¶bb algoritmus abból a szempontból, hogyha az adatbázisunkegyszer¶. Azaz, ha az adatbázisunk fastruktúrájú, akkor belátható id®n belül
az algoritmus eredményt adhat. Azonban, ha van az adatszerkezetünkben kör,
akkor el®fordulhat, hogy az algoritmus soha nem áll le. Így feltehetjük, hogy abacktrack-algoritmus gyel a körökre is. Általában a programozó ilyenkor visszaléptetést használ, azaz feljegyzi a már használt csomópontokat, és ha minden
lehet®séget megvizsgált már ebb®l kiindulva, és nem talált megoldást, akkor azt
többet már nem fogja bejárni.
Mivel ez fa-adatstruktúrákra van értelmezve, így nem nehéz olyan algoritmust
készíteni, ami bizonyos problémákra keres megoldást gráfokban. Graceful címkézés
esetén, az algoritmus nézzen ki a következ®képpen:

2.2.

BACKTRACK-ALGORITMUS ÉS A GRACEFUL CÍMKÉZÉS7(i.) Bemenetként megadjuk az algoritmusnak magát a gráfot, az éleknek a listáját,egy kezdeti címkézést, a kezd® csúcsnak a lehet® legkisebb értékét, és végül amár kiosztott élcímkéknek egy listáját. A kezdeti élcímkézés pontosan annyi
darab (−1)-est tartalmaz, amennyi csúcsa van a gráfunknak. Továbbá, alehet® legkisebb felvehet® érték a 0 lesz, mivel a graceful címkézés soránbármelyik csúcsnak a címkéje lehet 0. Mivel indításkor a gráf élei nincsenek
címkézve, így az élcímkéknek a listája kezdetben üres lesz.
(ii.) Ha az éleknek a listájában nincs (−1)-es elem, akkor találtunk egy lehetséges
megoldást. A megoldások között lehetnek azonosak, a szimmetria miatt.
(iii.) Ha egy csúcs nem volt még kiterjesztve ilyen címkével, azaz még nem volt
ilyen címkéj¶ csúcs, és a szomszédos csúcsok által generált él címkéje nemszerepel benne a jelenlegi élcímkék listájában, akkor jegyezzük fel ezeket, ésfolytassuk tovább a következ® csúcsnak az ellen®rzésével. Ha már szerepelaz élcímkék listájában a csúcsok által generált élcímke, akkor vessük el ezt a
csúcscímkét, és folytassuk tovább a következ® csúcscímkével, ameddig csak
lehet.
(iv.) Ha egy csúcs volt már kiterjesztve, azaz eddig megfelelt a graceful feltételnek, de nincs olyan szomszédos csúcsa ami már ne lett volna kiterjesztve
ebb®l a csúcsból, akkor nem lehetséges az eddigi csúcscímkékkel a kiterjesztés, így ebb®l a csúcsból visszalépünk egy már hamarabb vizsgált szomszédos csúcsához, és folytatjuk tovább a csúcsok vizsgálatait.
Az algoritmus a következ®képpen néz ki a gyakorlatban. Ez az algoritmus
implementálva van Python, illetve Java nyelven is. Viszont mivel a beépített
gráfok a Cocalc matematikai csomagban szerepelnek, és ennek alapja a Python
nyelv, így én is a Python programnyelvet választottam a további implementációk
során.

8

FEJEZET 2.

GRACEFUL CÍMKÉZÉS KERESÉSEGraceful-backtrack algoritmus

1

def kiterjesztheto(G,csucs,cimkek,l,elcimkek):

2
3
4
5
6
7
8
9
10
11
12

if l in cimkek:
return False
seged = list()
for szomszed in G[csucs]:
if cimkek[szomszed] != -1:
ertek = abs(l - cimkek[szomszed])
if (ertek in elcimkek) or (ertek in seged):
return False
seged.append(ertek)
return True

13
14
15
16
17
18
19
20
21
22

def graceful_backtrack(G, elek, cimkek, index, elcimkek):
if cimkek.count(-1) == 0:
with open('graceful_cimkek.txt', 'a') as filehandle:
for listaelem in cimkek:
filehandle.writelines("%s " %pozicio for pozicio in cimkek)
filehandle.writelines("\n")breakreturn True

23
24
25
26

for l in xrange(0,len(elek)+1):
if kiterjesztheto(G, index, cimkek, l, elcimkek):
cimkek[index] = l

27
28
29
30
31

for szomszed in G[index]:
if cimkek[szomszed] != -1:
elcimkek.add(
abs(cimkek[index]-cimkek[szomszed]))32
33

graceful_backtrack(G,elek,cimkek,index+1,elcimkek)

34
35
36
37
38

cimkek[index] = -1
for szomszed in G[index]:
if cimkek[szomszed] != -1:
elcimkek.discard(abs(l-cimkek[szomszed]))39
40

return False

Ez az algoritmus jól m¶ködik, hiszen vegyünk egy egyszer¶ fagráfot, legyen
ez P3 . Ennek az útgráfnak 3 darab csúcsa van, és 2 darab éle. A program futtatása során a következ® eredményeket kapjuk: [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1].

2.2.

BACKTRACK-ALGORITMUS ÉS A GRACEFUL CÍMKÉZÉS

9Azaz, izomorától eltekintve, megkaptuk a P3 gráf csúcsainak összes lehetséges
címkézését.
Azonban, attól függetlenül, hogy az algoritmus véges sok lépés után megadja
a gráfnak az összes csúcscímkézését, a probléma nehézségét az adja, hogy vizsgálva például az útgráfokat, nehéz minden osztálybeli gráfra megadni képletet.
Továbbá, az sem könnyíti meg a helyzetünket, hogy sokszor még kis gráfok esetén (mondjuk 10 csúcsú gráfok esetén), sokszor órákba, s®t napokba is telhet,
mire az algoritmus véget ér. Ennek megoldására általában meg szokták osztani
a magokat, és megpróbálják a programot különálló részenként egyszerre végrehajtani, hogy így gyorsabban eredményhez tudjunk jutni. Másik megoldás az,
ha videokártyát használunk a gyorsítás során. A CUDA, az NVIDIA grakus
processzorainak általános célú programozására használható környezete, amit általában adatok elemzésénél, és neurális hálózatok esetén használnak.
Viszont a backtrack-algoritmus rekurzív ebben az esetben, és így szinte lehetetlena szálasítása Python és Java nyelvek alatt. Így az osztályok kevés számú csúcsú gráfjaira kell a graceful algoritmusunkat lefuttatni, és az összes címkézési
lehet®ségek között kell szabályszer¶séget keresnünk, amely nagyobb csúcsú gráfok esetén is helyes graceful címkézést eredményez.
Ezen algoritmust használtam fel az álkerék gráfok páratlan esetének vizsgálata
során. Ha az n = 5 esetet vizsgáljuk, és erre futtatjuk le a backtrack-algoritmust,akkor az élek száma miatt, viszonylag nagy lesz a futásid®. Viszont, feltételezhetjük,
hogy a központi csúcs a 0 címkével rendelkezik. Ebben az esetben, néhány óra
alatt megkapjuk az összes lehetséges megoldást, amely 0-val kezd®dik. Továbbsz¶kíthetjük a kört, abban az esetben, hogyha feltesszük, hogy a bels® gy¶r¶jében
található csúcsokhoz a legnagyobb címkéket rendeljük, hiszen 0 központi csúcs
miatt, szükségünk van ezen legnagyobb címkékre is. Ebben az esetben már csak
10 darab csúcsra kell lefuttatni az algoritmus, és ezekben kell részsorozatokat
keresnünk. Így ezen feltételek mellett, már csak 1358 darab megoldást kapunk.
Hasonlóan kell eljárni az n = 7 esetben is. Ha legeneráljuk az összes lehetséges megoldást ebben az esetben is ezen feltételek mellett, akkor az így kapott
megoldások, illetve az n = 5 megoldásai alapján kell a sorozatot meghatározni.
Ha megtaláltuk ezeket a részsorozatok, akkor a páratlan esetr®l is be lehet látni, hogy bármely n esetén, ahol n páratlan, létezik graceful címkézése az álkerék
gráfnak.
Hasonlóan kell megvizsgálni azokat a gráfokat is, amelyeket a Mycielski-konstrukció
során alkotunk meg. Vegyük az C7 gráfot. El®ször alkalmazzuk erre a gráfra abacktrack-algoritmust, és gyártsuk le az összes lehetséges csúcscímkézését. Továbbá, alkalmazzuk erre a gráfra a Mycielski-konstrukciót. Az így kapott gráfot adjuk
meg a backtrack-algoritmusnak. Az algoritmus véges sok lépés után leáll. Hasonlóan kell eljárni a többi Mycielski-gráf esetén is, és az el®z® esethez hasonlóan
részsorozatokat kell keresgélni a listákban.

10

FEJEZET 2.

GRACEFUL CÍMKÉZÉS KERESÉSEÍgy a backtrack-algoritmus, bár megtalálja az összes lehetséges megoldást véges
id®n belül, viszont a futási ideje nagyon rossz, illetve a szimmetria miatt rengeteg
megoldást fog adni. Így a backtrack-algoritmust célszer¶bb arra használni graceful gráfok esetén, hogy belássuk azt, hogy az adott gráf nem graceful gráf.

3. Hadamard-mátrixok és graceful
címkézés

3.1. Hadamard-mátrixok
A Hadamard-mátrixokról az els® publikációk [5] a 19. században jelentek meg.
J.J.Sylvester nevéhez f¶z®dik a mátrixoknak a deniálása, de nevüket J.S.Hadamardról kapták, aki a 19. század végén jellemezte ezeket a mátrixokat.

3.1.1. Deníció. Egy An×n mátrixot Hadamard-mátrixnak nevezünk, ha minden eleme ±1, illetve sorai páronként ortogonálisak.

3.1.1. Tétel. Ha An×n és minden elemére teljesül, hogy |aij | ≤ 1, akkorn|det(A)| ≤ n 2 .
Bizonyítás. Legyenek az A mátrix sorai rendre a1 , a2 , . . . , an .

Továbbá azt istudjuk, hogy a det(A) az A mátrix sorvektorai által kifeszített paralelepipedon
térfogata. Mivel|a1 | · |a2 | · . . . · |an |a paralelepipedon éleinek szorzata, így a következ® igaz:|det(A)| ≤ |a1 | · . . . · |an |.

Viszont a tétel alapján
1

1|ai | = (a2i1 + a2i2 + . . . + a2in ) 2 ≤ n 2

adódik. Tehát |det(A)| ≤ n 2 . Egyenl®ség pontosan akkor áll fenn, hogyha az A
mátrix sorai ortogonálisak.
n

3.1.2. Tétel. Legyen An×n mátrix, amelynek minden eleme ±1. Ekkor a következ®
állítások ekvivalensek:n(i.) |det(A)| = n 2 ,(ii.) AAT = n · In ,(iii.) AT A = n · In .

11

12

FEJEZET 3.

HADAMARD-MÁTRIXOK ÉS GRACEFUL CÍMKÉZÉSBizonyítás. (i.) → (ii.) Mivel a mátrix egy sorvektora (±1, ±1, . . . , ±1) alakú, így

ennek hossza√n lesz. Így adódik, hogy


√ 2

n
0
...
0
1 0 ... 0
√ 2




n ...
0 
0 1 . . . 0
 0


 .
.
..  = n ·  .. . . . . .. ... ...
 .
.
. .
. 
.
 .

√ 2
0 ... 0 1
n
0
...
0

(ii.) → (iii.)
AAT = n · In
AT AAT = AT n · In
AT AAT A = AT n · In A
AT A = n · In(iii.) → (i.) Induljunk ki az
AT A = n · In

egyenletb®l. Az egyenl®ség a mátrixok determinánsainak vizsgálatakor is fennáll,
tehát
det(A) · det(AT ) = nn .

Ebb®l egyb®l adódik, hogydet(A)2 = nn ,amelyb®l gyökvonással adódik, hogyn|det(A)| = n 2 .

3.1.3. Tétel. Ha létezik An×n Hadamard-mátrix, akkor n = 1, n = 2, n ≡ 0(mod 4) közül az egyik teljesül.
Bizonyítás. n = 1 és n = 2 esetén is léteznek Hadamard-mátrixok.

n=1:

n=2:



±1



,

!
+1 +1
.
+1 −1

Így feltehet®, hogy n ≥ 3. Azt tudjuk, hogyha egy Hadamard-mátrix tetsz®legessorát megszorozzuk (−1)-gyel, akkor szintén Hadamard-mátrixot fogunk kapni.
Így feltehetjük, hogy A legels® sora csak 1-ket tartalmaz. Mivel a mátrix sorai ortogonálisak, így két sor pontosan n2 helyen különbözik, vagy egyezik meg. Legyenn = 2k . Ekkor a mátrix következ® sorának els® k eleme legyen 1, második k

3.2.

13

EGYSZERSÍTETT HADAMARD-MÁTRIXOK

eleme pedig legyen (−1). Tegyük fel, hogy a harmadik sorban s darab 1 van azels® k pozíció bármelyik helyén. Ebb®l adódik, hogy a második k pozícióban csak(k − s) darab 1 szerepelhet. Vegyük a két sor skaláris szorzatát. Így kapjuk, hogy
0 = s − (k − s) − (k − s) + s = s − k + s − k + s + s = 4s − 2k. Amib®l adódik,hogy s = n4 .
Ha Hadamard-mátrixokat szeretnénk alkotni, akkor annak legkönnyebb módja Sylvester-eljárását követése. Az eljárás során semmi másra nincs szükségünk
csak Hadamard-mátrixokra, illetve egy m¶veletre, ez a bizonyos Kronecker-szorzatm¶velet.

3.1.4. Tétel. Ha An×n Hadamard-mátrix, akkor

A A
A −A

!
is Hadamard-mátrix.

Bizonyítás. Mivel A Hadamard-mátrix, így elemei csak ±1 lehetnek.

Így −A
!

A A
.
A −A

elemei is csak ±1 lehetnek. Továbbá, legyen az új mátrixunk B =Ekkor B elemei csak ±1 lehetnek az el®z®ek miatt. Számoljuk ki BB T -t. Ekkor
T

BB =

A A
A −A
=

!
·

!T
A A
=
A −A

2AAT
0

0
2AAT

A A
A −A

!
= 2n ·

!

AT
AT

·

In 0
0 In

AT
−AT

!
=

!
.

3.1.5. Tétel. n = 2m esetén létezik n × n-es Hadamard-mátrix, ahol m ∈ Z+ .
Bizonyítás. Az el®z® tétel véges sokszori alkalmazásával kapjuk az állítást.

3.2. Egyszer¶sített Hadamard-mátrixok
A Hadamard-mátrixok ismertetése, illetve a mátrixok konstrukciója után látható,
hogy bár a mátrixok n×n mátrixok, és minden elem ±1, viszont ha ezt a mátrixot
egy az egyben szomszédsági mátrixnak tekintenénk, az így kapott gráf nem lenne
egyszer¶, hiszen az mátrix els® eleme miatt keletkezne hurokél. Továbbá, azt isfontos megjegyezni, hogy az els® csúcs a mátrixban szomszédos a mátrix összes
csúcsával.
Így ahhoz, hogy számunkra megfelel® szomszédsági mátrixot kapjunk, az alábbi
módosításokat kell elvégezni a Hadamard-mátrixokon. El®ször is vegyünk egy
olyan transzformációt, ami a mátrix elemein hat, és a −1 érték¶ elemekb®l 0-t
készít, míg a többi elemet békén hagyja, magyarul cseréljük ki a mátrix összes−1 elemét 0-ra. Továbbá, hagyjuk el azokat a csúcsokat amikb®l minden csúcsba megy él. Ez a legels® csúcs, így elhagyjuk az els® sort, és az els® oszlopot.

14

FEJEZET 3.

HADAMARD-MÁTRIXOK ÉS GRACEFUL CÍMKÉZÉS

Végül vegyünk egy A-val jelölt mátrixot, amely (n − 1) × (n − 1) mátrix, ésa f®átlón kívül csak 0-kat tartalmaz, míg a f®átlóban az elemek megegyeznek
a Hadamard-mátrixból készített új mátrixunk f®átlóbeli elemeivel. Vonjuk ki
ezt az A mátrixot a módosított Hadamard-mátrixból. Az így kapott mátrixban
a f®átlóban már csak 0 elemek fognak szerepelni, míg a többi elem változatlan
marad. Az így kapott (n−1)×(n−1) mátrix szomszédsági mátrixnak tekinthet®,
amit az n × n Hadamard-mátrixból képeztünk. Az így kapott mátrixot nevezzük
az n × n Hadamard-mátrix egy csonkított Hadamard-mátrixának.
Példa. Tekintsük a 8 × 8-as Hadamard-mátrixot. Jelöljük ezt H8 -cal.



1
 1


 1

 1
H8 = 
 1


 1

 1
1

1
−1
1
−1
1
−1
1
−1

1
1
−1
−1
1
1
−1
−1

1
−1
−1
1
1
−1
−1
1

1
1
1
1
−1
−1
−1
−1

1
−1
1
−1
−1
1
−1
1

1
1
−1
−1
−1
−1
1
1


1
−1 


−1 

1 
.
−1 


1 

1 
−1

(3.2.1)

A bel®le konstruált csonkított Hadamard-mátrixot jelöljük H7 -tel, amely akövetkez®képpen néz ki.


0

 1

 0

H7 = 
 1
 0


 1
0

1
0
0
1
1
0
0

0
0
0
1
0
0
1

1
1
1
0
0
0
0

0
1
0
0
0
0
1

1
0
0
0
0
0
1

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

(3.2.2)Ha ezt, mint szomszédsági mátrix tekintjük, akkor az általa generált gráf
egyszer¶ lesz, illetve mivel a csonkított Hadamard-mátrix minden sora azonos súlyú, azaz az 1-sek darabszáma minden sor esetén megegyezik , így az egyszer¶sítés
után kapott mátrixból képzett gráfnak, csak másodfokú, illetve harmadfokú csúcsai lehetnek. Hiszen, eredetileg egy csúcs kivételével minden csúcsnak a fokszáma
3 volt. Viszont a f®átlónak az egyszer¶sítése után, csökkenhet bizonyos csúcsoknak a fokszáma.

3.2.

EGYSZERSÍTETT HADAMARD-MÁTRIXOK

15

3.1. ábra. H7 irányítatlan gráfja
Tekintsük ezt a gráfot. Erre a gráfra alkalmazzuk az ismert backtrack-gracefulalgoritmust. Ennek a gráfnak is van graceful címkézése, az összes lehetséges
címkézés 216-féle lehet.
Vizsgáljuk meg ezután a következ® Hadamard-mátrixból alkotott csonkított Hadamard-mátrixot, amely a H11 lesz. Hasonlóan az algoritmus ebben az esetben ismegoldásokkal tér vissza, viszont ebben az esetben a futási id® exponenciálisann®. Így egy átlagos számítógép esetében, a futási id® az összes megoldás megtalálásához ebben az esetben, körülbelül 10-12 nap. A futtatás során 10540 darab
megoldást talált a programunk, amely a szimmetria miatt tartalmazhat azonos
címkézéseket is, csak más sorrendben. Így a H7 , illetve a H11 esetében is létezik
graceful címkézés. Ezzel a gráfcsaláddal kapcsolatosan a sejtésem az, hogy az így
megkonstruált gráfoknak létezik graceful címkézése.

4. Speciális graceful körgráfok
implementálása

Ebben a fejezetben speciális körgráfokat szeretnék bemutatni, amelyeket a SageMath programcsomag segítségével implementáltam. Ezek a gráfok mind a körgráfból keletkeztek, viszont mindegyik gráf jellegzetes tulajdonságokkal bír.

4.1. Cn gráfok
4.1.1. Deníció. Legyen Cn = (V, E, ϕ) véges gráf. Legyenek Cn csúcsai rendre

v1 , v2 , . . . , vn . Ha 1 ≤ i ≤ n − 1, akkor a vi csúcs legyen szomszédos a vi+1
csúccsal. Továbbá, ha i = n, akkor vn legyen szomszédos a v1 csúccsal. Az így
konstruált gráfot n csúcsú körgráfnak nevezzük, amelyet Cn -nel jelölünk.

4.1.1. Tétel. A Cn gráf pontosan akkor graceful gráf, hogyha n ≡ 0, 3 (mod 4).
Bizonyítás. El®ször is vegyük észre, hogy a körgráfok tartalmaznak Euler-vonalat.

Viszont, hogyha egy gráf tartalmaz Euler-vonalat, akkor az pontosan akkor lehet
graceful, hogyha n ≡ 0, 3 (mod 4). Ebben az esetben, legyen V (Cn ) == {v0 , v2 , . . . , vn−1 }.

(i.) Ha n ≡ 0 (mod 4), akkor deniáljuk az f csúcscímkézést a következ®képpen:
Ha 0 ≤ i ≤ n − 2, és i páros, akkori
f (vi ) = .
2

Ha 1 ≤ i ≤ n2 − 1, és i páratlan, akkor
f (vi ) = n −

i−1
.
2

Végül, ha n2 + 1 ≤ i ≤ n − 1, és i páratlan, akkor
f (vi ) = n −

i−1
− 1.
2

(ii.) Ha n ≡ 3 (mod 4), deniáljuk az f csúcscímkézést a következ®képpen:
Ha 0 ≤ i ≤ n − 1, és i páros, akkori
f (vi ) = .
2

17

18

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

Ha 1 ≤ i ≤ n+1
2 − 1, és i páratlan, akkor
f (vi ) = n −

i−1
.
2

Végül, ha n+1
2 + 1 ≤ i ≤ n − 2, és i páratlan, akkor
f (vi ) = n −

i−1
− 1.
2

Mivel a tétel bizonyítása konstruktív, így könnyen lehet implementálni. El®ször
is a címkéket fogom elkészíteni a gráf csúcsaihoz, azaz az f függvényt fogomdeniálni. Ezután felhasználom, hogy a körgráf implementálva van a SageMath
programcsomagban, és egyszer¶en csak hozzárendelem a címkéket.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1
2
3
4
5

def Labels(n):L=[]
if(n%4==1 or n%4==2):
return 'A gráf nem graceful gráf!'
elif(n%4==0):
for i in range(1,n+1):
if(i%2!=0):
L.insert(i,(i-1)/2)
else:
if(i<=n/2):
L.insert(i,n+1-i/2)
else:
L.insert(i,n-i/2)
elif(n%4==3):
for i in range(1,n+1):
if(i%2==0):
L.insert(i,n+1-i/2)
else:
if(i<=(n-1)/2):
L.insert(i,(i-1)/2)
else:
L.insert(i,(i+1)/2)
return L

def Cycle_graph(n):labels=Labels(n)G=graphs.CycleGraph(n)G.relabel(labels,inplace=True)for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))

4.2.

6
7

19

Bn,n GRÁFOK

return G.graphplot(edge_labels=True,edge_color='blue',vertex_color='yellow',vertex_size=200,graph_border=True).show()

4.1. ábra. C12 gráf

4.2. Bn,n gráfok
4.2.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. V csúcsai legyenek

rendre v0 , v1 , . . . , vn , u0 , u1 , . . . , un . Tekintsük a v0 csúcsot, és kössük össze éllel
az összes csúccsal. Ezután tekintsük az u0 csúcsot, és kössük össze éllel az összes
csúccsal, kivéve v0 -val, hiszen a gráf egyszer¶. Az így konstruált G gráfot Bn,n -neljelöljük, és sapka gráfnak nevezzük.
Megjegyzés. A sapka nevet a gráf jellegzetes kinézete alapján kapta. Továbbá err®la gráfról Samir Vaidya és N. H. Shah 2013-as cikkében [6] olvashattunk el®ször.

4.2.1. Tétel. A Bn,n gráf egy graceful gráf.
Bizonyítás. Tekintsük el®ször a Bn,n gráfot. Ennek a csúcsai rendre v0 , v1 , . . . , vn ,u0 , u1 , . . . , un . Továbbá, v0 és u0 jelölje a két kitüntetett csúcsot. Így enneka gráfnak összesen 2n + 2 darab csúcsa van, azaz |V (Bn,n )| = 2n + 2, illetve
4n + 1 darab éle, azaz |E(Bn,n )| = 4n + 1. Tekintsük a következ® csúcscímkézést
f : V (G) → {0, 1, . . . , 4n + 1} esetén.

Legyenf (v0 ) = 0,

illetvef (u0 ) = 4n + 1.

illetvef (ui ) = f (vn ) + i.

Ha 1 ≤ i ≤ n, akkor
f (vi ) = i,

20

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

Ez az f függvény viszont a graceful tulajdonság miatt, deniál egy f ∗ bijektív
függvényt, amely az élekhez rendel címkéket, vagy számokat.
Azaz f ∗ : E(G) → {1, 2, . . . , 4n+1}. Mivel az f ∗ egy bijektív függvény, értékkészlete {1, 2, . . . , 4n+1}, így f graceful címkézése Bn,n -nek, azaz a Bn,n gráf gracefulgráf.
A SageMath programcsomag programozási nyelve a Python programnyelv.
Viszont ebben a csomagban már az alapvet® függvények implementálásra kerültek, így azokat a függvényeket már nem kell nekünk megírnunk, hanem importálás
segítségével nyugodtan felhasználhatjuk ezeket.
Az implementálás során egy egyszer¶ függvényt deniáltam, amely bemenetként
a Bn,n gráf n értékét várja. A függvény lefutása után egy listát fog visszaadni,
amiben szerepelni fognak a csúcsoknak a címkéi. A címkéknek a konstrukciója abizonyításban leírt módon fog zajlani.

1
2
3
4
5
6
7
8
9
10
11
12
13

def Labels(n):L=[]L.insert(0,0)
L.insert(1,4*n+1)
szamlalo=2
for i in range(1,n+1):
L.insert(szamlalo,i)szamlalo=szamlalo+1
temp=len(L)for i in range(1,n+1):
L.insert(szamlalo,L[temp-1]+i)
szamlalo=szamlalo+1
return L

Bár a SageMath-ban vannak beépített gráfok, viszont a csúcsok hozzárendelésekor nekünk gyelnünk kell az egyértelm¶ hozzárendelésre. Sajnos a beépített
gráfoknál az indexelés miatt gyakran a listánk elemeit nem lehet hozzárendelnia csúcsokhoz. Így egy függvényt deniálunk, amely el®ször is felépíti a kívánt
gráfot. Ennek alapértelmezetten a csúcsok címkéi 0-tól (2n − 1)-ig tartanak.
A hozzárendelés után a vizuális részét is nekünk kell megtervezni, mivel a gráf
elkészítése után a SageMath nem ugyanúgy fogja szemléltetni a gráfokat a futtatások után. Továbbá, el®fordulhat, hogy néhány csúcsot ugyanarra a koordinátára
fog helyezni a beépített függvény. Viszont lehet®ségünk van koordináták segítségével megadni, hogy hogyan szeretnénk ábrázolni a gráfunkat. Ehhez csak kikell számolni az X , illetve Y koordinátákat. Jelen esetben a két kitüntetett csúcson kívül minden csúcsot kör struktúrában jelenítettem meg, míg a két kimaradó
csúcsot a körön kívülre helyeztem, az átláthatóság miatt.

4.2.

21

Bn,n GRÁFOK

Az n bemenetre csak azt követeljük meg, hogy pozitív egész szám legyen, hiszen
már n = 0 esetén is létezik gráf. Ez a gráf ebben az esetben a K2 gráf lesz, azaz
a 2 csúcsú teljes gráf, amir®l tudjuk, hogy graceful gráf.

4.2. ábra. B5,5 gráf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4.3. ábra. B10,10 gráf

def Cap_graph(n):if n>0:labels=Labels(n)G=Graph()G.add_vertex(0)G.add_vertex(2*n+1)
G.add_edges([(0,2*n+1)])
for i in range(1,2*n+1):
G.add_edges([(0,i)])G.relabel(labels,inplace=True)labels.pop(0)labels.pop(0)for i in labels:
G.add_edges([(4*n+1,i)])pos_dict={}
j=0
for i in labels:
x = 3*float(2*cos(pi/2 + ((2*pi)/(2*n))*j))y = 3*float(2*sin(pi/2 + ((2*pi)/(2*n))*j))j=j+1
pos_dict[i] = [x,y]pos_dict[0]=[10,10]
pos_dict[4*n+1]=[-10,10]
for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',
vertex_size=300).show()
else:

22

28

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

print ("Ilyen paraméterrel a gráf nem graceful gráf!")4.3. Gn gráfok
4.3.1. Deníció. Tekintsük a Cn = (V, E, ϕ) körgráfot, ahol V = {v1 , v2 , . . . , vn }.
Vegyünk egy v ∈/ V csúcsot, és válasszunk egy vi ∈ Cn (i = 1, . . . , n) tetsz®leges
csúcsot. Legyen v szomszédos azokkal a csúcsokkal, amellyel a vi csúcs is szomszédos volt. Jelöljük az így adódó új gráfot Gn -nel.

Megjegyzés. Hasonlóan, mint az el®z® gráfcsaládnál itt is Samir Vaidya deniálta

ezeket a gráfokat. A cikkben [7] azonban a konstruktív bizonyítás során
az n ≡ 0 (mod 4) eset hibásan szerepel. Ha az ® általa leírt konstrukciót használnám, akkor n = 8-ra még helyes lenne a címkézés, viszont nagyobb n esetén már
az éleknek a számozása nem lenne bijektív, így nem lehet graceful a gráf. A hibaazf (vi ) = (n + 2) −

i−1
,
2

ami helyett a helyes formula a következ® lenne:f (vi ) = (n + 2) −

i−1
2


− 1.

Továbbá, ugyanebben az esetben, hogyha az i = n+4
2 + 1, akkor a megadott képlet
helytelen eredményt adhat. A helyes címke a vi csúcs esetén a következ® lenne:f (vi ) =

n+i−1
.
2

4.3.1. Tétel. Ha 3 ≤ n, akkor a Gn gráfok graceful gráfok.
Bizonyítás. Legyenek v1 , v2 , . . . , vn a Cn gráf csúcsai, és készítsük el a fent leír-

taknak megfelel®en a G gráfot. Tegyük fel, hogy a tetsz®legesen kiválasztott csúcs
a v1 volt, és az új csúcsot jelöljük v -vel. Legyen f : V → {0, 1, . . . , n + 1}, ésdeniáljuk a következ®képpen:(i.) Az n ≡ 0 (mod 4) eset, ahol n 6= 4.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:
f (v) = 0,

illetvef (v1 ) =Továbbá, ha 2 ≤ i ≤ n2 , és i páros:f (vi ) = (n + 2) −


i−2
.
2

n
+ 1.
2

4.3.

23

Gn GRÁFOK

Ellenkez® esetben:
f (vi ) =


i−1
.
2

f (vi ) =

n+i−1
.
2



Ha i = n+4
2 + 1:
Ha n2 + 3 ≤ i ≤ n, és i páratlan:f (vi ) = (n + 2) −Ellenkez® esetben:
f (vi ) =

i−1
2


− 1.

i−2
.
2

(ii.) Az n ≡ 1 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:
f (v) = 0,

illetvef (v1 ) =n+1.
2

Továbbá, ha 2 ≤ i ≤ n+1
2 , és i páros:f (vi ) = (n + 2) −Ellenkez® esetben:

f (vi ) =


i−2
.
2


i−1
.
2

Ha n+32 ≤ i ≤ n, és i páratlan:f (vi ) = (n + 2) −Ellenkez® esetben:


i−1
.
2

i
f (vi ) = .
2(iii.) Az n ≡ 2 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:
f (v) = 0,

illetvef (v1 ) =Továbbá, ha 2 ≤ i ≤ n+4
2 , és i páros:f (vi ) = (n + 2) −Ellenkez® esetben:

f (vi ) =


i−2
.
2


i−1
.
2

n
+ 3.
2

24

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

Ha n+82 ≤ i ≤ n, és i páratlan:f (vi ) = (n + 2) −


i−3
.
2

Ellenkez® esetben:
f (vi ) =i+2.
2(iv.) Az n ≡ 3 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:
f (v) = 0,

illetvef (v1 ) =n+1.
2

Továbbá, ha 2 ≤ i ≤ n+1
2 , és i páros:f (vi ) = (n + 2) −


i−2
.
2

Ellenkez® esetben:
f (vi ) =


i−1
.
2

Ha n+32 ≤ i ≤ n, és i páratlan:f (vi ) = (n + 2) −


i−1
.
2

Ellenkez® esetben:if (vi ) = .
2

Az így deniált csúcscímkézés egy f ∗ élcímkézést indukált, ahol az f ∗ bijektív, ígyaz f csúcscímkézés egyben graceful címkézés is, tehát a Gn gráf graceful gráf.
Megjegyzés. A bizonyításban nem esett szó az n = 4, és az n = 6 esetekr®l. Ezzel
a konstrukcióval bár nem címkézhet® jól a gráf, úgy hogy graceful tulajdonságú
legyen, viszont megadható olyan csúcscímkézés, ahol teljesül a graceful tulajdonság.

4.3.

25

Gn GRÁFOK

4.4. ábra. G4 gráf

4.5. ábra. G6 gráf

Hasonlóan, mint az el®z® gráfcsalád esetében, itt is a címkézés implementálásával kell kezdeni, ami a következ®képpen néz ki Python programnyelven:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

26

28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

if i%2==0:
L.insert(i,(n+2)-(i-2)/2)
else:
L.insert(i,(i-1)/2)
else:
if i%2==0:
L.insert(i,i/2)
else:
L.insert(i,(n+2)-(i-1)/2)
elif n%4==2 and n!=6:
L.insert(0,0)
L.insert(1,n/2+3)
for i in range(2,n+1):
if 2<=i<=(n+4)/2:
if i%2==0 :L.insert(i,(n+2)-(i-2)/2)
else:
L.insert(i,(i-1)/2)
if i==(n+4)/2+1:
L.insert(i,i/2)
if (n+8)/2<=i<=n:if i%2==0:
L.insert(i,(i+2)/2)
else:
L.insert(i,(n+2)-(i-3)/2)
elif n%4==3:
L.insert(0,0)
L.insert(1,(n+1)/2)
for i in range(2,n+1):
if 2<=i<=(n+1)/2:
if i % 2==0:
L.insert(i,(n+2)-(i-2)/2)
else:
L.insert(i,(i-1)/2)
else:
if i%2==0:
L.insert(i,i/2)
else:
L.insert(i,(n+2)-(i-1)/2)

67
68

return L

Hasonlóan, mint az el®z® gráfcsalád esetében el®ször itt is a kört kell els®nek
megkonstruálni. Miután megvan a szokásos rendezést használva, illetve a címkéket
felhasználva megkapjuk a Gn gráfot.

4.3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

27

Gn GRÁFOK

def G_n(n):if n>=3:
labels=Labels(n)G=Graph()G.add_vertex()
for i in range(1,n+1):
if i!=n:G.add_edges([(i,i+1)])
else:
G.add_edges([(i,1)])
G.add_edges([(0,2),(0,n)])G.relabel(labels,inplace=True)
pos_dict={}labels_0=labels.pop(0)j=0
for i in labels:
x = 3*float(2*cos(pi/2 + ((2*pi)/(n))*j))y = 3*float(2*sin(pi/2 + ((2*pi)/(n))*j))j=j+1
pos_dict[i] = [x,y]pos_dict[labels_0]=[0,10]
for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_labels=True,
edge_color='blue',vertex_color='yellow',
vertex_size=300,graph_border=True).show()

4.6. ábra. G15 gráf

28

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

4.4. Medál gráfok
Medál gráfokkal (angol nevén Pendant Graphs), már a szakdolgozatomban isfoglalkoztam, ahol különböz® eseteket mutattam be, amelyek függtek a legkisebb
számú címke elhelyezését®l. A most bemutatott formulát 2000-ben Watson ismertette dolgozatában [8].

4.4.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. V csúcsai legyenek
rendre v0 , v1 , . . . , vn−1 , u0 , u1 , . . . , un−1 . Ha 0 ≤ i ≤ n − 2, akkor a vi csúcs legyenszomszédos a vi+1 csúccsal,illetve ha i = n − 1, akkor vn−1 legyen szomszédos a v0
csúccsal. Továbbá, minden 0 ≤ i ≤ n − 1 esetén a vi legyen szomszédos az ui -vel.
Az így konstruált gráfot medál gráfnak nevezzük. Jelöljük Mn -nel.

4.4.1. Tétel. Az Mn gráfok graceful gráfok.
Bizonyítás. A bizonyítás konstruktív módon fog történni. Legyenek Mn csúcsai

rendre v1 , v2 , . . . , vn , u1 , u2 , . . . , un .

(i.) Az n ≡ 0 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:, ha i = 1, 3, . . . , n2 − 1
 i−1
f (vi ) =i
, ha i = n2 + 1, n3 + 3, . . . , n − 1 2n + 1 − i , ha i = 2, 4, . . . , n,illetve(f (ui ) =2n − f (vi ), ha i = 1, 2, . . . , n2
2n + 1 − f (vi ) , ha i = n2 + 1, n2 + 2, . . . , n.

(ii.) Az n ≡ 1 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:


i−1


 n−3
f (vi ) =

2n + 1 − i
2n − i

illetve, ha i = 1, 3, . . . , n, ahol i 6= n+1
2, ha i = n+1
2, ha i = 2, 4, . . . , n−12n+7, ha i = n+3,,.
. . , n − 1,222n − f (vi )
2n + 1 − f (vi )f (ui ) =

2n − 2 − f (vi )
2n − 1 − f (vi ), ha i = 1, 2, . . . , n−32, ha i = n−1
2, ha i = n+1
2
n+5, ha i = n+3
2 , 2 , . . . , n.

4.4.

29

MEDÁL GRÁFOK

(iii.) Az n ≡ 2 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:


i−1


 n −22
f (vi ) =
 2n + 1 − i
2n − i, ha i = 1, 3, . . . , n, ahol i 6= n2, ha i = n2
, ha i = 2, 4, . . . , n2 − 1, ha i = n2 + 1, n2 + 3, . . . , n,illetve
2n − f (vi ) 2n + 1 − f (v )if (ui ) =
 2n − 2 − f (vi )
2n − 1 − f (vi ), ha i = 1, 2, . . . , n2
, ha i = n2 − 1, ha i = n2
, ha i = n2 + 1, n2 + 2, . . . , n.

(iv.) Az n ≡ 3 (mod 4) eset.
Ebben az esetben a következ®képpen deniáljuk az f csúcscímkézést:, ha i = 1, 3, . . . , n−1
 i−1
2
n+7
f (vi ) =i
, ha i = n+3
,
,
.
..,n
2
2

 2n + 1 − i , ha i = 2, 4, . . . , n − 1,

illetve(f (ui ) =2n − f (vi ), ha i = 1, 2, . . . , n+1
2n+5
2n + 1 − f (vi ) , ha i = n+3
2 , 2 , . . . , n.

Az így meghatározott f csúcscímkézés egy f ∗ élcímkézést indukál, ami bijektív,
így teljesül a graceful tulajdonság, tehát Mn graceful gráf.
Megjegyzés. A felhasznált irodalomban a bizonyítás során itt is elírás történt,

mégpedig n ≡ 3 (mod 4) esetben, ahol a helyes érték 2n − i, és nem 2n − 1.
Továbbá, n ≡ 1 (mod 4) esetben, a szerz® n−3értéket adott meg, viszont a2
helyes érték n − 3.
1
2
3
4
5
6
7
8
9
10
11

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

30

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

if j<=n/2:
L.insert(n+j-1,2*n-L[j-1])
else:
L.insert(n+j-1,2*n+1-L[j-1])
if n % 4==1:
for i in range(1,n+1):
if i!=(n+1)/2 and i%2!=0:
L.insert(i-1,i-1)
elif i==(n+1)/2:
L.insert(i-1,(n-3)/2)
elif i<=(n-1)/2 and i%2==0:
L.insert(i-1,2*n+1-i)
else:
L.insert(i-1,2*n-i)
for j in range(1,n+1):
if j<=(n-3)/2:
L.insert(n+j-1,2*n-L[j-1])
elif j==(n-1)/2:
L.insert(n+j-1,2*n+1-L[j-1])
elif j==(n+1)/2:
L.insert(n+j-1,2*n-2-L[j-1])
else:
L.insert(n+j-1,2*n-1-L[j-1])
if n % 4==2:
for i in range(1,n+1):
if i!=n/2 and i%2!=0:
L.insert(i-1,i-1)
elif i==n/2:
L.insert(i-1,n/2-2)
elif i<=n/2-1 and i%2==0:
L.insert(i-1,2*n+1-i)
else:
L.insert(i-1,2*n-i)
for j in range(1,n+1):
if j<=n/2-2:
L.insert(n+j-1,2*n-L[j-1])
elif j==n/2-1:
L.insert(n+j-1,2*n+1-L[j-1])
elif j==n/2:
L.insert(n+j-1,2*n-2-L[j-1])
else:
L.insert(n+j-1,2*n-1-L[j-1])
if n % 4==3:
for i in range(1,n+1):
if i<=(n-1)/2 and i%2!=0:
L.insert(i-1,i-1)

4.4.

58
59
60
61
62
63
64
65
66
67

31

MEDÁL GRÁFOK

elif i<=n-1 and i%2==0:
L.insert(i-1,2*n+1-i)
else:
L.insert(i-1,i)for j in range(1,n+1):
if j<=(n+1)/2:
L.insert(n+j-1,2*n-L[j-1])
else:
L.insert(n+j-1,2*n+1-L[j-1])
return L

A gráf megalkotása:
1
2
3
4
5
6

def Graph(n):G=graphs.CycleGraph(n)for i in range(0,n):G.add_vertex()G.add_edge((i,n+i))
return G

4.7. ábra. M20 gráf

32

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

A gráf ábrázolása:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def draw(G, L):
temp=nR1=20
R2=30
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_color='blue',vertex_color='yellow',vertex_size=200,graph_border=True)

19
20

pl.show(figsize=[4,7])

4.5. Álkerék gráfok
A szakdolgozatomban különböz® speciális kerék gráfokat vizsgáltam, amir®l belátható volt, hogy létezik graceful címkézése ezeknek a gráfoknak. Most viszont nem
új kerekekkel fogom b®víteni a gráfot, hanem épp sz¶kíteni fogom azt. A most
bemutatott gráfokat G. Sethuraman és K. Sankar deniálták 2015-ben kiadottcikkükben [9].

4.5.1. Deníció. Legyen SWn = (V, E, ϕ) egy véges, egyszer¶ gráf. Induljunk ki

a W (n) kerékgráfból. Jelöljük el a középponti csúcsot u0 -val, a többi csúcs pedig
legyen rendre u1 , u2 , . . . , un . Vegyük azokat az éleket, amelyekre u0 illeszkedik, ésosszuk fel azokat. Továbbá, a maradék éleket is osszuk fel hasonlóan. Azaz V == {u0 , u1 , u2 , . . . , un , un+1 . . . , u2n , w1 , w2 . . . , wn } adódik, ahol wi jelöli a maradékélek felosztása során keletkezett újabb csúcsokat.(i = 1, . . . , n) Az így megalkotott SWn gráfot, álkerék gráfnak nevezzük, ahol n a kiinduló kerék gráfnak a
csúcsszáma.

4.5.1. Tétel. Ha 4 ≤ n, és páros, akkor az SWn gráf graceful gráf.
Bizonyítás. Az SWn gráf csúcsainak száma 3n+1, míg éleinek száma 4n. Jelöljük

m-mel az éleknek a számát. Továbbá, legyen f : V (SWn ) → {0, 1, . . . , m} csúcs-

4.5.

33

ÁLKERÉK GRÁFOK

címkézés, és deniáljuk a a következ®képpen:f (u0 ) = 0,(m+1−i
, ha 1 ≤ i ≤ n
2i − 1 − 2n , ha n + 1 ≤ i ≤ 2n.

(

6i − 2, ha 1 ≤ i ≤ n2
4n + 1 − 2i , ha n2 + 1 ≤ i ≤ n.

f (ui ) =Továbbá,f (wi ) =Az így megkonstruált f függvény egy f ∗ bijektív függvényt indukál, amellyel
teljesül a graceful tulajdonság, így SWn graceful gráf.
A cikkben csak a páros esetet mutatták be a szerz®k, a páratlan esettel nem
foglalkoztak, viszont leírták, hogy az a sejtésük, hogy páratlan esetben is ezek agráfok graceful gráfok.
Megvizsgáltam a backtrack-algoritmussal az n = 5, illetve n = 7. A backtrackalgoritmus segítségével pillanatok alatt megoldáshoz juthatunk. n = 5 esetén
legyen a központi csúcsunk v , a bels® csúcsok legyenek v1 , . . . , v5 , míg a küls®
gy¶r¶n lév® csúcsok legyenek v6 , v7 , . . . , v15 . A csúcsok címkéit reprezentáljuk
egy tömbben, azaz [f (v), f (v1 ), f (v2 ), . . . , f (v14 ), f (v15 )].
Ebben az esetben egy lehetséges graceful címkézés a következ®képpen néz ki:[0, 20, 12, 17, 16, 15, 1, 2, 4, 7, 3, 10, 5, 18, 9, 19].
Hasonlóan n = 7 esetén tömb reprezentációban, a graceful címkézés a következ®képpen néz ki: [0, 16, 27, 24, 26, 22, 25, 28, 1, 2, 4, 7, 3, 8, 14, 5, 12, 20, 6, 23, 10, 21].
Továbbá, az implementálás els® lépése még mindig a címkéknek a legyártása lesz.
Viszont a gondot épp a csúcscímkézés deniálása okozza, hiszen a listába az iváltozó szerint kerülnek bele a címkék. A pozíció megadásánál, viszont nem lehetezeket egyszer¶en csak ábrázolni. Részlistákat kell létrehozni, amely segítségévélel®ször a bels® gy¶r¶t fogjuk megalkotni, majd a küls® gy¶r¶t. El®ször a központi
csúcsnak adjuk a címkét, amely minden esetben 0 címke fog lenni. Majd felcímkézzük a bels® gy¶r¶t az egyik részlista címkéivel, illetve hasonlóan a küls® gy¶r¶t amásik részlista címkéivel.
1
2
3
4
5
6
7
8
9
10

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

34

11
12
13
14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

L.insert(j+2*n+1,6*j-2)
elif (n/2)+1<=j<=n:L.insert(j+2*n+1,4*n+1-2*j)return L

def graph(n):labels=Labels(n)L=Labels(n)temp_0=L[n+1:2*n+1]
temp_1=L[2*n+1:3*n+1]
Z=L[1:n+1]
T=L[n+1:3*n+1]
K=[]
j=len(K)for i in range(0,n):K.insert(j,temp_0[i])j=j+1
K.insert(j,temp_1[i])j=j+1
t=K.pop(len(K)-1)
K.reverse()
K.insert(len(K),t)
G=Graph()G.add_vertex(0)for i in range(1,n+1):
G.add_vertex(i)for i in range(n+1,3*n+1):
G.add_vertex(i)G.relabel(labels,inplace=True)for i in range(0,len(K)):
if i!=len(K)-1:
G.add_edges([(K[i],K[i+1])])else:
G.add_edges([(K[i],K[0])])j=0szamlalo=0
for i in range(0,len(K),2):
G.add_edges([(K[i],Z[szamlalo])])szamlalo=szamlalo+1
j=j+1

36
37
38
39
40

pos_dict={}
j=0
for i in Z:
x = 25*float(2*cos(pi/2 + ((pi)/(len(Z)/2))*j))

4.6.

41
42
43

35

SÍN GRÁFOK

y = 25*float(2*sin(pi/2 + ((pi)/(len(Z)/2))*j))j=j+1
pos_dict[i] = [x,y]

44
45
46
47
48
49
50
51

j=0
for i in K:
x = 50*float(2*cos(pi/2 + ((pi)/(len(K)/2))*j))y = 50*float(2*sin(pi/2 + ((pi)/(len(K)/2))*j))j=j+1
pos_dict[i] = [x,y]pos_dict[0]=[0,0]

52
53
54
55
56
57
58
59
60
61

for i in range(4*n,3*n,-1):
G.add_edges([(0,i)])G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',
vertex_size=300).show()
def sub_wheel(n):if n%2==0:graph(n)else:return "Páratlan esetre ez a konstrukció nem hajtható végre!"4.8. ábra. SW8 gráf

4.9. ábra. SW12 gráf

4.6. Sín gráfok
4.6.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. Tekintsük a Pk

útgráfot. Az útgráf minden csúcsán végezzünk zárt fül ragasztást ugyanolyan
m hosszú fülekkel. Ezen fülek nem tartalmaznak közös csúcsot. Az így kapott[Pk , Cm ] gráfot sín gráfnak nevezzük, és jelöljük Sk,m -mel.

36

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

Megjegyzés. Ezeket a gráfokat 2018-ban két indiai kutató S. Venkatesh és N.Amir-thavahini mutatta be el®ször cikkükben [10].

4.6.1. Tétel. Az Sk,m gráf pontosan akkor graceful, hogyha m ≡ 0 (mod 4).
Bizonyítás. Vizsgáljuk meg az Sk,m gráfot. Erre a gráfra a következ®ek igazak:
p := |V (Sk,m )| = mk , és q := |E(Sk,m )| = mk + k − 1. Továbbá, a gráf csúcsai
legyenek i = 1, 2, . . . , k esetén vi,1 , vi,2 . . . , vi,m . Deniáljuk az f csúcscímkézést akövetkez®képpen:

f (v1,1 ) = q,

illetvef (v1,2 ) = 0.

Ha j páratlan, akkor(
f (v1,j ) =mq − ( j−12 ) , ha 3 ≤ j ≤ 2mq − ( j+1
2 ) , ha 2 < j ≤ m.

Ha j páros, és 2 ≤ j ≤ m, akkor
f (v1,j ) =

j
− 1.
2

Ha 2 ≤ i ≤ k, és i páros, akkor
f (vi,1 ) = f (vi−1,m−1 ) − 1,f (vi,2 ) = f (vi−1,m ) + 1,
j−1
f (vi,j ) = f (vi,1 ) −, ha 3 ≤ j ≤ m − 1 és j páratlan,
2

illetve(f (vi,j ) =f (vi,2 ) + 2j − 1 , ha 4 ≤ j ≤ m
2 és j párosjmf (vi,2 ) + 2, ha 2 ≤ j ≤ m és j páros.

Ha 3 ≤ i ≤ k, és i páratlan, akkor
f (vi,1 ) = f (vi−1,m−1 ) − 1,f (vi,2 ) = f (vi−1,m ) + 1,
j−2
f (vi,j ) = f (vi,2 ) +, ha 4 ≤ j ≤ m és j páros,2

illetve(f (vi,j ) =mf (vi,1 ) + j−1
2 − 1 , ha 3 ≤ j ≤ 2 és j páratlan
f (vi,1 ) + j+1, ha m2
2 ≤ j ≤ m és j páratlan.

Az így konstruált f függvény egy f ∗ bijektív élcímkézést indukál, amib®lkövetkezik, hogy teljesül a graceful tulajdonság, így Sk,m graceful gráf.
A címkézés implementálása a fentebb látható módon történik.

4.6.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

SÍN GRÁFOK

def Labels(k,m):L=[]
q=m*k+k-1
L.insert(0,q)
szamlalo=1
for j in range(2,m+1):
if j%2!=0 and 3<=j<=m/2:
L.insert(szamlalo,q-(j-1)/2)
szamlalo=szamlalo+1
elif j%2!=0 and m/2<j<=m:L.insert(szamlalo,q-(j+1)/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,j/2-1)
szamlalo=szamlalo+1
for i in range(2,k+1):
if i%2==0:
L.insert(szamlalo,L[szamlalo-1]+1)
szamlalo=szamlalo+1
temp_0=L[szamlalo-3]-1
temp_1=L[szamlalo-1]
for j in range(3,m+1):
if j%2!=0:
L.insert(szamlalo,temp_0-(j-1)/2)
szamlalo=szamlalo+1
elif j%2==0 and 4<=j<=m/2:
L.insert(szamlalo,temp_1+j/2-1)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,temp_1+j/2)
szamlalo=szamlalo+1
L.insert(szamlalo,temp_0)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,L[szamlalo-3]-1)
szamlalo=szamlalo+1
L.insert(szamlalo,L[szamlalo-3]+1)
szamlalo=szamlalo+1
temp_0=L[szamlalo-2]
temp_1=L[szamlalo-1]
for j in range(3,m+1):
if j%2!=0 and 3<=j<=m/2:
L.insert(szamlalo,temp_0-(j-1)/2)
szamlalo=szamlalo+1
elif j%2!=0 and m/2<j<=m:L.insert(szamlalo,temp_0-(j+1)/2)

37

38

FEJEZET 4.

szamlalo=szamlalo+1
else:
L.insert(szamlalo,temp_1+(j-2)/2)
szamlalo=szamlalo+1

47
48
49
50
51

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

return L

A gráf konstrukciója során el®ször az útgráfot készítjük el, majd zárt füleket ragasztunk rá. A pozicionálás eltolásokkal, és tükrözésekkel valósul meg, így a végs®
gráfunk ábrázolása hasonlít az informatikában használt sín/busz topológiára.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def bus_graph(k,m):
if m%4==0:
G=Graph()labels=Labels(k,m)
temp=0while(temp!=k):for i in range(0+temp*m,m+temp*m):
if i!=m-1+temp*m:G.add_edges([(i,i+1)])
else:
G.add_edges([(i,0+temp*m)])temp=temp+1
for i in range(0,k-1):
G.add_edges([((m-1)+i*m,2*m-1+i*m)])G.relabel(labels,inplace=True)
pos_dict={}S=[]szamlalo=0
for i in range(0,k):S.insert(szamlalo,labels[(m-1)+i*m])szamlalo=szamlalo+1
pos_dict={}x=0
for i in S:
x=x+100
y=0
pos_dict[i] = [x,y]j=1
r=20
temp=0fix=0valto=1
while(temp!=k*m):
if valto%2==0:
for i in range(0+temp,m+temp):
x = r*float(2*cos(pi/2 + ((2*pi)/(m))*j))+fix

4.6.

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

39

SÍN GRÁFOK

y = r*float(2*sin(pi/2 + ((2*pi)/(m))*j))j=j+1
pos_dict[labels[i]] = [x,y]fix=fix+100
temp=temp+m
valto=valto+1
else:
for i in range(0+temp,m+temp):
x = r*float(2*cos(pi/2 + ((2*pi)/(m))*j))+fix
y = r*float(2*sin(pi/2 + ((2*pi)/(m))*j))-80
j=j+1
pos_dict[labels[i]] = [x,-y]
fix=fix+100
temp=temp+m
valto=valto+1
e_edge=[]szamlalo=0
for u,v,l in G.edges():
e_edge.insert(szamlalo,abs(u-v))
szamlalo=szamlalo+1
G.set_edge_label(u,v,abs(u-v))
e_edge.sort()
print("Élek_címkéi: ")print(e_edge)

61
62
63
64
65
66

for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300).show(figsize=[10,20])
else:
print ("Sajnos nem felel meg az m érték a feltételeknek!")

4.10. ábra. S6,8 gráf

40

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

4.7. Ct(Cn) gráfok
4.7.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. Tekintsük a Cn0

körgráfot. A körgráf minden csúcsán végezzünk zárt fül ragasztást ugyanolyan
n hosszú fülekkel. Ezen fülek nem tartalmaznak közös csúcsot. Az így kapott[Cn0 , Cn ] gráfot körlánc gráfnak nevezzük.

4.7.1. Tétel. A [Cn0 , Cn ] gráf, pontosan akkor graceful gráf, ha n0 , n ≡ 0 (mod 4).
Bizonyítás. Legyenek a Cn0 gráf csúcsai rendre v1 , v2 , . . . , vn0 , míg Cn csúcsai

rendre vi,1 , vi,2 , . . . , vi,n , ahol i jelöli, hogy melyik körben található az adott csúcs.
p = n0 + n0 (n − 1) csúcsok száma, és q = n0 + n0 n az élek száma. Deniáljuk az
f csúcscímkét a következ®képpen, ahol f : V ([Cn0 , Cn ] → {1, 2, . . . , q}:f (v1,1 ) = q,
illetvef (v1,2 ) = 0.
j−1, ha j < n2 és j páratlan
 f (v1,1 ) + 2
j+1
f (v1,j ) =f (vi,1 ) − 2, ha n2 ≤ j és j páratlan j −1, ha j páros.
2

Továbbá, ha 3 ≤ i ≤ n0 , i páratlan, és i 6= n20 + 1, akkor
f (vi,1 ) = f (vi−1,n−1 ) − 1,

illetvef (vi,2 ) = f (vi−1,n ) + 1.

Ha i = n20 + 1, akkor
f (vi,2 ) = f (vi−1,n ) + 2.

Ha 3 ≤ j ≤ n, akkor
j−1, ha j < n2 és j páratlan
 f (vi,1 ) + 2
f (vi,j ) =f (vi,1 ) − j+1, ha n2 ≤ j és j páratlan2 f (v ) + j − 1 , ha j páros.
i,2
2

Továbbá, ha 2 ≤ i ≤ n0 , i páros, és i 6= n20 + 1, akkor
f (vi,1 ) = f (vi−1,n−1 ) − 1,

illetvef (vi,2 ) = f (vi−1,n ) + 1.

Ha i = n20 + 1, akkor
f (vi,2 ) = f (vi−1,n ) + 2.

Ha 3 ≤ j ≤ n, akkor
j−1, ha j páros
 f (vi,1 ) + 2
f (vi,j ) =f (vi,2 ) + 2j − 1 , ha 4 ≤ j ≤ n2 és j páros f (v ) + j, ha j páros és n2 < j.
i,22Az így deniált f csúcscímkézés egy f ∗ bijektív élcímkézést indukál, amelyb®lkövetkezik, hogy teljesül a graceful tulajdonság, így a gráf graceful gráf.

4.7.

Ct (Cn ) GRÁFOK

41

A címkézés implementálása a szokásos módon zajlik. Viszont az implementálás
során a cikkben szerepl® formulát alkalmazva nem sikerült legyártani a címkéket,mivel a cikkben egy elírás történt a bizonyítás páros esetében. Ez csak egy szimpla
indexelési hiba, ahol a helyes érték az f (vi,2 ) lenne, és nem az f (vi,1 ).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

def Labels(n_0,n):L=[]
p=n_0+n_0*(n-1)
q=n_0+n_0*nszamlalo=0
L.insert(szamlalo,q)szamlalo=szamlalo+1
L.insert(szamlalo,0)szamlalo=szamlalo+1
for j in range(3,n+1):
if j%2!=0 and j<n/2:
L.insert(szamlalo,L[0]-(j-1)/2)
szamlalo=szamlalo+1
elif j%2!=0 and j>=n/2:
L.insert(szamlalo,L[0]-(j+1)/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,j/2-1)
szamlalo=szamlalo+1
for i in range(2,n_0+1):
if i % 2 ==0:
L.insert(szamlalo,L[len(L)-2]-1)
szamlalo=szamlalo+1
if i!=n_0/2+1:
L.insert(szamlalo,L[len(L)-2]+1)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,L[len(L)-2]+2)
szamlalo=szamlalo+1
temp_1=L[len(L)-2]
temp_2=L[len(L)-1]
for j in range(3,n+1):
if j%2!=0:
L.insert(szamlalo,temp_1-(j-1)/2)
szamlalo=szamlalo+1
elif j%2==0 and 4<=j<=n/2:
L.insert(szamlalo,temp_2+j/2-1)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,temp_2+j/2)
szamlalo=szamlalo+1

42

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

else:
L.insert(szamlalo,L[len(L)-2]-1)
szamlalo=szamlalo+1
if i!=n_0/2+1:
L.insert(szamlalo,L[len(L)-2]+1)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,L[len(L)-2]+2)
szamlalo=szamlalo+1
temp_1=L[len(L)-2]
temp_2=L[len(L)-1]
for j in range(3,n+1):
if j%2!=0 and j<n/2:
L.insert(szamlalo,temp_1-(j-1)/2)
szamlalo=szamlalo+1
elif j%2!=0 and j>=n/2:
L.insert(szamlalo,temp_1-(j+1)/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,temp_2+j/2-1)
szamlalo=szamlalo+1
return L

Mivel egy viszonylag sok csúcsot tartalmazó gráfról beszélünk, így a pozicionálás nem egyszer¶. Az egyszer¶ körök pozicionálása a szokásos módon történt,viszont az átláthatóság miatt, jobbnak láttam, hogyha az alap Cn0 gráfot nem
körnek ábrázolom, hanem bizonyos esetekben cikk-cakkosan.
12
3

def cycles(n_0,n):labels=Labels(n_0,n)G=Graph()

4
5
6
7
8
9
10
11
12
13
14

db=0
temp=0while(db<n_0):
for i in range(0+temp,n+temp):
if i!=n-1+temp:
G.add_edges([(i,i+1)])
else:
G.add_edges([(i,0+temp)])
temp=temp+ndb=db+1

15
16
17
18

temp=1
while(1):

4.7.

19
20
21
22
23
24

Ct (Cn ) GRÁFOK

G.add_edges([(temp*n-1,temp*n)])if (temp*n<len(G.vertices())-n):G.add_edges([(temp*n,(temp+2)*n-1)])
temp=temp+2
else:
break

25
26
27

G.add_edges([(n-1,(n_0-1)*n)])G.relabel(labels,inplace=True)

28
29
30
31

csucsok=[]for i in range(0,n_0):
csucsok.insert(i,[])

32
33
34
35
36
37
38
39
40
41
42
43
44

szamlalo=0
db=0
tul=0
while(tul<len(csucsok)):
for j in range(0,n):
csucsok[tul].insert(szamlalo,labels[db])szamlalo=szamlalo+1
db=db+1
tul=tul+1
for i in range(0,len(csucsok)):
if i%2==0:
csucsok[i].reverse()

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

pos_dict={}
if n_0==4:
j=0
for i in csucsok[0]:x = float(cos(pi/2 + ((2*pi)/len(csucsok[0]))*j))y = float(sin(pi/2 + ((2*pi)/len(csucsok[0]))*j))j=j+1
pos_dict[i] = [x-3,-y+2]
j=0
for i in csucsok[1]:x = float(cos(pi/2 + ((2*pi)/len(csucsok[1]))*j))y = float(sin(pi/2 + ((2*pi)/len(csucsok[1]))*j))j=j+1
pos_dict[i] = [x-3,y-2]
j=0
for i in csucsok[2]:x = float(cos(pi/2 + ((2*pi)/len(csucsok[2]))*j))y = float(sin(pi/2 + ((2*pi)/len(csucsok[2]))*j))
j=j+1

43

44

65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

pos_dict[i] = [x,y-2]
j=0
for i in csucsok[3]:x = float(cos(pi/2 + ((2*pi)/len(csucsok[3]))*j))y = float(sin(pi/2 + ((2*pi)/len(csucsok[3]))*j))j=j+1
pos_dict[i] = [x,-y+2]
else:
db=0
s=0
fix_0=(n_0/2-1)*5
fix_1=4
while(db<n_0/2):
for i in csucsok[s]:x = 2*float(cos(pi + ((2*pi)/len(csucsok[0]))*j))y = 2*float(sin(pi + ((2*pi)/len(csucsok[0]))*j))j=j+1
if s==0:
pos_dict[i]=[x+fix_0,y+fix_1-1]
else:
pos_dict[i]=[x+fix_0,y+fix_1]
fix_0=fix_0-5
if s%2==0:
fix_1=4
else:
fix_1=2
s=s+1
db=db+1
db=0
fix_0=0
fix_1=-4s=n_0/2

97
98
99
100
101
102
103
104
105
106
107
108
109
110

while(db<n_0/2):
j=0
for i in csucsok[s]:x = 2*float(cos(pi + ((2*pi)/len(csucsok[s]))*j))y = 2*float(sin(pi + ((2*pi)/len(csucsok[s]))*j))j=j+1
if s==n_0/2:
pos_dict[i] = [x+fix_0,y+fix_1+1]
else:
pos_dict[i] = [x+fix_0,y+fix_1]
fix_0=fix_0+5
if s%2==0:
fix_1=-4

4.8.

111
112
113
114

45

SÁRKÁNY GRÁFOK

else:
fix_1=-2
s=s+1
db=db+1

115
116
117
118
119
120
121
122
123
124
125
126
127

if n_0<=8:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[5,5])
elif 8<n_0<=16:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[10,5])else:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[15,5])

4.11. ábra. C8 C4 gráf

4.8. Sárkány gráfok
4.8.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. Legyen a G gráf

központi csúcsa v . Tegyük fel, hogy a v csúcs pontosan t darab másik csúccsal
szomszédos, legyenek ezek rendre u1 , u2 , . . . , un . Ragasszunk ezekre a csúcsokra

46

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

egy három hosszú zárt fület, ahol egy csúcs pontosan csak az egyik fülön lehet.
Az így megkonstruált gráfot sárkány gráfnak nevezzük, és Dn -nel jelöljük.

4.8.1. Tétel. Bármely n > 1 esetén a Dn gráf graceful gráf.
Bizonyítás. Jelöljük a Dn gráf zárt fül ragasztásával keletkez® köreinek csúcsait

rendre vi,1 , vi,2 , vi,3 , vi,4 , ahol i jelöli az i-edik kört, és 1 ≤ i ≤ n. Továbbá, jelölje
a központi csúcsot v . A gráf csúcsainak számát jelöljük p-vel, ahol p = 4n + 1,
illetve éleinek számát jelöljük q -val, ahol q = 5n. Ekkor az f csúcscímkézést
deniáljuk a következ®képpen:(i.) Ha i = 1, akkor(
f (v1,j ) =illetve(f (v2,j ) =q − ( j−12 ) , ha j páratlanj−2, ha j páros,

q − 4 + (j − 1) , ha j páratlan, ha j páros.
4 + ( j−22 )(ii.) Ha 3 ≤ i ≤ n, és i páratlan, akkor

i−1
f (vi,1 ) = q − 5
,
2


i−1
f (vi,2 ) = 5
+ 1,
2


i−1
f (vi,3 ) = q − 5− 2,2

illetve



i−1
+ 2.
f (vi,4 ) = 5
2(iii.) Ha 4 ≤ i ≤ n, és i páros, akkor
f (vi,1 ) =f (vi,2 ) = q −f (vi,3 ) =

5i
,
2
5i
+ 2,
2

5i
− 2,
2

illetvef (vi,4 ) = q −

5i
+ 1.
2

Az így deniált f csúcscímkézés egy f ∗ élcímkézést indukál, amely bijektív, ígyteljesül a graceful tulajdonság, azaz a Dn gráf graceful gráf.

4.8.

SÁRKÁNY GRÁFOK

47

Megjegyzés. A feldolgozott cikk [10] bizonyításában az f (v1,j ) esetben hiba történt,hiszen a helyes érték a j − 2 lenne, és nem pedig a 2(j − 2).

Az implementálás a címkék elkészítésével kezd®dik, amely els®ként a központi
csúcsnak a címkéjét adja meg, majd négyesével a köröknek a csúcscímkézést. Jelenesetben t-vel jelöljük a zárt füleknek a számát.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def Labels(t):L=[]L.insert(4*t,3)
for j in range(1,5):
if j%2!=0:
L.insert(j,5*t-(j-1)/2)
else:
L.insert(j,(j-2))
for j in range(1,5):
if j%2!=0:
L.insert(j+4,5*t-4+(j-1))
else:
L.insert(j+4,4+(j-2)/2)
for i in range(3,t+1):
if i%2!=0:
L.insert(i*5-4,5*t-5*(i-1)/2)
L.insert(i*5-3,5*(i-1)/2+1)
L.insert(i*5-2,5*t-5*(i-1)/2-2)
L.insert(i*5-1,5*(i-1)/2+2)
else:
L.insert(i*5-4,5*i/2)
L.insert(i*5-3,5*t-5*i/2+2)
L.insert(i*5-2,5*i/2-2)
L.insert(i*5-1,5*t-5*i/2+1)
return L

A pozicionálás rétegenként történik. El®ször a legyártott címkéket tartalmazó
listát részlistákra osztjuk, amelyb®l épp annyi darab lesz ahány fület ragasztottunk a gráf csúcsaira. A központi csúcsot kezeljük külön esetként, amelyet avégén pozicionálunk. A négy hosszú listákból el®ször vegyük ki az els® elemeket
és ezeket ábrázoljuk egy kör mentén. Ezután ábrázoljuk a listák harmadik elemeit
is ilyen módon, viszont a kör átmér®je kisebb legyen. Végül a listák maradék elemeit folytonosan ábrázoljuk egy kör mentén. Az átmér®je legyen a két másik körátmér®je között.
12
3

def graph(labels,t):alap=t
G=Graph()

48

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

G.add_vertex(0)for i in range(1,5):
G.add_vertices([i])
G.add_edges([(1,2),(2,3),(3,4),(4,1),(3,0)])
temp=4
while(t-1>0):
for i in range(1+temp,1+temp):
G.add_vertices([i*1])
G.add_edges([(1+temp,2+temp),(2+temp,3+temp),(3+temp,4+temp),(4+temp,1+temp),(3+temp,0)])
temp=temp+4
t=t-1
G.relabel(labels,inplace=True)
pos_dict={}
F=[]
db=0
temp=0for i in labels:
if db%3==0 and db!=0:
F.insert(temp,i)
temp=temp+1
db=0
else:
db=db+1
F_0=[]
db=0
temp=0for i in labels:
db=db+1
if db%4==2:
F_0.insert(temp,i)
temp=temp+1
F_1=[]
db=0
temp=0for i in labels:
db=db+1
if db%4==3:
F_1.insert(temp,i)
temp=temp+1
F_2=[]
db=0
temp=0for i in labels:
db=db+1
if db%4==1 and i!=3:

4.8.

50
51
52
53
54
55
56
57

SÁRKÁNY GRÁFOK

49

F_2.insert(temp,i)
temp=temp+1
j=0
for i in F:
x = 10*float(2*cos(pi/2 + ((pi)/(len(F)/2))*j))y = 10*float(2*sin(pi/2 + ((pi)/(len(F)/2))*j))j=j+1
pos_dict[i] = [x,y]

58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

j=0
for i in F_0:
x = 20*float(2*cos(pi/2 + ((pi)/(len(F_0)/2))*j))y = 20*float(2*sin(pi/2 + ((pi)/(len(F_0)/2))*j))j=j+1
pos_dict[i] = [x,y]j=0
if(alap>11):
for i in F_1:
x = 15*float(2*cos(pi/(2.1)+ ((pi)/(len(F_1)/2))*j))y = 15*float(2*sin(pi/(2.1)+ ((pi)/(len(F_1)/2))*j))j=j+1
pos_dict[i] = [x,y]j=0for i in F_2:
x = 15*float(2*cos(pi/(1.9) + ((pi)/(len(F_2)/2))*j))y = 15*float(2*sin(pi/(1.9) + ((pi)/(len(F_2)/2))*j))j=j+1
pos_dict[i] = [x,y]pos_dict[3]=[0,0]G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=200,graph_border=True).show()else:
for i in F_1:
x = 15*float(2*cos(pi/(2.25)+ ((pi)/(len(F_1)/2))*j))y = 15*float(2*sin(pi/(2.25)+ ((pi)/(len(F_1)/2))*j))j=j+1
pos_dict[i] = [x,y]j=0for i in F_2:
x = 15*float(2*cos(pi/(1.8) + ((pi)/(len(F_2)/2))*j))y = 15*float(2*sin(pi/(1.8) + ((pi)/(len(F_2)/2))*j))j=j+1
pos_dict[i] = [x,y]pos_dict[3]=[0,0]G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,graph_border=True).show()

50

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

Végül meghívjuk a függvényeket, és kezeljük azokat az eseteket, amelyek nem
valósíthatók meg ezzel a konstrukcióval.
1
2
3
4
5

def dragon_graphs(t):if t<2:
return "A t paraméter 1-nél nagyobb kell, hogy legyen!"labels=Labels(t)graph(labels,t)

4.12. ábra. D9 gráf

4.9. Körgráfok párhuzamos húrokkal
Az alábbi speciális gráf esetében az a furcsa eset állt el®, hogy alapértelmezetten
van egy formula a csúcscímkézés el®állítására, viszont ez nem annyira szép. Viszont, ha a gráfot alkotó körgráfot nem körgráfnak, hanem két útgráfnak tekintjük,
és egy közös csúccsal összekötjük ezeket, akkor a páratlan esetben sokkal szebb
képlet megadható, amely nem tartalmaz törtrészeket.
Megjegyzés. A cikkek, amiket felhasználtam az egy A. Elumalai, és Sethuraman

Guruswamy 2012-es cikk [11], illetve egy 2017-es A. Solairaju, S. Subbulakshmi,
és R. Kokila cikk [12]. Az els® cikkben az n > 6 esetre adnak bizonyítást, míg amásodik cikkben csak a páratlan esetre adnak bizonyítást, viszont a cikk szerz®i
nem vették gyelembe, hogy ez egy speciális körgráf. Továbbá, a cikkben
elírások
i−1
is történtek, hiszen ®k egy vi csúcs esetén, az f (vi ) = q − 2 értéket adták
lenne, ahol i páratlan. Továbbá, ®kmeg, ahol a helyes érték az f (vi ) = q − i+1
2

4.9.

51

KÖRGRÁFOK PÁRHUZAMOS HÚROKKAL

megkülönböztetnek a cikkükben bizonyos vi csúcsokat, azonban ez nem szükséges,az el®z® javítás miatt. Ha az els® hibát nem javítanánk, még akkor sem lenne jó
a formula ezekkel a megkülönböztetett esetekben sem.

4.9.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. Legyenek a csúcsai

rendre v0 , v1 , . . . , vn−1 , és vezessen él vi -b®l vi+1 , ahol 0 ≤ i ≤ n − 2, és vn−1 b®l vezessen él v0 . Továbbá, ha n páros, akkor legyen vj szomszédos vn−j -vel,ahol 1 ≤ j ≤ n2 − 1. Ha n páratlan, akkor legyen vj szomszédos vn−j -vel, ahol
1 ≤ j ≤ n−1
2 − 1. Az így megkonstruált gráfot párhuzamos húrokkal rendelkez®
körgráfnak nevezzük. Jelöljük ezt CW Pn -vel.

4.9.1. Tétel. Ha n > 6, és n egész, akkor CW Pn graceful gráf.
Bizonyítás. Legyenek a gráf csúcsai rendre v0 , v1 , . . . , vn−1 . Jelöljük a gráf éleinekszámát q -vel, ahol q = 3n−s
2 , és s = 3, ha n páratlan, míg s = 2, ha n páros.
Deniáljuk az f csúcscímkézést a következ®képpen:(i.) Ha n páros, akkor
f (v0 ) = 0,f (v1 ) = 1,
3n − 2,f (vn−1 ) =2
3n − 6i + 2
n−4
f (v2i ) =, ha 1 ≤ i ≤
,
2
4


3n − 6in−4
f (vn−(2i+1) ) =, ha 1 ≤ i ≤,2
4

illetven−4.
f (vn−2i ) = 3i, ha 1 ≤ i ≤4


Továbbá, ha 1 ≤ i ≤ δ , akkor n ≡ 0 (mod 4) esetén, legyen δ =Ha 1 ≤ i ≤ δ , akkor n ≡ 2 (mod 4) esetén, legyen δ = n−4
, és
4

-1.

 n−4 4

f (v2i+1 ) = 3i + 2.

Továbbá,(f (v n2 −1 ) =illetve(f (v n2 ) =3n
43(n+2)
4, ha n ≡ 0 (mod 4), ha n ≡ 2 (mod 4),

3n−8
4
3(n+4)+2
4, ha n ≡ 0 (mod 4), ha n ≡ 2 (mod 4).

Az így deniált f csúcscímkézés egy f ∗ bijektív élcímkézést indukál, amelyb®l következik, hogy teljesül a graceful tulajdonság, azaz a gráf graceful
gráf, ha n páros.

52

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

(ii.) Ha n páratlan, akkor legyen s = n−1
2 , és q = 3s. Ekkor
f (v0 ) = 0,f (vn−1 ) = q,

illetve(f (vi ) =q − i+12i2, ha i páratlan, ha i páros.

Ebben az esetben külön címkézzük el a v0 csúcsot, amelyb®l nem vezet
ki párhuzamos húr, illetve a vn−1 csúcsot is. A többi csúcs alternálva
címkéz®dik el, mint az útgráf esetén. Ez a csúcscímkézés is egy f ∗ élcímkézést indukál, ami szintén bijektív, amib®l következik, hogy a gráf
graceful gráf páratlan esetben is.

Mivel a bizonyításban két esetet különböztettünk meg, így a gráf címkézésének
implementálása során is két függvényt fogok deniálni ennek megfelel®en.
Ha n páratlan:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

def Labels_0(n):L=[]
L.insert(0,0)
q=3*nszamlalo=1
for i in range(1,2*n):
if i%2!=0:
L.insert(szamlalo,q-(i+1)/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,i/2)
szamlalo=szamlalo+1
L.insert(szamlalo,q)
return L

Ha n páros:
1
2
3
4
5
6
7

def Labels_1(n):s=0L=[]L.insert(0,0)
L.insert(1,1)
szamlalo=2
for i in range(2,n):

4.9.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

KÖRGRÁFOK PÁRHUZAMOS HÚROKKAL

53

if i==n-1:
s=(3*n-2)/2
for j in range(1,ceil((n-4)/4)+1):
if i==2*j and j!=ceil((n-4)/4)+1:
s=(3*n-6*j+2)/2
breakelif i==n-(2*j+1) and j!=ceil((n-4)/4)+1:
s=(3*n-6*j)/2
breakelif i==n-2*j :
s=3*j
break
elif i==2*j+1 and j!=ceil((n-4)/4):
if n%4==0 and j!=floor((n-4)/4):
s=3*j+2
breakelif n%4==2 and j!=floor((n-4)/4)+1:
s=3*j+2
breakelif i==(n/2-1):
if n%4==0 :s=3*n/4
breakelif n%4==2 :s=3*(n+2)/4
breakelif i==(n/2):
if n%4==0 :s=(3*n-8)/4
breakelif n%4==2 :s=(3*(n+4)+2)/4
break
if i==3:
print(i,s)
L.insert(szamlalo,s)szamlalo=szamlalo+1
return L

A gráf készítése során csak az n > 6 feltételre kell ügyelni, a pozicionálás aszokásos ábrázolási mód szerint történik.
1
2
3
4

def cycle_graph_with_parallels(n):if n%2!=0:
if n>6:n=(n-1)/2

54

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

labels=Labels_0(n)G=Graph()for i in range(0,2*n+1):
if i!=2*n:G.add_edges([(i,i+1)])
for i in range(0,n):G.add_edges([(i,2*n-i)])G.relabel(labels,inplace=True)
pos_dict={}
j=0
for i in labels:
x = float(2*cos(pi/2 + ((pi)/(len(labels)/2))*j))y = float(2*sin(pi/2 + ((pi)/(len(labels)/2))*j))j=j+1
pos_dict[i] = [x,y]

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

for u,v,l in G.edges():G.set_edge_label(u,v,abs(u-v))
if n<=5:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show()elif 5<n<=10:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[10,5])else:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[15,5])
else:
print("A konstrukció miatt 6<n szükséges.")else:
if n>6 :labels=Labels_1(n)G=Graph()for i in range(0,n):
if i!=n-1:
G.add_edges([(i,i+1)])
else:
G.add_edges([(0,i)])koz=(n/2)-1
db=1
while(db<=koz):
G.add_edges([(0+db,n-db)])
db=db+1

4.9.

51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

55

KÖRGRÁFOK PÁRHUZAMOS HÚROKKAL

G.relabel(labels,inplace=True)
pos_dict={}
j=0
for i in labels:
x = float(2*cos(pi/2 + ((pi)/(len(labels)/2))*j))y = float(2*sin(pi/2 + ((pi)/(len(labels)/2))*j))j=j+1
pos_dict[i] = [x,y]for u,v,l in G.edges():G.set_edge_label(u,v,abs(u-v))
if n<=9:G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show()elif 9<n<=20:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[10,5])else:
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[12,12])
else:
print("A konstrukció miatt 6<n szükséges.")

4.13. ábra. CW P11 gráf

4.14. ábra. CW P14 gráf

56

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

4.10. Körgráfok cikk-cakk húrokkal
Mint a neve is sugallja, ezeknek a gráfoknak is az alapja a Cn gráfok. A különbség
csak az, hogy ezekben a gráfokban egyes csúcsokból nem csak a hozzá legközelebb
álló legnagyobb, és legkisebb sorszámú csúcsba megy él, hanem megengedünk
bizonyos éleket a körgráfon belül is.

4.10.1. Deníció. Egy G = (V, E, ϕ) egyszer¶ gráfot cikk-cakk húros körgráfnak

nevezünk, ha a |V (G)| ≥ 8, és V (G) = {v0 , . . . , vn−1 } esetén a körgráf szomszédos
csúcsaiból kiinduló két darab élen kívül az alábbi feltételek alapján illeszkedik újél a csúcsokra:n+2(i.) Ha n ≡ 0 (mod 4), akkor n−2
2 és 2 csúcsok között illeszkedjen új él.
n+3(ii.) Ha n ≡ 1 (mod 4), akkor n−3
2 és 2 csúcsok között illeszkedjen új éj.
n(iii.) Ha n ≡ 2 (mod 4), akkor n+4
2 és 2 csúcsok között illeszkedjen új él.
n−1(iv.) Ha n ≡ 3 (mod 4), akkor n+5
2 és 2 csúcsok között illeszkedjen új éj.

Jelöljük ezt a gráfot CW Zn -nel.
Ezeket a gráfokat A. Elumalai és A.A. Ephremnath indiai kutatók deniálták
egyik 2013-as cikkükben [13]. Azonban már hamarabb más kutatókat is foglalkoztatott speciális körgráfoknak a létezése. 1985-ben, például Koh és Yap cikkükben
[14] deniálták els®ként a Pk húrral rendelkez® körgráfokat, ahol a körgráf csúcsaira az k csúcsú útgráf végpontjai illeszkedtek. Továbbá, a nevükhöz f¶z®dik agracefulság bebizonyítása az egy darab húrral rendelkez® körgráfok esetében is.

4.10.1. Tétel. Ha n ≥ 8, akkor létezik graceful címkézése az n csúcsú cikk-cakk
gráfnak.
Bizonyítás. Legyen az n csúcsú cikk-cakk körgráf csúcsai rendre v0 , v1 , . . . , vn−1 .

Legyen M = |E(CW Zn )|. Deniáljuk az f csúcscímkézést a következ®képpen:(i.) Ha n ≡ 0 (mod 4), akkor M = 3n−2
2 , ahol n = 4k (k ≥ 2) alakú. Ekkor
f (v0 ) = 0,f (v2i ) = i, ahol 1 ≤ i ≤f (v n+4i−4 ) =2illetvef (v2i−1 ) =

n−4
,
4

n + 4in, ahol 1 ≤ i ≤ ,443n − 2in, ahol 1 ≤ i ≤ .
22

4.10.

57

KÖRGRÁFOK CIKK-CAKK HÚROKKAL(ii.) Ha n ≡ 1 (mod 4), akkor M = 3n−3
2 , ahol n = 4k + 1 (k ≥ 2) alakú. Ekkor
f (v0 ) = 0,f (v n−1 ) =2

3n + 1,4

f (v2i ) = i, ahol 1 ≤ i ≤f (v (n+4i−3) ) =2

f (v2i−1 ) =

n−5
,
4

n−1
n + 4i − 5, ahol 1 ≤ i ≤,443n − 2i − 1
n−1, ahol 1 ≤ i ≤,2
4

illetvef (v (n+4i−1) ) =2

5n − 4i − 1
n−1, ahol 1 ≤ i ≤.
4
4(iii.) Ha n ≡ 2 (mod 4), és k = 2, ahol n = 4k+2 alakú, akkor vegyük a következ®
csúcscímkézést. Legyen C = {v0 , . . . , v9 } és D = {8, 14, 9, 13, 1, 11, 4, 2, 3, 0}.
Ekkor rendeljük egymáshoz az azonos index¶ halmazbeli elemeket, és jelentse azt a (vi , j), hogy a címkézés az i-edik csúcshoz a j -edik címkét rendeli (i = 0, . . . , 9, j = 1, . . . , 14).
Végül deniáljuk a k ≥ 3 esetén a címkéket, ahol M = 3n−2
2 . Ekkor
f (vn−1 ) = 0,f (v n+6 ) =2

f (v n2 ) =3n − 2,4

5n − 6,4

f (v2i+2 ) = i, ahol 1 ≤ i ≤f (v (n−2i+6) ) =2

f (v (n+4i+6) ) =2

f (vn−2i−1 ) =f (v2i−1 ) =

n−6
,
4

n + 8i − 10
, ahol 1 ≤ i ≤ 2,
4

n + 4i + 6
n − 10, ahol 1 ≤ i ≤,4
4n + 2i + 2
n − 10, ahol 1 ≤ i ≤,243n − 2in−2, ahol 1 ≤ i ≤,2
4

illetvef (v4−2i ) = n − 3i + 4, ahol 1 ≤ i ≤ 2.

58

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

(iv.) Ha n ≡ 3 (mod 4), akkor M = 3n−3
2 , ahol n = 4k + 3 (k ≥ 2) alakú. Ekkor
f (v0 ) =3n − 3,2

f (v1 ) = 0,f (v2 ) = n − 2,
f (v2i+1 ) = i, ahol 1 ≤ i ≤

n+1
,
4

n + 4i + 5
n−3, ahol 1 ≤ i ≤
,
4
4
2
n−7
n + 2i + 1, ahol 1 ≤ i ≤,f (vn−2i ) =24f (v (n−4i+5) ) =illetvef (vn−2i+1 ) =n−3
3n − 2i − 3, ahol 1 ≤ i ≤.
2
4

Az így megadott f csúcscímkézés mindegyik esetben egy f ∗ bijektív élcímkézést
indukál, amelyb®l következik, hogy teljesül a graceful tulajdonság, azaz a gráf
graceful gráf.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

4.10.

25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

KÖRGRÁFOK CIKK-CAKK HÚROKKAL

L[2*i-1]=(3*n-2*i-1)/2
L[(n+4*i-1)/2]=(5*n-4*i-1)/4
elif n % 4==2 and n==10:
L=[8,14,9,13,1,11,4,2,3,0]
elif n % 4==2 and n!=10:
for i in range(0,n):L.insert(0,0)
L[n-1]=0
L[(n+6)/2]=(3*n-2)/4
L[n/2]=(5*n-6)/4
for i in range(0,n):if 1<=i<=(n-6)/4:
L[2*i+2]=iif 1<=i<=2:
L[(n-2*i+6)/2]=(n+8*i-10)/4L[4-2*i]=n-3*i+4
if 1<=i<=(n-10)/4:
L[(n+4*i+6)/2]=(n+4*i+6)/4
L[n-2*i-1]=(n+2*i+2)/2
if 1<=i<=(n-2)/4:
L[2*i-1]=(3*n-2*i)/2
elif n % 4==3:
for i in range(0,n):L.insert(0,0)
L[0]=(3*n-3)/2
L[1]=0
L[2]=n-2
for i in range(0,n):if 1<=i<=(n+1)/4:
L[2*i+1]=iif 1<=i<=(n-3)/4:
L[(n-4*i+5)/2]=(n+4*i+5)/4
if 1<=i<=(n-7)/4:
L[n-2*i]=(n+2*i+1)/2
if 1<=i<=(n-3)/4:
L[n-2*i+1]=(3*n-2*i-3)/2
return L

A gráf elkészítése deníció alapján történik az α és β értékekkel.
1
2
3
4
5
6

def ZigZag(n):if n>=8:
labels=Labels(n)G=Graph()if n%4==0:
alpha=(n-2)/2

59

60

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

FEJEZET 4.

SPECIÁLIS GRACEFUL KÖRGRÁFOK IMPLEMENTÁLÁSA

beta=(n+2)/2
elif n%4==1:
alpha=(n-3)/2
beta=(n+3)/2
elif n%4==2:
alpha=(n+4)/2
beta=n/2
elif n%4==3:
alpha=(n+5)/2
beta=(n-1)/2
G.add_vertex(0)if n%4==0:
for i in range(1,alpha+1,2):
G.add_edges([(i,n-i)])
for i in range(1,alpha,2):G.add_edges([(n-i,i+2)])
for i in range(0,n):
if i!=n-1:
G.add_edges([(i,i+1)])
else:
G.add_edges([(0,n-1)])
elif n%4==1:
for i in range(1,alpha+1,2):
G.add_edges([(i,n-i)])
for i in range(1,alpha,2):G.add_edges([(n-i,i+2)])
for i in range(0,n):
if i!=n-1:
G.add_edges([(i,i+1)])
else:
G.add_edges([(0,n-1)])
elif n%4==2:
for i in range(1,beta,2):G.add_edges([(i,n-i)])
for i in range(1,beta,2):G.add_edges([(n-i,i+2)])
for i in range(0,n):
if i!=n-1:
G.add_edges([(i,i+1)])
else:
G.add_edges([(0,n-1)])
elif n%4==3:
for i in range(1,beta,2):G.add_edges([(i,n-i)])
for i in range(1,beta,2):G.add_edges([(n-i,i+2)])

4.10.

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

61

KÖRGRÁFOK CIKK-CAKK HÚROKKAL

for i in range(0,n):
if i!=n-1:
G.add_edges([(i,i+1)])
else:
G.add_edges([(0,n-1)])
G.relabel(labels,inplace=True)
pos_dict = {}j=0
for i in labels:
x = float(2*cos(pi/2 + ((pi)/(len(labels)/2))*j))y = float(2*sin(pi/2 + ((pi)/(len(labels)/2))*j))j=j+1
pos_dict[i] = [x,y]for u,v,l in G.edges():G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300).show()else:
print ("A konstrukció miatt 7<n szükséges.")

4.15. ábra. ZW P15 gráf

4.16. ábra. ZW P20 gráf

5. Speciális graceful fagráfok, ésálrács gráfok implementálása

A speciális körgráfok implementálása után néhány fagráfcsalád implementálásátt¶ztem ki célul. Az el®z® dolgozatomban a caterpillar gráf általános címkézését
mutattam be, amivel különböz® méret¶ caterpillar gráfokat lehetett létrehozni.
Ebben a részben az egyik legegyszer¶bb fagráfot, a csillag gráfot szeretném els®nek bemutatni. A csillag gráfok után egy kis változtatással eljuthatunk a pók
gráfok egyik fajtájához, végül pedig egy speciális, több komponensb®l álló gráfot
szeretnék bemutatni.

5.1. Csillag gráfok
5.1.1. Deníció. Egy fa gráfot csillag gráfnak nevezünk, ha n + 1 darab csúcsa

van, és az n + 1 darab csúcsból, pontosan n darab levél csúcs.

Megjegyzés. A csillag gráf megegyezik a K1,n teljes páros gráal.

csillag gráfok is egyszer¶ caterpillar gráfok.

Továbbá, a5.1.1. Tétel. A csillag gráfok graceful gráfok.
Bizonyítás. Legyen a gráf központi csúcsa v , a többi csúcsa rendre v1 , v2 , . . . , vn .

Mivel n darab levele van a gráfnak, és ezek közt semelyik kett® nem szomszédos,viszont mindegyik szomszédos a v csúccsal, így az 1, 2, . . . , n címkék közül a nem
közbüls® csúcsot tetsz®legesen el lehet címkézni. Míg a közbüls® csúcshoz rendeljük hozzá a 0 csúcscímkét. Az így konstruált csúcscímkézés egy f ∗ élcímkézést
indukál, és mivel f ∗ bijektív, így teljesül a graceful tulajdonság. Tehát a csillag
gráfok graceful gráfok.

Az implementálás során a címkéket úgy készítettem el, hogy alternáló sorozatot alkossanak.
1
2
3
4

def Labels(n):L=[]
j=0
for i in range(0,n+1):

63

64
5
6
7
8
9
10
11

1
2
3
4
5

1
2
3

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

if(i%2!=0):
L.insert(i,n)
n=n-1elif(i%2==0):
L.insert(i,j)
j=j+1
return L

def graph(labels,n):G=graphs.StarGraph(n)G.relabel(labels,inplace=True)
return G.graphplot(edge_color='blue',vertex_color='yellow',
vertex_size=200,graph_border=True).show()def Star_graphs(n):labels=Labels(n)graph(labels,n)5.1. ábra. S5 gráf

5.2. ábra. S11 gráf

5.2. Pók gráfok
5.2.1. Deníció. Egy S gráfot pók gráfnak nevezünk, ha fa gráf, és pontosan

egy olyan csúcsa van, amelyiknek fokszáma nagyon, mint kett®. Ha létezik ilyen
csúcs, akkor ezt a csúcsot a gráf elágazási pontjának nevezzük. Továbbá, a pók
gráfban az elágazási pontból induló különböz® hosszúságú útjait nevezzük a pók
gráf lábainak.

5.2.

65

PÓK GRÁFOK

5.2.1. Tétel. Legyen S = (V, E, ϕ) véges pók gráf l darab lábbal, amelyeknek
hossza m, vagy m + 1 lehet, ahol m ≥ 1. Ekkor az S gráf graceful gráf.
Bizonyítás. Tegyük fel, hogy l ≥ 3, mivel l ≤ 2 esetén a pók gráfok egyben út

gráfok is, azokról viszont tudjuk, hogy graceful gráfok.
Az f csúcscímkézést vizsgáljuk meg az alábbi esetekben.

(i.) Tegyük fel, hogy l páratlan.
Ebben az esetben, legyen l = l0 + l1 , ahol l0 jelenti az m hosszú lábaknak aszámát, míg l1 jelenti az m + 1 hosszú lábaknak a számát. Ekkor a csúcsok
száma n = l0 m + l1 + 1. Jelölje v az elágazási csúcsot, míg a gráf többi
csúcsa esetén, jelölje vi,j azt a csúcsot, amelyik az i-edik lában van, és jtávolságra van az elágazási csúcstól.
Deniáljuk az f csúcscímkézést a következ®képpen:f (v) = 1.

Ha i és j mindkett® páratlan számok, akkor
f (vi,j ) = n −i − 1 (j − 1)l−.
2
2

Ha i és j mindkett® páros számok, akkor
f (vi,j ) = n −l−1i(j − 2)l
− −
.
2
2
2

Ha i páros, míg j páratlan szám, akkor
f (vi,j ) =(j − 1)li+.
2
2

Ha i páratlan, míg j páros szám, akkor
f (vi,j ) =l − 1 i + 1 (j − 2)l
+
+
.
2
2
2

Az így meghatározott f csúcscímkézés egy f ∗ élcímkézést indukál, amely
bijektív, így teljesül a graceful tulajdonság, így a gráf graceful gráf.
(ii.) Tegyük fel, hogy l páros.
Továbbá, tegyük fel azt is, hogy ebben az esetben van m hosszú láb. Töröljük
a lábon lév® összes csúcsot, kivéve a központi csúcsot. Így kaptunk egy l − 1
darab, páratlan lábú pók gráfot. Használjuk erre az els® esetben leírt konstrukciót. Jelöljük el ezt a gráfot T0 -val. Továbbá, n0 := |V (T0 )|. Deniáljuk
az f0 függvényt, úgy hogy f0 (u) = n0 − f (u), bármely u ∈ V (T0 ) esetén. Az
így keletkezett gráfot jelöljük T1 -gyel. Adjunk hozzá a T1 gráfhoz egy w1
csúcsot, amely legyen szomszédos a v központi csúccsal. Deniáljuk az f1

66

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

függvényt, úgy hogy f1 (w1 ) = 0, és f1 (u) = f0 (u) + 1, bármely u ∈ V (T0 ) esetén. Továbbá, deniáljuk az f2 függvényt, úgy hogy f2 (u) = n0 +1−f1 (u),bármely u ∈ V (T0 ) esetén, és legyen f2 (w1 ) = n0 + 1.
A következ® lépésben adjunk hozzá a gráfhoz egy w2 csúcsot, amely legyenszomszédos w1 -gyel. Majd alkalmazzuk rá a fent deniált függvényeket
ugyanúgy sorban, mint w1 esetén. Majd folytassuk ezt a konstrukciót wm ig.
Mivel az eredeti csúcscímkézés összes csúcsát folyamatosan ugyanúgy változtattuk, és mindig olyan új csúcscímkét deniáltunk, amely csúcscímke még
nem volt, így minden csúcs csúcscímkéje különböz®. Mivel minden csúcscímke különböz®, és a csúcscímkézés egy f ∗ bijektív élcímkézést indukál,
ezért teljesül a graceful tulajdonság, így a gráf graceful gráf.

A gráf implementálása során gyelembe kell venni bizonyos eseteket is, aminél
a konstruktív bizonyítás problémába kerülhet. A gráf csúcscímkézése során három
paramétert kell megadnunk az l0 -t, az l1 -et és az m-et. Ezek alapján probléma
azokban az esetekben fordulhat el®, amikor valamelyik li érték 0, ahol i ∈ {0, 1}.
Ebben az esetben viszont egy csillag gráf adódna, amelyr®l tudjuk, hogy graceful
gráf.
Továbbá, meg kell említeni, hogy az itt szerepl® bizonyítás el®ször Bahls cikkében[15] jelent meg, viszont kés®bb Elina Robeva ezt felhasználta cikkében [16], ahol
már helytelenül szerepelnek a bizonyításban leírt formulák. Három hibát követettel a cikk szerz®je. Két esetben tévesen adott hozzá az értékekhez 1-et, míg aharmadik hibája az volt, hogy elfelejtett kivonni 2i -t, a bizonyítás i és j is páros
esetében.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def Labels(l_0,l_1,m):l=l_0+l_1
if l_0!=0:
n=l*m+l_1
else:
n=l*(m+1)
L=[]
L.insert(0,0)
szamlalo=1
db=0
if l%2!=0:
for i in range(1,l+1):
if db<l_1:
for j in range(1,m+2):
if i%2!=0 and j%2!=0:
L.insert(szamlalo,n-(i-1)/2-(j-1)/2*l)

5.2.

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

PÓK GRÁFOK

szamlalo=szamlalo+1
elif i%2==0 and j%2==0:
L.insert(szamlalo,n-(l-1)/2-i/2-(j-2)/2*l)szamlalo=szamlalo+1
elif i%2==0 and j%2!=0:
L.insert(szamlalo,i/2+(j-1)*l/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,(l-1)/2+(i+1)/2+(j-2)*l/2)
szamlalo=szamlalo+1
db=db+1
else:
for j in range(1,m+1):
if i%2!=0 and j%2!=0:
L.insert(szamlalo,n-(i-1)/2-(j-1)/2*l)szamlalo=szamlalo+1
elif i%2==0 and j%2==0:
L.insert(szamlalo,n-(l-1)/2-i/2-(j-2)/2*l)szamlalo=szamlalo+1
elif i%2==0 and j%2!=0:
L.insert(szamlalo,i/2+(j-1)*l/2)
szamlalo=szamlalo+1
else:
L.insert(szamlalo,(l-1)/2+(i+1)/2+(j-2)*l/2)
szamlalo=szamlalo+1
db=db+1
else:
F=[]
if l_0!=0:
n_0=n-melse:
n_0=n-m-1
if l_0>0:
L=Labels(l_0-1,l_1,m)else:
L=Labels(l_0,l_1-1,m)db=0
F_0=[]
szamlalo=0
for i in range(0,len(L)):
F.insert(szamlalo,n_0-L[i])szamlalo=szamlalo+1
L.clear()
if l_0!=0:
while(db<=m):szamlalo=0

67

68
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

for i in range(0,len(F)):
F_0.insert(szamlalo,F[i]+1)
szamlalo=szamlalo+1
F_0.insert(szamlalo,0)F.clear()for i in range(0,len(F_0)):
F.insert(szamlalo,n_0-F_0[i]+1)
szamlalo=szamlalo+1
db=db+1
n_0=n_0+1
F_0.clear()L.clear()else:
while(db<=m):szamlalo=0
for i in range(0,len(F)):
F_0.insert(szamlalo,F[i]+1)
szamlalo=szamlalo+1
F_0.insert(szamlalo,0)F.clear()for i in range(0,len(F_0)):
F.insert(szamlalo,n_0-F_0[i]+1)
szamlalo=szamlalo+1
db=db+1
n_0=n_0+1
F_0.clear()L.clear()for i in range(0,len(F)):
L.insert(i,F[i])return L

A pozicionálás úgy történik, hogy el®ször a központi csúcs helyét adjuk meg,
majd mindegyik részlistából kiolvasom az els® elemet. Ezeket egy közös körönábrázolom. Ezt m hosszú lábak esetén meg tudom valósítani. Probléma abban
az esetben léphet fel, amikor elfogynak az m hosszú lábak. Ilyenkor továbbra
is a részlistákról olvasom be az értékeket, viszont ha egy olyan listáról szeretne
beolvasni értéket, amelynek az adott pozíciójában nincs már érték, akkor a (−1)értéket fogom beolvasni. Ebben az esetben a kör ábrázolásakor nem fog megjelenniúj csúcs, viszont a helyére nem fog kerülni másik csúcs, így elkerülöm azt, hogy
más helyre kerüljenek az azonos listából származó csúcsok. Végül már csak azátmér®ket kell azonosan növelni, és így a gráf szépen ábrázolhatóvá válik.
1
2
3

def spider(l_0,l_1,m):labels=Labels(l_0,l_1,m)if (l_0+l_1)%2==0 and l_0!=0:

5.2.

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

PÓK GRÁFOK

del labels[-1]G=Graph()db=0
temp=0G.add_vertex(0)while(db<l_1):
for i in range(1+temp,m+1+temp):
G.add_edges([(i,i+1)])
db=db+1
temp=temp+m+1
temp=0for i in range(1,l_1+1):
G.add_edges([(0,1+temp)])
temp=temp+m+1
db=0
temp=0s=l_1*(m+1)+1
n=l_0*m+l_1*mwhile(db<l_0):
for i in range(s+temp,s+m-1+temp):
G.add_edges([(i,i+1)])
db=db+1
temp=temp+m
temp=0for i in range(1,l_0+1):
G.add_edges([(0,s+temp)])
temp=temp+m
G.relabel(labels,inplace=True)

32
33
34
35

S=[]
for i in range(1,(l_0+l_1)*m+l_1+1):
S.insert(i,i)

36
37
38
39
40
41
42
43
44
45
46
47
48
49

pos_ver=[]for i in range(0,m):
pos_ver.insert(i,[])seged=0
while(seged<m):
temp=m+1
db=0
last_index=0
for i in range(1+seged,len(labels),temp):
pos_ver[seged].insert(i,labels[i])if db==l_1:
last_index=i
break

69

70
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

else:
db=db+1
if l_0!=0:
temp=mdb=0
for i in range(last_index+temp,len(labels),temp):
pos_ver[seged].insert(i,labels[i])if db==l_0:
break
else:
db=db+1
seged=seged+1
else:
seged=seged+1
pos_dict={}
tul=[]
j=0
db=0
for i in range(m+1,len(labels),m+1):
if db<l_1:
tul.insert(j,labels[i])j=j+1
db=db+1
else:
break
for i in range(0,l_0+l_1):
if len(tul)!=l_0+l_1:
tul.insert(len(tul),-5)
else:
break
labels_0=labels.pop(0)temp_0=0
r=2
j=0
while(temp_0<len(pos_ver)):for i in pos_ver[temp_0]:
x = float(r*cos(pi/2 + ((2*pi)/len(pos_ver[temp_0]))*j))y = float(r*sin(pi/2 + ((2*pi)/len(pos_ver[temp_0]))*j))j=j+1
pos_dict[i] = [x,y]temp_0=temp_0+1
r=r+2
j=0
for i in tul:
x = float(r*cos(pi/2 + ((2*pi)/len(tul))*j))y = float(r*sin(pi/2 + ((2*pi)/len(tul))*j))

5.2.

96
97
98
99
100
101
102
103

71

PÓK GRÁFOK

j=j+1
pos_dict[i]=[x,y]pos_dict[labels_0]=[0,0]if tul.count(-5)>0:
del pos_dict[-5]for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300).show(figsize=[10,5])5.4. ábra. S4,4,4 gráf

5.3. ábra. S2,3,4 gráf

5.5. ábra. S0,3,4 gráf

72

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

5.3. Petárda gráfok
5.3.1. Deníció. Legyen F = (V, E, ϕ) véges, egyszer¶ gráf. Az F gráfot petárda
gráfnak nevezzük, ha egy tetsz®leges k hosszú útgráf minden egyes csúcsához, egy
m − 1 méret¶, de különböz® csillag gráfokat illesztünk.

5.3.1. Tétel. Minden petárda gráfnak van graceful címkézése.
Bizonyítás. Legyen F egy petárda gráf. Legyen P (F )k az F gráf részgráfja, amely

speciálisan egy k hosszú útgráf. Továbbá, mindegyik csillag gráf legyen m − 1
csúcsú. Így az F csúcsainak a száma az éppen km lesz.
Az útgráf els® csúcsának legyen a címkéje 1, a második csúcsának legyen a címkéje
1 + (k − 1)m, a harmadik csúcsának legyen a címkéje 1 + m, a negyedik csúcsának
a címkéje legyen 1 + (k − 2)m,és folytassuk ezt a címzést addig ameddig csak lehet
balról jobbra.
Ezután vegyük az els® csillag központi csúcsát és címkézzük el km címkével, amásodik csillag központi csúcsát m címkéve, a harmadik csillag központi csúcsát
(k − 1)m címkével, a negyedik csillag központi csúcsát 2m címkével,. . . . Így
maradt összesen k(m − 2) darab csúcs aminek nincs még címkéje.
Vegyük az i-edik csillag gráfot. Ha i páros, akkor legyen az els® csúcs címkéje
2+im, a második csúcs címkéje 3+im, . . . , az m-edik csúcs címkéje (m−1)+im.
Ha i páratlan, akkor legyen az els® csúcs címkéje 2 + (k − i)m, a második csúcs
címkéje 3 + (k − i)m,. . . , az m-edik csúcs címkéje m − 1 + (k − i)m.
Az így megkonstruált címkézés minden csúcshoz különböz® csúcscímkét rendel,
amely egy élcímkézést indukál, amely bijektív, így teljesül a graceful tulajdonság,
tehát a gráf graceful gráf.
Az implementálás során részlistákat fogok képezni, amibe címkék kerülnek.
Három részlistát használok, amelyikbe kerülnek az út csúcscímkéi, a központi
csillag csúcscímkéi, illetve a csillag csúcscímkéi, leszámítva a központi csúcsot, ésaz úton fekv® csúcsot.
1
2
3
4
5
6
7
8
9
10
11
12

import copy
def Labels(m,k):
L=[]
pos=0
temp=0
temp_0=1
for i in range(0,k):
if i%2==0:
L.insert(pos,1+temp)
pos=pos+1
temp=temp+m
else:

5.3.

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

PETÁRDA GRÁFOK

73

L.insert(pos,1+(k-temp_0)*m)
temp_0=temp_0+1
pos=pos+1
K=[]
pos=0
temp_0=0
temp_1=1
for i in range(0,k):
if i%2==0:
K.insert(pos,(k-temp_0)*m)
temp_0=temp_0+1
pos=pos+1
else:
K.insert(pos,temp_1*m)
temp_1=temp_1+1
pos=pos+1
T=[]
pos=0
length=len(L)temp=0db=1
while(length>0):
for i in range(2+temp,m+temp):
T.insert(pos,i)
pos=pos+1
temp=temp+m
if(len(T)==(m-2)*k):break
for i in range(2+(k-db)*m,m+(k-db)*m):T.insert(pos,i)
pos=pos+1
db=db+1
length=length-1
if(len(T)==(m-2)*k):
break
return L,K,T

A pozicionálás során el®ször az út csúcsait helyezem el, majd a pozíciók alapján
egy körön ábrázolom egyenként a csillagok csúcsait.
1
2
3
4
5
6

def firecracker(n,k):
if n>=2 and k>=2:
L,K,T=Labels(n,k)
labels=[]for i in range(0,len(L)):
labels.insert(i,L[i])

74
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

for i in range(0,len(K)):
labels.insert(i+len(L),K[i])for i in range(0,len(T)):
labels.insert(i+len(L)+len(T),T[i])G=Graph()G.add_vertex(k-1)
for i in range(0,k-1):
G.add_edges([(i,i+1)])
d=0
for i in range(k,2*k):
G.add_vertex(i)G.add_edges([(d,i)])
d=d+1
vmi=k
db=0
for i in range(k,2*k):hossz=n-2
while(hossz>0):G.add_edges([(i,i+k+db)])
hossz=hossz-1
db=db+1
db=db-1
G.relabel(labels,inplace=True)
pos_dict = {}
S=[]
Z=[]
pos=0
temp=0kis=0
for i in range(0,k):S.insert(pos,L[i])pos=pos+1
S.insert(pos,K[i])pos=pos+1
for j in range(0,n-2):
S.insert(pos,T[j+temp])
pos=pos+1
temp=temp+n-2
W = copy.deepcopy(S)Z.insert(kis,W)
kis=kis+1
S.clear()j=0
Z_hossz=len(Z)
R=10
fix=1

5.3.

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

75

PETÁRDA GRÁFOK

for t in range(0,len(Z)):
if t % 2 == 0:
for i in Z[t]:x = 3*float(2*cos(pi/2 + ((2*pi)/(n))*j))+R*fix
y = 3*float(2*sin(pi/2 + ((2*pi)/(n))*j))j=j+1
pos_dict[i] = [x,y]j=0
fix=fix+1
else:
for i in Z[t]:x = 3*float(2*cos(pi/2 + ((2*pi)/(n))*j))+R*fix
y = 3*float(2*sin(pi/2 + ((2*pi)/(n))*j))-12
j=j+1
pos_dict[i] = [x,-y]j=0
fix=fix+1
for u,v,l in G.edges(): G.set_edge_label(u,v,abs(u-v))
G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow',vertex_size=300,
graph_border=True).show(figsize=[5,5])
else:
print("Az n vagy a k értéke túl kicsi.")

5.6. ábra. F10,4 gráf

5.7. ábra. F5,10 gráf

76

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

5.4. Álrács gráfok
5.4.1. Deníció. Legyen G = (V, E, ϕ) véges, egyszer¶ gráf. Legyenek a csúcsai

rendre v1,1 , v1,2 , . . . , v1,n−1 , v1,n , . . . , vm,n−1 , vm,n . Azaz |V (G)| = nm. Továbbá,az i-edik csúcs legyen szomszédos az i + (n + 1)-edik csúccsal, ha i ≡ 0 (mod n).
Ha i ≡ n − 1 (mod n), akkor az i-edik csúcs legyen szomszédos az i + (n − 1)-edik
csúccsal. Ha i ≡ 2 (mod n), vagy i ≡ 3 (mod n),. . . , vagy i ≡ n − 2 (mod n)teljesül, akkor az i-edik csúcs legyen szomszédos az i + (n + 1)-edik, illetve az
i + (n − 1)-edik csúccsal. Az így megkonstruált gráfot álrács gráfnak nevezzük.
Megjegyzés. Ezeket a gráfokat P Gm,n -nel jelöljük.

A P Gm,n gráfok ábrázolhatóak, úgy mint a rácsgráfok, és így úgy néz ki a gráf, mintha összefügg® lenne,
de nem az, két komponensb®l állnak. A tétel, illetve a bizonyítása Meghpara
Meera cikkében [17] olvasható.

5.4.1. Tétel. Az P Gm,n gráfok graceful gráfok, pontosan akkor, ha m, n ≥ 3,ésm, illetve n páratlan számok.
Bizonyítás. Tegyük fel, hogy az SGm,n gráf, egy rácson van ábrázolva.

Legyenvi,j a gráf i-edik sorának, és j -edik oszlopának a csúcsa, ahol 1 ≤ i ≤ m, illetve
1 ≤ j ≤ n. Tegyük fel, hogy m, és n is páratlan számok, illetve m, n ≥ 3.
Deniáljuk az f : V (SGm,n ) → {0, 1, . . . , mn − 1} csúcscímkézést a következ®képpen:
Ha 1 ≤ i ≤ m, és i páratlan, akkor
f (vi,1 ) =illetvef (vi,2 ) = f (vm,n ) +i−1,
2
nm − n i − 1−.
2
2

Ha 1 ≤ i ≤ m, i páratlan, 3 ≤ j ≤ n, és j páratlan, akkor
f (vi,j ) = f (vi,j−2 ) + (m − 1).

Ha 1 ≤ i ≤ m, i páratlan, 4 ≤ j ≤ n − 1, és j páros, akkor
f (vi,j ) = f (vi,j−2 ) − (m − 1).

Ha 2 ≤ i ≤ m − 1, és i páros, akkor
f (vi,2 ) = 2(m − 1)(n − 1) −illetvei−2,2if (vi,n ) = f (v2,n−1 ) + .
2

5.4.

77

ÁLRÁCS GRÁFOK

Ha 2 ≤ i ≤ m − 1, és i páros, 4 ≤ j ≤ n − 1, és j páros, akkor
f (vi,j ) = f (vi,j−2 ) − (m − 1).

Ha 2 ≤ i ≤ m − 1, és i páros, 1 ≤ j ≤ n − 2, és j páratlan, akkor
f (vi,j ) = f (vi,j+2 ) − (m − 1).

Az így deniált f csúcscímkézés egy f ∗ élcímkézést indukál, amely bijektív, ígyteljesül a graceful tulajdonság, tehát a gráf graceful gráf.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def temp_f(m,n):
L_paratlan=[]L=[]
temp=0szamlalo=0
szamlalo_2=0
mid=[]
q=2*(m-1)*(n-1)
for i in range(1,m+1):
if i%2!=0:
for j in range(1,n+1):
if j%2!=0:
if j==1:
L_paratlan.insert(szamlalo,(i-1)/2)
szamlalo=szamlalo+1
else:
L_paratlan.insert(szamlalo,L_paratlan[szamlalo-1]++(m-1))
szamlalo=szamlalo+1
else:
for j in range(2,n+1):
if j==2:
mid.insert(szamlalo_2,q-(i-2)/2)
szamlalo_2=szamlalo_2+1
L_2=[]
for i in range(1,m+1):
if i%2!=0:
for j in range(1,n+1):
if j==2:
L_2.insert(szamlalo,L_paratlan[len(L_paratlan)-1]+n*(m-1)/2-(i-1)/2)
szamlalo=szamlalo+1
szamlalo=0
kor=0
for i in range(1,m+1):

78
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

if i%2!=0:
for j in range(4,n+1):
if j%2==0:
if j==4:
L.insert(szamlalo,L_2[kor]-m+1)
szamlalo=szamlalo+1
kor=kor+1
else:
L.insert(szamlalo,L[szamlalo-1]-m+1)
szamlalo=szamlalo+1
szamlalo=0
tomb=[]
temp_0=0
for i in range(2,m,2):
for j in range(4,n,2):
if j==4:
tomb.insert(szamlalo,mid[temp_0]-(m-1))
szamlalo=szamlalo+1
temp_0=temp_0+1
else:
tomb.insert(szamlalo,tomb[len(tomb)-1]-(m-1))
szamlalo=szamlalo+1
utolso_oszlop=[]szamlalo=0
if n==5:
for i in range(2,m,2):
utolso_oszlop.insert(szamlalo,tomb[0]+i/2)
szamlalo=szamlalo+1
elif n==3:
for i in range(2,m,2):
if szamlalo==0:
utolso_oszlop.insert(szamlalo,mid[0]+i/2)
szamlalo=szamlalo+1
else:
utolso_oszlop.insert(szamlalo,mid[0]+i/2)
szamlalo=szamlalo+1
else:
for i in range(2,m,2):
utolso_oszlop.insert(szamlalo,tomb[1]+i/2)
szamlalo=szamlalo+1
tomb_2=[]szamlalo=0
temp_0=0
if n==3:
for i in range(2,m,2):
for j in range(n-2,0,-2):

5.4.

82
83
84
85
86
87
88
89
90
91
92
93
94
95

ÁLRÁCS GRÁFOK

79

tomb_2.insert(szamlalo,utolso_oszlop[temp_0]-(m-1))
szamlalo=szamlalo+1
temp_0=temp_0+1
else:
for i in range(2,m,2):
for j in range(n-2,0,-2):
if j==n-2 :tomb_2.insert(szamlalo,utolso_oszlop[temp_0]-(m-1))
szamlalo=szamlalo+1
temp_0=temp_0+1
else:
tomb_2.insert(szamlalo,tomb_2[len(tomb_2)-1]-(m-1))
szamlalo=szamlalo+1
return L_paratlan, L_2,L,mid,tomb,utolso_oszlop,tomb_2

A könnyebb ábrázolás miatt a részlistákat rendezni kell, és a listákba most már
soronként kerülnek majd az értékek. Ezen élekkel az ábrázolás már sokkal könynyebben történik, hiszen a sorokat már egyszer¶en csak soronként kell feltölteni.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def Labels(m,n):
csucsok=[[]]
S,MID,L,mid,tomb,utolso_oszlop,tomb_2=temp_f(m,n)
for i in range(0,(m+1)/2-1):
csucsok.insert(i,[])szamlalo=0
kor=0
temp=0while(kor!=len(csucsok)):for i in range(0+temp,(n+1)/2+temp):
csucsok[kor].insert(i,S[i])szamlalo=szamlalo+1
kor=kor+1
temp=temp+(n+1)/2
for i in range(0,len(csucsok)):
csucsok[i].insert(1,MID[i])k_t=(n-3)/2
l_t=(m+1)/2
l=l_t
szamlalo=0
temp_1=0
while(l>0):
temp_0=3
k=k_twhile(k>0):

80
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

csucsok[szamlalo].insert(temp_0,L[temp_1])
temp_0=temp_0+2
temp_1=temp_1+1
k=k-1
szamlalo=szamlalo+1
l=l-1
ismetlodes_hossza=(n-3)/2+1
ismetlodes_szama=(m+1)/2-1
temp=[]
szamlalo=0
kor=0
temp_1=0
while(kor!=ismetlodes_szama):szamlalo=0
for i in range(0+temp_1,len(tomb_2)):
if szamlalo!=ismetlodes_hossza:
temp.insert(0+temp_1,tomb_2[i])szamlalo=szamlalo+1
kor=kor+1
temp_1=temp_1+ismetlodes_hossza
csucsok_2=[]
for i in range(0,len(mid)):
csucsok_2.insert(i,[])szamlalo=0
lep=0
szamlalo=1
szamlalo_2=0
for j in range(0,len(mid)):
if j==0:
csucsok_2[j].insert(0, temp[0])else:
csucsok_2[j].insert(0,temp[szamlalo])szamlalo=szamlalo+1
csucsok_2[j].insert(1, mid[lep])
for i in range(2,n-1):
if i%2==0:
csucsok_2[j].insert(i,temp[szamlalo])szamlalo=szamlalo+1
else:
csucsok_2[j].insert(i,tomb[szamlalo_2])
szamlalo_2=szamlalo_2+1
csucsok_2[j].insert(6,utolso_oszlop[lep])
lep=lep+1
osszes_csucs=[]szamlalo=0
szamlalo_1=0

5.4.

72
73
74
75
76
77
78
79

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

ÁLRÁCS GRÁFOK

for i in range(0,len(csucsok)+len(csucsok_2)):
if i%2==0:
osszes_csucs.insert(i,csucsok[szamlalo])szamlalo=szamlalo+1
else:
osszes_csucs.insert(i,csucsok_2[szamlalo_1])
szamlalo_1=szamlalo_1+1
return osszes_csucs

def pseudogrid(m,n):if (m>2 and n>2) and (m%2!=0 and n%2!=0):
csucsok=Labels(m,n)
labels=[]szamlalo=0
for i in range(0,len(csucsok)):
for j in range(0,len(csucsok[i])):labels.insert(szamlalo,csucsok[i][j])szamlalo=szamlalo+1
G=Graph()for i in range(0,n*m):
G.add_vertex(i)for i in range(0,(m-1)*n):
if i%n==0:
G.add_edges([(i,i+(n+1))])elif i%n==n-1:
G.add_edges([(i,i+(n-1))])else:
G.add_edges([(i,i+(n-1))])
G.add_edges([(i,i+(n+1))])
G.relabel(labels,inplace=True)
pos_dict={}
x=0;y=0
for i in csucsok:
x=0
y=y+100
for j in i:x=x+100y
pos_dict[j]=[x,y]G.graphplot(pos=pos_dict,edge_color='blue',vertex_color='yellow').show(figsize=[5,5])
else:
print("Az n,m>2 vagy m,n páratlan paritása nem teljesül.")

81

82

FEJEZET 5.

SPECIÁLIS GRACEFUL FAGRÁFOK, ÉS ÁLRÁCS GRÁFOK
IMPLEMENTÁLÁSA

5.8. ábra. P G5,7 gráf

Irodalomjegyzék[1]

A. Rosa, On certain valuations of the vertices of a graph, Journal of Graph Theory- JGT, 01 1967.
[2]

S. W. Golomb, How to number a graph, in Graph Theory and Computing, pp. 23
 37, Academic Press, 1972.

[3]

E. Gnang, On graceful and harmonious labelings of trees. 11 2018.

[4]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version9.0), 2020. https://www.sagemath.org.
[5]

Wikipedia contributors, Hadamard matrix  Wikipedia, the free encyclopedia,
2020.

[6]

S. Vaidya and N. Shah, Graceful and odd graceful labeling of some graphs, Inter-national Journal of Mathematics and Soft Computing, vol. 3, p. 61, 01 2013.
[7]

S. Vaidya and L. Bijukumar, Some new graceful graphs, Advances and Applications

in Discrete Mathematics, vol. 6, 01 2010.
[8]

R. L. Watson, A survey on the graceful labeling of graphs, Master's thesis, University of Colorado at Denver, 2000.

[9]

S. Guruswamy and S. Kuppusamy, Subdivision of wheel is graceful and cordial,International Journal of Mathematical Analysis, vol. 9, pp. 817822, 01 2015.
[10] V. Srinivasan and N.Amirthavahini, New results on some vertex labeling of graphs,International Journal of Pure and Applied Mathematics, vol. 118, pp. 891898, 02
2018.
[11] A. Elumalai and S. Guruswamy, Gracefulness of a cycle with parallel chords andparallel p k -chords of dierent lengths, Ars Combinatoria, vol. 104, 04 2012.
[12] A. Solairaju, S. Subbulakshmi, and R. Kokila, Graceful labelings for sun graph, sun
extension graph, double fan, and leg graph with star, vol. 13, pp. 13571364, 2017.
[13] A. Elumalai and A. Ephremnath, Gracefulness of a cycle with zigzag chords, In-

ternational Journal of Pure and Applied Mathematics, vol. 101, pp. 629635, 01
2015.
[14] K. M. Koh and K. Y. Yap, Graceful numberings of cycles with a p-chord,

Inst.Math. Acad. Sinica, vol. 12, pp. 4148, 1985.

83

Bull.

84

IRODALOMJEGYZÉK[15] P. Bahls, S. Lake, and A. Wertheim, Gracefulness of families of spiders,Involve,vol. 3, 10 2010.
[16] E. Robeva, An extensive survey of graceful trees, 07 2011. Undergraduate Honours
thesis.
[17] M. Meghpara, Graceful labeling for grid related graphs, International Journal of

Mathematics and Soft Computing, vol. 5, pp. 111117, 04 2015.
[18] J. Gallian, A dynamic survey of graph labeling, Electron J Combin DS6, vol. 19,
11 2000.
[19] C. M. Cavalier, Graceful labelings, Master's thesis, University of South Carolina,
2009.
[20] J. Maowa, Study on graceful labeling of trees, Master's thesis, Bangladesh University of Engineering and Technology (BUET), 07 2016.
[21] R. M. Zhou, Graceful labeling of graphs, Master's thesis, UFRJ/COPPE, Rio deJaneiro, 12 2016.
[22] A. Graf, Graceful labelings of pendant graphs, Rose-Hulman Undergraduate Math-ematics Journal, vol. Vol. 15, 2014.
[23] V. Kaneria and H. Makadia,
p. 173178, 2014.

Graceful labeling for cycle of graphs,

vol. 6,