Grafalgebra

Inom matematiken , särskilt inom områdena universell algebra och grafteori , är en grafalgebra ett sätt att ge en riktad graf en algebraisk struktur . Det introducerades av McNulty och Shallon, och har sett många användningsområden inom universell algebra sedan dess.

Definition

$0$ Låt $D = (V, E)$ vara en riktad graf och ett element som inte finns i $V.$ Grafalgebra associerad med $D$ har underliggande mängd $V\cup \{0\}$ och är utrustad med en multiplikation som definieras av reglerna

$xy = x$ om $x,y\in V$ och $(x,y)\in E$ ,
$xy = 0$ om $x,y\in V\cup \{0\}$ och $(x,y)\notin E$ .

Ansökningar

Denna uppfattning har gjort det möjligt att använda metoderna för grafteorin i universell algebra och flera andra riktningar inom diskret matematik och datavetenskap. Grafalgebror har till exempel använts i konstruktioner om dualiteter, ekvationsteorier , planhet , gruppoidringar , topologier , varianter , finita tillståndsautomater , finita tillståndsmaskiner , trädspråk och trädautomater , etc.

Se även

Citat

Anförda verk

Davey, Brian A.; Idziak, Pawel M.; Lampe, William A.; McNulty, George F. (2000). "Dualiserbarhet och grafalgebror" . Diskret matematik . 214 (1): 145–172. doi : 10.1016/S0012-365X(99)00225-3 . ISSN 0012-365X . MR 1743633 .
Delić, Dejan (2001). "Finita baser för platta grafalgebror" . Journal of Algebra . 246 (1): 453–469. doi : 10.1006/jabr.2001.8947 . ISSN 0021-8693 . MR 1872631 .
Kelarev, AV; Miller, M.; Sokratova, OV (2005). "Språk som känns igen av tvåsidiga grafer". Proc. Estlands vetenskapsakademi . 54 (1): 46–54. ISSN 1736-6046 . MR 2126358 .
Kelarev, AV; Sokratova, OV (2001). "Riktade grafer och syntaktiska algebror för trädspråk". J. Automata, Språk och kombinatorik . 6 (3): 305–311. ISSN 1430-189X . MR 1879773 .
Kelarev, AV; Sokratova, OV (2003). "Om kongruenser av automater definierade av riktade grafer" (PDF) . Teoretisk datavetenskap . 301 (1–3): 31–43. doi : 10.1016/S0304-3975(02)00544-3 . ISSN 0304-3975 . MR 1975219 .
Lee, S.-M. (1988). "Grafikalgebror som endast tillåter diskreta topologier". kongr. Nummer . 64 : 147–156. ISSN 1736-6046 . MR 0988675 .
Lee, S.-M. (1991). "Enkla grafalgebror och enkla ringar". Sydostasien Bull. Matematik . 15 (2): 117–121. ISSN 0129-2021 . MR 1145431 .
McNulty, George F.; Shallon, Caroline R. (1983). "Inteboende oändligt baserade finita algebror". I Freese, Ralph S.; Garcia, Octavio C. (red.). Universell algebra och gitterteori (Puebla, 1982) . Föreläsningsanteckningar i matematik. Vol. 1004. Berlin, New York City: Springer-Verlag . s. 206–231 . doi : 10.1007/BFb0063439 . hdl : 10338.dmlcz/102157 . ISBN 978-354012329-3 . MR 0716184 – via Internet Archive .
Oates-Williams, Sheila (1984). "Om variationen som genereras av Murskiĭs algebra". Algebra Universalis . 18 (2): 175–177. doi : 10.1007/BF01198526 . ISSN 0002-5240 . MR 0743465 . S2CID 121598599 .
Poeschel, R. (1989). "Den ekvationella logiken för grafalgebror". Z. Math. Logik Grundlag. Matematik . 35 (3): 273–282. doi : 10.1002/malq.19890350311 . MR 1000970 .

Vidare läsning

Kelarev, AV (2003). Grafalgebror och automater . New York City: Marcel Dekker . ISBN 0-8247-4708-9 . MR 2064147 – via Internet Archive .
Kiss, EW; Poeschel, R.; Pröhle, P. (1990). "Undervarieteter av sorter genererade av grafalgebror". Acta Sci. Matematik . 54 (1–2): 57–75. MR 1073419 .
Raeburn, Iain (2005). Grafalgebror . American Mathematical Society . ISBN 978-082183660-6 .