Ny Algebra ny zava-drehetra

Latabatra Rohy

Abstract sy 1 Fampidirana

2 Famaritana fototra sy fanamarihana

2.1 Sets

2.2 Filaharana

2.3 Sonia sy Algebra ary 2.4 Sokajy

3 Monographs sy ny Morphisms

4 Fetra sy Colimits

5 fanaovana sary monografy

6 Rafitra Graph sy Monographe voatendry

7 Submonographs sy Morphisma ampahany

8 Fiovan'ny algebra amin'ny monografy

9 Monographe voatendry

10 Famaranana sy Fanondroana

Abstract

Ny monografy dia rafitra mitovitovy amin'ny grafika misy sisiny mivantana tsy misy fetra izay mifanakaiky malalaka. Ny nodes mahazatra dia aseho ho toy ny sisin'ny halavany aotra. Izy ireo dia azo atao amin'ny fomba mifanaraka amin'ny grafika mahazatra sy ny maro hafa, toy ny E-graphs na 8-graphs. Ny sokajin'ny monografy dia mizara fananana maro miaraka amin'ireo sokajin'ny rafitry ny grafika (algebras amin'ny sonia maro karazana monadika), afa-tsy ny tsy misy monografy farany. Maneran-tany izy io satria mitovy amin'ny sokajin'ny rafitry ny grafika ny sokajin'ny tapany (na ny sokajin'ny monografy voatendry). Ny karazana monografy dia miseho ho fomba voajanahary hamaritana ny rafitra grafika. Ny famakafakana amin'ny antsipiriany momba ny fiovan'ny tosika tokana sy roa sosona amin'ny monografy dia omena, ary ny hevitra momba ny monografy misy sora-baventy manara-penitra ny sarin'ny E-grafy voatondro dia anadihadiana wrt fiovam-po mitahiry toetra.

Keywords : Fiovan'ny Graph Algebraic, Structures Graph, Graphs Types

1 Fampidirana

Hevitra maro samihafa momba ny grafika no ampiasaina amin'ny matematika sy ny siansa informatika: graphs tsotra, graphs directed, multigraphs, hypergraphs, sns. Ny hevitra iray ankafizina indrindra amin'ny tontolon'ny lojika sy ny fanoratana indray dia fantatra koa amin'ny hoe quivers, izany hoe, rafitra amin'ny endrika pN, E, s, tq izay misy N, E dia napetraka ary avy amin'ny N, E (tsy misy loharanon-kevitra) ary avy amin'ny E (tsy misy loharano) isaky ny sisiny (na zana-tsipìka). Ny antony iray amin'izany dia ny hoe isomorphic ny sokajin'ny quivers amin'ny sokajy algebra amin'ny sonia maromaro misy karazany roa sy sisiny ary anarana operatera roa src sy tgt amin'ny karazana sisiny Ñ nodes. Mifanaraka amin'io fomban-drazana io, amin'ny alalan'ny grafika no tiana holazaina amin'ny hoe quiver manerana an'ity taratasy ity.

Mba ahafahana maneho tsara ny firafitry ny angon-drakitra dia ilaina matetika ny manatsara ny firafitry ny grafika miaraka amin'ny toetra: ny nodes na ny sisiny dia azo asiana marika miaraka amin'ny singa avy amin'ny andiana raikitra, na miaraka amin'ny soatoavina raisina amin'ny algebra sasany, na miaraka amin'ny soatoavina toy ny ao amin'ny [1], sns.

Ny marimarina kokoa, ny E-graph dia algebra izay ny sonia dia azo aseho amin'ny alalan'ity grafika manaraka ity:

Ny anarana nomena ny karazana sy ny mpandraharaha dia manampy amin'ny fahatakarana ny firafitry ny E-graphs: ny sisiny dia mifandray amin'ny nodes eo amin'izy ireo, ny nv-sisiny dia mampifandray ny node amin'ny soatoavina, ary ny ev-edge dia mampifandray ny sisiny amin'ny soatoavina. Noho izany, ny soatoavina karazana dia mitazona toetra izay nodes ihany koa. Saingy hitantsika fa ao amin'ny E-graphs dia mifanakaiky amin'ny sisiny ny ev-edges. Tsy manara-penitra izany, saingy mety mbola hanaiky rafitra toy ny endrika grafika ihany isika, raha toa ka azontsika atao ny manao sary.

Noho izany, ny fomba fanetsiketsehana ny hevitra momba ny graph dia toa ahitana fanetren-tena ny sonian'ny grafika heverina ho algebra. Ity lalana ity dia narahin'i Michael L¨owe ao amin'ny [3], izay mamaritra ny rafitry ny grafika ho toy ny sonia monadika maro karazana. Eny tokoa, ao amin'ireo ohatra etsy ambony, ary amin'ny ohatra maro omena ao amin'ny [3], ny mpandraharaha rehetra dia manana ariity 1 ary noho izany dia azo raisina ho toy ny sisiny avy amin'ny sehatra misy azy mankany amin'ny karazany misy azy. Izany ve no antony iantsoana azy ireo hoe rafitra grafika? Saingy ny ohatra etsy ambony dia mampiseho fa ny E-graphs dia tsy mitovy amin'ny grafika maneho ny soniany. Ankoatra izany, tsy mety raha ny fahatakarantsika ny rafitra toy izany dia tokony hiorina amin'ny syntax, izany hoe, amin'ny anarana manokana nomena ny karazana sy ny mpandraharaha amin'ny sonia.

