IAlgebra yayo yonke into

Itheyibhile yoQhagamshelwano

Isishwankathelo kunye ne-1 Intshayelelo

2 Iingcaciso eziSisiseko kunye neeNqaku

2.1 Iiseti

2.2 Ulandelelwano

2.3 IiSiginitsha neeAlgebra kunye 2.4 Iindidi

3 Iimonographs kunye neeMorphism zazo

4 Imida kunye neMida

5 Ukuzoba iiMonographs

6 iZakhiwo zeGrafu kunye neeMonographs ezichwetheziweyo

7 IiSubmonographs kunye ne-Paial Morphisms

8 Ukuguqulwa kweAlgebraic yeMonographs

9 Kunxulunyaniswa IiMonographs ezichwetheziweyo

10 Isiphelo kunye neeNgcaciso

Abstract

Iimonographs zizakhiwo ezifana neegrafu ezinemiphetho eqondisiweyo yobude obungenasiphelo ngokukhululekileyo ngokukhululekileyo omnye komnye. Amanqaku asemgangathweni amelwe njengeencam zobude obunguziro. Zinokuzotywa ngendlela ehambelana neegrafu eziqhelekileyo kunye nezinye ezininzi, njenge-E-graphs okanye i-8-graphs. Udidi lwemonographs lwabelana ngeepropati ezininzi kunye neendidi zezakhiwo zegrafu (iialjibra zotyikityo lwe-monadic oluhlelwe ngeendlela ezininzi), ngaphandle kokuba akukho siphelo monograph. Ikho jikelele ngengqiqo yokuba iindidi zezilayi (okanye iindidi zemonograph echwetheziweyo) zilingana neendidi zezakhiwo zegrafu. Uhlobo lwemonographs ngoko luvela njengendlela yendalo yokuchaza izakhiwo zegrafu. Uhlalutyo oluneenkcukacha lotshintsho olutyhalwayo olunye noluphindwe kabini lwemonographs lunikiwe, kwaye imbono yemonographs ethayiphwe ngokubanzi echwetheziweyo ebizwa ngokuba yi-E-graphs iyahlalutywa ngokuhambelana neempawu zogcino-mpawu.

Amagama angundoqo : I-Algebraic Graph Transformation, i-Graph Structures, iiGrafu ezichwetheziweyo

1. Intshayelelo

Iingcamango ezininzi ezahlukeneyo zeegrafu zisetyenziswa kwimathematika nakwisayensi yekhompyutha: iigrafu ezilula, iigrafu ezithe ngqo, ii-multigraphs, iihypergraphs, njl. njl. Enye ingcamango ethandwayo kumxholo wengqiqo nokubhala ngokutsha yeyokwaziwa ngokuba yi-Quivers, okt, izakhiwo zefom pN, E, s, tq apho N, E ziseti kwaye zichonge imisebenzi ukusuka (i-nodes) kunye nokuchonga (i-nodes) kuwo wonke udini (okanye utolo). Esinye isizathu soku kukuba udidi lwe-quivers luyi-isomorphic kudidi lwe-algebra yotyikityo oluhlelwe ngeendlela ezininzi ezineentlobo ezimbini zeenodi nemiphetho kunye namagama amabini omsebenzisi src kunye ne-tgt yohlobo lwemiphetho Ñ nodi. Ngokuhambelana nesi sithethe, ngegrafu sithetha umphongolo kulo lonke eli phepha.

Ukuze kube lula ukumela ulwakhiwo lwedatha ebanzi kudla ngokuba yimfuneko ukutyebisa ubume beegrafu ezineempawu: iindawo zokuhlala okanye imiphetho inokuthi ibhalwe ngezinto ezivela kwiseti esisigxina, okanye ngamaxabiso athathwe kwialgebra ethile, okanye ngeeseti zamaxabiso njengaku [1], njl.

Ngokuchanekileyo, i-E-graph yialgebra egama layo linokumelwa yigrafu elandelayo:

