I-Algebra Yakho Konke

Ithebula Lezixhumanisi

Abstract kanye 1 Isingeniso

2 Izincazelo Eziyisisekelo kanye Nezaziso

2.1 Amasethi

2.2 Ukulandelana

2.3 AmaSiginesha nama-Algebra kanye 2.4 Izigaba

3 Ama-Monographs kanye nama-morphisms awo

4 Imikhawulo kanye Nemikhawulo

5 Ukudweba Ama-Monograph

Izakhiwo zeGrafu ezi-6 kanye nama-Monographs Athayishiwe

7 Ama-submonographs kanye ne-Partial Morphisms

8 Ukuguqulwa kwe-Algebraic ye-Monographs

9 Ama-Monograph Afakwe Ngomshini

10 Isiphetho Nezikhombo

Abstract

Ama-monographs ayizakhiwo ezifana negrafu ezinemiphetho eqondisiwe yobude obungenamkhawulo ezincikene ngokukhululekile. Amanodi ajwayelekile amelwe njengemiphetho yobude obuyiziro. Angadwetshwa ngendlela ehambisana namagrafu ajwayelekile nezinye eziningi, njenge-E-graphs noma 8-graphs. Isigaba sama-monographs sabelana ngezici eziningi nezigaba zezakhiwo zegrafu (ama-algebra amasiginesha ahlungwe kaningi e-monadic), ngaphandle kokuthi ayikho i-terminal monograph. Itholakala endaweni yonke ngomqondo wokuthi izigaba zayo zocezu (noma izigaba zama-monographs athayiphiwe) zilingana nezigaba zezakhiwo zegrafu. Ngakho-ke thayipha ama-monographs avela njengendlela engokwemvelo yokucacisa izakhiwo zegrafu. Ukuhlaziywa okuningiliziwe kokuguqulwa okuphushayo okukodwa nokukabili kwe-monographs kunikezwa, kanye nombono wama-monographs athayiphiwe ahlanganisa ama-E-graph afakwe ngomshini uyahlaziywa kanye nezinguquko zokulondoloza isibaluli.

Amagama angukhiye : Ukuguqulwa Kwegrafu ye-Algebraic, Izakhiwo Zegrafu, Amagrafu Athayiphiwe

1 Isingeniso

Imibono eminingi eyahlukene yamagrafu isetshenziswa kwizibalo nesayensi yekhompiyutha: amagrafu alula, amagrafu aqondisiwe, ama-multigraphs, ama-hypergraphs, njll. Omunye umbono oyintandokazi kumongo wokucabanga nokubhala kabusha yilowo owaziwa nangokuthi ama-quivers, okungukuthi, izakhiwo zefomu pN, E, s, tq lapho u-N, E engamasethi futhi s (umthombo) ukhomba (umthombo) amathiphu kuwo wonke umkhawulo (noma umcibisholo). Isizathu esisodwa salokhu ukuthi isigaba sama-quivers si-isomorphic esigabeni sama-algebra sesiginesha ehlungwe kaningi enezinhlobo ezimbili zamanodi namaphethelo namagama o-opharetha amabili src kanye ne-tgt yohlobo lwama-edges Ñ. Ngokuhambisana naleli siko, ngegrafu sisho ukugoba kulo lonke leli phepha.

Ukuze umele kahle izakhiwo zedatha eziyinkimbinkimbi ngokuvamile kudingekile ukucebisa ukwakheka kwamagrafu ngezibaluli: ama-node noma imiphetho ingase ifakwe ilebula ngezinto ezivela kusethi engaguquki, noma ngamavelu athathwe kwenye i-algebra, noma ngamasethi amanani njengaku-[1], njll. Isibonelo esithakazelisayo singatholakala kokuthi [2] nombono wama-E-des tributes, njengoba ama-e-grafu ebhekwa njengama-e-tributes.

Ngokunembayo, i-E-graph i-algebra isiginesha yayo ingamelwa igrafu elandelayo:

Amagama anikezwe izinhlobo nama-opharetha asiza ukuqonda ukwakheka kwama-E-graphs: amaphethelo ahlobanisa ama-node phakathi kwawo, ama-nv-edges ahlobanisa ama-node namanani, futhi ama-ev-edges ahlobanisa imiphetho namanani. Ngakho-ke amanani okuhlunga aphethe izibaluli ezingamanodi. Kodwa-ke siyabona ukuthi kuma-E-graphs ama-ev-edges asondelene nemiphetho. Lokhu akuyona indinganiso, kodwa sisengase sizamukele izakhiwo ezifana nohlobo oluthile lwegrafu, uma nje siqonda ukuthi zingadwetshwa kanjani.

Ngakho-ke indlela yokwenza umqondo wamagrafu ube jikelele ibonakala ibandakanya ukwenziwa okuvamile kwesiginesha yamagrafu athathwa njengama-algebra. Le ndlela ilandelwe nguMichael L¨owe kokuthi [3], lapho ukwakheka kwegrafu kuchazwa njengesiginesha ye-monadic ehlungwe kaningi. Ngempela ezibonelweni ezingenhla, nasezibonelweni eziningi ezihlinzekwe kokuthi [3], bonke opharetha bane-arity 1 ngakho-ke bangabhekwa njengamaphethelo ukusuka kusizinda sabo kuya kuhlobo lwabo lobubanzi. Ingabe yisona sizathu lesi esibangela ukuthi zibizwe ngokuthi izakhiwo zamagrafu? Kodwa isibonelo esingenhla sibonisa ukuthi ama-E-graphs ahluke kakhulu kugrafu emele isiginesha yawo. Ngaphandle kwalokho, akulula ukuthi ukuqonda kwethu lezi zakhiwo kusekelwe ku-syntax, okungukuthi, emagameni athile anikezwe izinhlobo nama-opharetha kusiginesha.