Fanampin'izany, sarotra ny mahita ny fomba azo adika ho toy ny grafika amin'ny endriny rehetra ny algebra amin'ny sonia monadika tsotra. Raiso, ohatra, ny sonian'ny grafika ary avereno amin'ny tgt : nodes Ñ sisiny. Avy eo dia misy asymmetrika eo amin'ireo karazana nodes sy sisiny, izay midika fa ao amin'ny algebra amin'ity node sy sisiny sonia ity dia ho zavatra mitovy toetra. Mbola grapika ve ity? Afaka manao sary ve isika? Mbola ratsy kokoa aza, raha mirodana ho iray ireo karazany roa ireo, midika ve izany fa ny node/siny iray dia afaka mifanakaiky amin'ny tenany?

Azontsika atao ny mamaha ireo olana ireo amin'ny alàlan'ny famerana ny rafitry ny grafika ho an'ny kilasin'ny sonia monadika izay azo antoka fa mandeha amin'ny fomba ortodoksa ny algebra, hoy ny fampirantiana ny sisiny sy ny node misaraka mazava tsara. Saingy mety ho mora amin'ny arbitrariness izany, ary mbola misy lesoka hafa: ny fiheverana ny firafitry ny grafika dia tsy mora miteraka sokajy. Sarotra tokoa ny mamaritra ny morphisme eo amin'ny algebra misy sonia samihafa, raha toa ka afaka manana andiana mpitatitra maromaro izy ireo.

Ny fomba fanao eto dia ny fandavana ny fanavahana ara-drafitra misy eo amin'ny node sy ny sisiny, noho izany dia raisina ho toy ny sisin'ny halavan'ny 0 ny sisiny, ary ny sisiny mahazatra ho toy ny sisin'ny halavany 2 satria mifanakaiky amin'ny node roa. Io fomba fijery mitambatra io dia ahafahan'ny sisiny mifanakaiky amin'ny sisiny rehetra fa tsy amin'ny node fotsiny, ka mahatonga ny ev-siran'ny E-graphs, ary na dia amin'ny sisiny mifanakaiky amin'izy ireo aza. Farany, tsy misy antony hamerana ny halavan'ny sisiny ho 0 na 2, ary hahita antony tsara isika (ao amin'ny Fizarana 6) hamela ny sisiny tsy manam-petra, halavan'ny ordinal. Ny hevitra sy ny fanamarihana ilaina dia ampidirina ao amin'ny Fizarana 2. Ny firafitry ny monografy (miaraka amin'ny morphisme) dia voafaritra ao amin'ny Fizarana faha-3, izay manome ny bestiary ny sokajin'ny monografy araka ny toetrany sasany. Ny fananan'ireo sokajy ireo amin'ny fisian'ny fetra sy ny fetran'ny fiaraha-miasa dia nodinihina ao amin'ny Fizarana 4.

Hitantsika avy eo ao amin'ny Fizarana faha-5 hoe ahoana no ahafahan'ny monografy aseho amin'ny alalan'ny sary, raha mazava ho azy fa manana sisiny maro be izy ireo ary manana halavany voafetra. Indrindra indrindra, ny sary toy izany dia mifanaraka amin'ny fomba mahazatra amin'ny fanaovana sary ho an'ireo monographs izay azo fantarina amin'ny grafika mahazatra, ary toy izany koa ho an'ny E-graphs.

Ny fizarana faha-6 dia natokana ho an'ny fampitahana ny monografy sy ny rafitry ny grafika, ary ny algebra mifanaraka amin'izany (izay azo antsoina hoe algebra voarafitra graph). Asehontsika ny toetran'ny maha-universel ny monografy, amin'ny heviny hoe ny algebra voarafitra amin'ny grafika rehetra dia azo aseho (na dia tsy amin'ny fomba kanônika aza matetika) ho toy ny monografy soratana, izany hoe, toy ny morphisme amin'ny monografy.

Nampidirina tao amin'ny [3] ny hevitra momba ny firafitry ny grafika mba hahazoana sokajy homomorphisme ampahany izay azo anaovana teknika amin'ny fanoratana ny kisary algebra. Ny fifandraisana amin'ny monografy napetraka ao amin'ny Fizarana 6 dia mitaky fivoarana mitovy amin'ny ampahany amin'ny morphisme amin'ny monografy ao amin'ny Fizarana 7. Ny fomba fanosehana tokana sy roa sosona amin'ny fanoratana monografy dia azo faritana, anadihadiana ary ampitahaina ao amin'ny Fizarana 8.

Ny hevitra momba ny E-graph dia nampidirina tao amin'ny [2] mba hahazoana sokajy tsara fitondran-tena (wrt graph rewriting) amin'ireo grafika voatondro, ary noho izany dia manolotra fanehoana mety amin'ny rafitra angon-drakitra tena izy. Izany dia azo amin'ny alàlan'ny fampitomboana ny E-graphs miaraka amin'ny algebra karazana data, ary amin'ny famantarana ireo node misy sanda miaraka amin'ireo singa amin'ity algebra ity. Manaraka fomba fiasa mitovy amin'izany isika ao amin'ny Fizarana faha-9 miaraka amin'ny fiheverana ny monographie misy sora-baventy amin'ny alàlan'ny famantarana ireo singa amin'ny algebra misy sisiny, ary mahazo sokajy mitovy fitondrantena tsara. Noho ny maha-ankapobeny ny monografy dia hitantsika fa ny Σ-algebra rehetra dia azo aseho ho toy ny monografy misy karazana.

Mamarana ny fizarana faha-10 izahay. Mariho fa ny ampahany amin'ny fizarana faha-4 ka hatramin'ny faha-6 dia navoaka tao amin'ny [4].