Amagama anikwe kwiintlobo kunye nabaqhubi banceda ukuqonda isakhiwo se-E-graphs: imiphetho idibanisa ii-nodes phakathi kwabo, i-nv-edges idibanisa ii-nodes kumaxabiso, kwaye i-ev-edges idibanisa imida kumaxabiso. Yiyo loo nto amaxabiso ohlobo agcina iimpawu ezikwangamaqhuqhuva. Kodwa ke siyabona ukuba kwii-E-graphs i-ev-edges ikufuphi nemiphetho. Oku akungomgangatho, kodwa sisenokwamkela izakhiwo ezinje ngohlobo oluthile lwegrafu, ukuba nje siyayiqonda indlela ezinokuzotywa ngayo.

Yiyo loo nto indlela yokwenza ngokubanzi imbono yeegrafu ibonakala ibandakanya ukwenziwa ngokubanzi kotyikityo lweegrafu ezithathwa njengeealgebra. Le ndlela ilandelwe nguMichael L¨owe kwi- [3], apho ulwakhiwo lwegrafu luchazwa njengotyikityo lwe-monadic oluhlelwe ngeendlela ezininzi. Ngokwenene kule mizekelo ingasentla, nakwimizekelo emininzi enikwe kwi- [3], bonke abaqhubi bane-arity 1 kwaye ke ngoko banokuqwalaselwa njengemida ukusuka kwindawo yabo ukuya kuluhlu lwabo loluhlu. Ingaba sisizathu esibangela ukuba zibizwe ngokuba zizakhiwo zegrafu? Kodwa umzekelo ongasentla ubonisa ukuba ii-E-graphs zahluke kakhulu kwigrafu emele utyikityo lwazo. Ngaphandle koko, akufanelekanga ukuba ukuqonda kwethu kwezakhiwo ezinjalo kusekwe kwi-syntax, okt, kumagama athile anikwe iintlobo kunye nabasebenzisi kutyikityo.

Ngaphaya koko, kunzima ukubona ukuba ii-algebra zezinye iisignisha ezilula kakhulu ze-monadic zinokutolikwa njani njengegrafu zalo naluphi na uhlobo. Thatha umzekelo utyikityo lwegrafu kwaye ubuyise umva umsebenzi ekujoliswe kuwo kwi tgt : iindawo Ñ edge. Emva koko kukho i-symmetry phakathi kweentlobo ze-nodes kunye ne-edges, oku kuthetha ukuba kwi-algebra yolu tyikityo lweendawo kunye nemiphetho iya kuba zizinto zendalo efanayo. Ngaba le iseyigrafu? Ngaba singayizoba? Okona kubi nangakumbi, ukuba ezi ntlobo zimbini ziwile zaba yinto enye, ngaba oko kuthetha ukuba i-node/i-edge inokuba secaleni kwayo?

Sinokuzilungisa ezi ngxaki ngokumisela umda kwizakhiwo zegrafu kudidi oluthile lwemisayino yee-monadic ezinealjibra eziqinisekisiweyo ukuba ziziphatha ngendlela eyiyo, ukutsho ngokubonisa imiphetho ecacileyo kunye neenodi. Kodwa oku kunokutyekela kulawulo olungenamkhethe, kwaye kusenokubonisa enye intsilelo: ukuba ingcamango yolwakhiwo lwegrafu ayiluniki lula udidi. Enyanisweni, kunzima ukuchaza i-morphisms phakathi kwe-algebra yeesignesha ezahlukeneyo, ukuba kuphela ngenxa yokuba banokuba nalo naliphi na inani leesethi zokuthwala.