Ngaphezu kwalokho, kunzima ukubona ukuthi ama-algebra amanye amasignesha alula kakhulu angahunyushwa kanjani njengamagrafu anoma yiluphi uhlobo. Thatha isibonelo isiginesha yamagrafu bese uhlehlisa umsebenzi oqondiwe uye ku-tgt : ama-nodes Ñ emaphethelweni. Bese kuba khona ukulinganisa phakathi kwamanodi ohlobo namachopho, okusho ukuthi ku-algebra yale ndawo yesiginesha nemiphetho kungaba izinto zemvelo efanayo. Ingabe lokhu kuseyigrafu? Singasidweba? Okubi nakakhulu, uma lezi zinhlobo ezimbili zigoqeke zaba yinto eyodwa, ingabe kusho ukuthi indawo/unqenqema lungaba eduze nalo?

Singase sibhekane nalezi zinkinga ngokukhawulela izakhiwo zegrafu esigabeni esithile samasiginesha ama-monadic ama-algebra awo aqinisekiswa ukuthi azoziphatha ngendlela eyi-orthodox, ukusho ngokubonisa imiphetho namanodi ahlukaniswe ngokucacile. Kodwa lokhu kungase kuthambekele ekubeni nobugovu, futhi kusazokwethula enye inselele: ukuthi umbono wesakhiwo segrafu awuvezi kalula isigaba. Ngempela, kunzima ukuchaza ama-morphisms phakathi kwama-algebra amasiginesha ahlukene, uma kuphela ngenxa yokuthi angaba nanoma iyiphi inombolo yamasethi enkampani yenethiwekhi.

Indlela eyamukelwe lapha iwukwenqaba noma yimuphi umehluko wesakhiwo phakathi kwamanodi nemiphetho, ngakho-ke ukwamukela umbono ohlangene wamanodi njengamaphethelo obude obungu-0, namaphethelo ajwayelekile njengamaphethelo obude obu-2 njengoba ancikene nama-node amabili. Lokhu kubuka okuhlanganisiwe kuvumela ngokunengqondo ukuthi imiphetho isondele kunoma iyiphi imiphetho futhi ingagcini nje ngamanodi, ngaleyo ndlela yenze kabanzi imiphetho yama-E-graphs, ngisho nemiphetho encikene nayo. Okokugcina, asikho isizathu sokukhawulela ubude bamaphethelo ku-0 noma ku-2, futhi sizothola izizathu ezinhle (eSigabeni sesi-6) zokuvumela imiphetho yobude obungenamkhawulo, ubude be-ordinal. Imibono edingekayo kanye namanothi ethulwa eSigabeni sesi-2. Ukwakheka kwe-monograph (kanye ne-morphisms) kuchazwe eSigabeni sesi-3, esiveza izigaba eziningi zamamonographs ngokwezinye izici zawo. Izici zalezi zigaba ezihambisana nokuba khona kwemikhawulo kanye nemikhawulo ehlangene zihlaziywa eSigabeni sesi-4.

Sibe sesibona eSigabeni sesi-5 ukuthi i-monographs ingamelwa kanjani ngokunembile ngemidwebo, inqobo nje uma inemiphetho eminingi futhi inobude obunomkhawulo. Ikakhulukazi, imidwebo enjalo ihambisana nendlela evamile yokudweba igrafu yalawo ma-monographs angabonakala ngamagrafu ajwayelekile, futhi ngokufanayo nama-E-graphs.

Isigaba sesi-6 sizinikele ekuqhathaniseni phakathi kwama-monographs nezakhiwo zegrafu, kanye nama-algebra ahambisanayo (esingawabiza ngokuthi ama-algebra ahleliwe egrafu). Sibonisa isakhiwo sendawo yonke yama-monographs, ngomqondo wokuthi wonke ama-algebra ahlelekile egrafu angamelwa (yize ngokuvamile engekho ngendlela ye-canonical) njengama-monographs athayiphiwe, okungukuthi, njengama-monographs.

Umqondo wokwakheka kwegrafu wethulwe kokuthi [3] ukuze kutholwe izigaba ze-homomorphisms eyingxenye lapho amasu okubhala kabusha igrafu ye-algebraic angenziwa khona. Ukuxhumana nama-monographs asungulwe eSigabeni sesi-6 kubiza ukuthuthukiswa okufanayo kwengxenye ye-monographs eSigabeni 7. Izindlela zokuphusha okukodwa kanye nezikabili zokubhala kabusha ama-monograph zingabe sezichazwa, zihlaziywe futhi ziqhathaniswe eSigabeni sesi-8.

Umbono we-E-graph yethulwe kokuthi [2] ukuze kutholwe izigaba eziziphatha kahle (wrt igrafu ebhalwe kabusha) yamagrafu achasisiwe, futhi ngenxa yalokho kuphakanyiswe izethulo ezifanele zezakhiwo zedatha yempilo yangempela. Lokhu kufinyelelwa ngokucebisa ama-E-graphs ngohlobo lwedatha ye-algebra, nangokuhlonza ama-node enani lokuhlunga ngezinto zale algebra. Silandela indlela efanayo eSigabeni 9 ngombono we-monograph ethayiphiwe esibaluliwe ngokuhlonza izici ze-algebra ezinomphetho, futhi sithole izigaba zokuziphatha kahle okufanayo. Ngenxa yokuhlukahluka kwama-monographs sibona ukuthi noma iyiphi i-Σ-algebra ingamelwa njenge-monograph ethayiphiwe.

Siphetha ngeSigaba 10. Qaphela ukuthi izingxenye zeSigaba 4 kuya ku-6 zishicilelwe ku- [4].