Grafová algebra - Graph algebra

v matematika, zejména v oblastech univerzální algebra a teorie grafů, a grafová algebra je způsob, jak dát řízený graf an algebraická struktura. To bylo představeno v (McNulty & Shallon 1983 ), a od té doby zaznamenal mnoho využití v oblasti univerzální algebry.

Definice

Nechat ${displaystyle D = (V, E)}$ být režírovaný graf, a ${displaystyle 0}$ prvek není v ${displaystyle V}$ . Algebra grafu spojená s ${displaystyle D}$ má podkladovou sadu ${displaystyle Vcup {0}}$ , a je vybaven násobením definovaným pravidly

${displaystyle xy = x}$ -li ${displaystyle x, yin V}$ a ${displaystyle (x, y) v E}$ ,
${displaystyle xy = 0}$ -li ${displaystyle x, yin Vcup {0}}$ a ${displaystyle (x, y) otin E}$ .

Aplikace

Tato představa umožnila použít metody teorie grafů v univerzální algebře a několik dalších směrů diskrétní matematiky a informatiky. Grafové algebry byly použity například při konstrukcích týkajících se dualit (Davey a kol. 2000 ), rovnicové teorie (Pöschel 1989 ), plochost (Delić 2001 ), grupoid prsteny (Lee 1991 ), topologie (Lee 1988 ), odrůdy (Oates-Williams 1984 ), konečné automaty (Kelarev, Miller & Sokratova 2005 ), konečné stavové automaty (Kelarev & Sokratova 2003 ), stromové jazyky a stromové automaty (Kelarev & Sokratova 2001 ) atd.

Viz také

Citované práce

Davey, Brian A .; Idziak, Pawel M .; Lampe, William A .; McNulty, George F. (2000), „Dualizability and graph algebras“, Diskrétní matematika, 214 (1): 145–172, doi:10.1016 / S0012-365X (99) 00225-3, ISSN 0012-365X, PAN 1743633
Delić, Dejan (2001), „Konečné základy pro algebry s plochým grafem“, Journal of Algebra, 246 (1): 453–469, doi:10.1006 / jabr.2001.8947, ISSN 0021-8693, PAN 1872631
Kelarev, A.V. (2003), Grafové algebry a automaty, New York: Marcel Dekker, ISBN 0-8247-4708-9, PAN 2064147 - přes Internetový archiv
Kelarev, A.V .; Miller, M .; Sokratova, O.V. (2005), „Jazyky rozpoznávané oboustrannými automaty grafů“, Proc. Estonian Akademy of Science, 54 (1): 46–54, ISSN 1736-6046, PAN 2126358
Kelarev, A.V .; Sokratova, O.V. (2001), „Řízené grafy a syntaktické algebry stromových jazyků“, J. Automaty, jazyky a kombinatorika, 6 (3): 305–311, ISSN 1430-189X, PAN 1879773
Kelarev, A.V .; Sokratova, O.V. (2003), "O shodě automatů definovaných orientovanými grafy" (PDF), Teoretická informatika, 301 (1–3): 31–43, doi:10.1016 / S0304-3975 (02) 00544-3, ISSN 0304-3975, PAN 1975219
Kiss, E.W .; Pöschel, R .; Pröhle, P. (1990), „Poddruhy odrůd generovaných grafovými algebrami“, Acta Sci. Matematika. (Segedín), 54 (1–2): 57–75, PAN 1073419
Lee, S.-M. (1988), „Graph algebry, které připouštějí pouze diskrétní topologie“, Congr. Číslo., 64: 147–156, ISSN 1736-6046, PAN 0988675
Lee, S.-M. (1991), „Jednoduché grafové algebry a jednoduché prsteny“, Jihovýchodní asijský býk. Matematika., 15 (2): 117–121, ISSN 0129-2021, PAN 1145431
McNulty, George F .; Shallon, Caroline R. (1983), „Vrozeně neomezeně založené konečné algebry“, Univerzální algebra a teorie mřížky (Puebla, 1982), Poznámky k přednášce v matematice., 1004, Berlín, New York: Springer-Verlag, str.206–231, doi:10.1007 / BFb0063439, hdl:10338.dmlcz / 102157, ISBN 978-3-540-12329-3, PAN 0716184 - přes Internetový archiv
Oates-Williams, Sheila (1984), „O odrůdě generované Murskiĭovou algebrou“, Algebra Universalis, 18 (2): 175–177, doi:10.1007 / BF01198526, ISSN 0002-5240, PAN 0743465, S2CID 121598599
Pöschel, R (1989), „The equational logic for graph algebras“, Z. Math. Logik Grundlag. Matematika., 35 (3): 273–282, doi:10,1002 / malq.19890350311, PAN 1000970

Další čtení

Raeburn, Iain (2005), Grafové algebry, Americká matematická společnost, ISBN 978-0-8218-3660-6