Indlela eyamkelweyo apha inokuthi igatye naluphi na ulwahlulo phakathi kweendawo zokuhlala kunye neengqameko, kungoko kuthathwe imbono edibeneyo yeendawo zokuhlala njengemida yobude obungu-0, kunye nemiphetho eqhelekileyo njengemiphetho yobude besi-2 ekubeni ikufuphi neendawo ezimbini. Le mbono idityanisiweyo ivumela imiphetho ukuba imelene nayo nayiphi na incam kwaye ingabi macala kuphela, ngaloo ndlela ijikelezisa imiphetho yee-E-graphs, kunye nakwincam emelene nayo. Ekugqibeleni, akukho sizathu sokukhawulela ubude bemiphetho ukuya ku-0 okanye kwi-2, kwaye siya kufumana izizathu ezifanelekileyo (kwiCandelo lesi-6) zokuvumela imiphetho engapheliyo, ubude be-ordinal. Iingcamango eziyimfuneko kunye nobhalo lwaziswa kwiCandelo lesi-2. Ulwakhiwo lwemonograph (kunye nemonografi) luchazwe kwiCandelo lesi-3, luvelisa udidi lweendidi zemonografi ngokwezinye iimpawu zazo. Iipropati zezi ndidi ngokunxulumene nobukho bemida kunye nemida ehlangeneyo zicazululwa kwiCandelo lesi-4.

Emva koko sibona kwiCandelo lesi-5 ukuba i-monographs inokubonakaliswa ngokuchanekileyo yimizobo, ngaphandle kokuba ngokuqinisekileyo inemiphetho emininzi kwaye inobude obulinganiselweyo. Ngokukodwa, imizobo enjalo ihambelana nendlela esemgangathweni yokudweba igrafu yaloo ma-monographs anokuthi achongwe ngeegrafu eziqhelekileyo, kwaye ngokufanayo kwii-E-graphs.

Icandelo lesi-6 linikezelwe kuthelekiso phakathi kwemonographs kunye nezakhiwo zegrafu, kunye nealgebra ehambelanayo (enokuthi siyibize igrafu ehleliweyo yealgebra). Sibonisa ubunjani bemonographs jikelele, ngengqiqo yokuba zonke iialgebra ezicwangcisiweyo zegrafu zinokumelwa (nangona iqhele ukubakho ngendlela yecanonical) njengemonographs echwetheziweyo, okt, njengemofim yemonographs.

Ingcinga yolwakhiwo lwegrafu iye yaziswa kwi- [3] ukuze kufunyanwe iindidi zee-homomorphisms ezingaphelelanga apho ubuchule bokubhala ngokutsha igrafu yealjebra bunokuthi buqhutywe. Imbalelwano nemonographs esekwe kwiCandelo lesi-6 ifuna uphuhliso olufanayo lwemonographs engaphelelanga yemonographs kwiCandelo lesi-7. Indlela yokutyhala enye nephindwe kabini yokubhala ngokutsha iimonografi zinokuchazwa, zihlalutywe kwaye zithelekiswe kwiCandelo lesi-8.

Ingcamango ye-E-graph iye yaziswa kwi- [2] ukuze kufumaneke iindidi zokuziphatha kakuhle (wrt igrafu ebhalwe ngokutsha) yeegrafu ezibandakanyiweyo, kwaye ngoko ke ukuphakamisa ukubonakaliswa okufanelekileyo kwezakhiwo zedatha yenyani. Oku kuphunyezwa ngokutyebisa ii-E-graphs ngohlobo lwedatha ye-algebra, kunye nokuchonga iindawo zexabiso lohlobo oluneziqalelo zale algebra. Silandela indlela efanayo kwiCandelo le-9 ngengcinga yokubalelwa kwemonograph echwetheziweyo ngokuchonga izakhi ze-algebra ezinemiphetho, kwaye sifumane iindidi zokuziphatha kakuhle ngokufanayo. Ngenxa yobulunga bemonographs sibona ukuba nayiphi na i-Σ-algebra inokumelwa njengophawu lwemonograph echwetheziweyo.

Siphetha kwiCandelo le-10. Qaphela ukuba iinxalenye zeCandelo 4 ukuya kwi-6 ziye zapapashwa kwi- [4].