グラフ代数

数学、特に普遍代数とグラフ理論の分野において、グラフ代数は有向グラフに代数構造を与える方法です。これはマクナルティとシャロン^[1]によって導入され、それ以来普遍代数の分野で多くの用途が見られてきました。

意味

$D = (V, E)$ を有向グラフとし、0 $を$ $V$ に含まれない要素とする。D に関連付けられたグラフ代数は基底集合を持ち、次の規則で定義される乗算を備えている $。$ $V\cup \{0\}$

$xy = x$ かつ、 $x,y\in V$ $(x,y)\in E$
かつの場合、 $xy$ $= 0$ となります。 $x,y\in V\cup \{0\}$ $(x,y)\notin E$

アプリケーション

この概念により、グラフ理論の手法を普遍代数や離散数学、コンピュータサイエンスのその他のいくつかの分野に利用することが可能になった。グラフ代数は、例えば、双対性、^[2] 方程式理論、^{[ 3]} 平坦性、^[4] 類群環、^[5] 位相、^[6] 多様体、^[7] 有限状態機械、^[8]^[9] ツリー言語とツリーオートマトン、^[10]などに関する構成に利用されてきた。

参照

引用

^ マクナルティ＆シャロン1983年、206-231頁。
^ Davey et al. 2000、145-172ページ。
^ Pöschel 1989、pp. 273–282。
^ デリッチ2001、453-469頁。
^ リー1991、117-121頁。
^ リー1988年、147-156頁。
^ オーツウィリアムズ 1984年、175-177頁。
^ Kelarev、Miller、Sokratova 2005、46–54 ページ。
^ Kelarev & Sokratova 2003、31–43 ページ。
^ Kelarev & Sokratova 2001、305–311 ページ。

引用文献

Davey, Brian A.; Idziak, Pawel M.; Lampe, William A.; McNulty, George F. (2000). 「双対可能性とグラフ代数」.離散数学. 214 (1): 145–172. doi : 10.1016/S0012-365X(99)00225-3 . ISSN 0012-365X. MR 1743633.
Delić, Dejan (2001). 「平坦グラフ代数の有限基数」. 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). 「グラフの両面オートマトンによって認識される言語」Proc. Estonian Akademy of Science . 54 (1): 46–54. ISSN 1736-6046. MR 2126358.
Kelarev, AV; Sokratova, OV (2001). 「有向グラフとツリー言語の統語代数」. J. Automata, Languages & Combinatorics . 6 (3): 305–311. ISSN 1430-189X. MR 1879773.
Kelarev, AV; Sokratova, OV (2003). 「有向グラフで定義されたオートマトン合同性について」(PDF) .理論計算機科学. 301 (1–3): 31–43. doi :10.1016/S0304-3975(02)00544-3. ISSN 0304-3975. MR 1975219.
Lee, S.-M. (1988) .「離散トポロジーのみを許容するグラフ代数」。Congr . Numer . 64 : 147–156。ISSN 1736-6046。MR 0988675 。
Lee, S.-M. (1991). 「単純なグラフ代数と単純な環」. Southeast Asian Bull. 数学. 15 (2): 117–121. ISSN 0129-2021. MR 1145431.
McNulty, George F.; Shallon, Caroline R. (1983)。「本質的に非有限基底の有限代数」。Freese, Ralph S.、Garcia, Octavio C. (編著)。普遍代数と格子理論 (プエブラ、1982)。数学講義ノート。第 1004 巻。ベルリン、ニューヨーク市: S pringer-Verlag。pp . 206–231。doi :10.1007/ BFb0063439。hdl : 10338.dmlcz / 102157。ISBN 978-354012329-3. MR 0716184 –インターネットアーカイブ経由。
Oates-Williams, Sheila (1984). 「Murskiĭ の代数によって生成される多様体について」. Algebra Universalis . 18 (2): 175–177. doi :10.1007/BF01198526. ISSN 0002-5240. MR 0743465. S2CID 121598599.
Pöschel, R. (1989). 「グラフ代数の方程式論理」Z. Math. Logik Grundlag. Math . 35 (3): 273–282. doi :10.1002/malq.19890350311. MR 1000970.

さらに読む

ケラレフ、AV (2003)。グラフ代数とオートマトン。ニューヨーク市:マルセル・デッカー。ISBN 0-8247-4708-9. MR 2064147 –インターネットアーカイブ経由。
Kiss, EW; Pöschel, R.; Pröhle, P. (1990). 「グラフ代数によって生成される多様体のサブ多様体」. Acta Sci. Math . 54 (1–2): 57–75. MR 1073419.
レイバーン、イアン (2005)。グラフ代数。アメリカ数学会。ISBN 978-082183660-6。

[FOOTNOTEMcNultyShallon1983[httpsarchiveorgdetailsuniversalalgebra0000unsepage206_pp._206–231]-1] マクナルティ＆シャロン1983年、206-231頁。

[FOOTNOTEDaveyIdziakLampeMcNulty2000145–172-2] Davey et al. 2000、145-172ページ。

[FOOTNOTEPöschel1989273–282-3] Pöschel 1989、pp. 273–282。

[FOOTNOTEDelić2001453–469-4] デリッチ2001、453-469頁。

[FOOTNOTELee1991117–121-5] リー1991、117-121頁。

[FOOTNOTELee1988147–156-6] リー1988年、147-156頁。

[FOOTNOTEOates-Williams1984175–177-7] オーツウィリアムズ 1984年、175-177頁。

[FOOTNOTEKelarevMillerSokratova200546–54-8] Kelarev、Miller、Sokratova 2005、46–54 ページ。

[FOOTNOTEKelarevSokratova200331–43-9] Kelarev & Sokratova 2003、31–43 ページ。

[FOOTNOTEKelarevSokratova2001305–311-10] Kelarev & Sokratova 2001、305–311 ページ。