nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

A Category of “Undirected Graphs”

A Tribute to Hartmut Ehrig

verfasst von : John L. Pfaltz

Erschienen in: Graph Transformation, Specifications, and Nets

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, a category of undirected graphs is introduced where the morphisms are chosen in the style of mathematical graph theory rather than as algebraic structures as is more usual in the area of graph transformation.

A representative function, \({\omega }\), within this category is presented. Its inverse, \({\omega }^{-1}\), is defined in terms of a graph grammar, \({\varepsilon }\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Overview of Reconfigurable Petri Nets

Nächstes Kapitel Modular Termination of Graph Transformation

The codomain \(2^{V'}\) of f need not be \(2^V\), and its edge set \(E'\) need not have the same structure as E. Therefore, elements of the codomain are denoted with a prime.

We use suffix notation to denote the application of set-valued operators and functions.

This is a common terminology, but unfortunately such “closed neighborhoods” are not “closed”. The intersection of closed sets must be closed, but it easy to show that this is seldom true with “closed neighborhoods”.

We modify the usual definition of monotonicity to read: \(X \subseteq Y\) implies \(X.f \subseteq Y.f\), provided

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-75396-6_12/464263_1_En_12_IEq60_HTML.gif

This procedure has been quite effective reducing large graphs \(| V | \ge 1,000\), with at worst 6 iterative sweeps of V.

A graph, \(K_n\) is complete if all n nodes are mutually connected by an edge.

Because extreme points are simplicial (neighborhood is a clique), and because every chordal graph must have at least two extreme points [8, 9], every chordal graph can be so generated.

Arbib, M., Manes, E.: Arrows, Structures, and Functors: The Categorical Imperative. Academic Press, New York (1975)MATH

Castellini, G.: Categorical Closure Operators. Birkhauser, Boston (2003)CrossRefMATH

Chvátal, V.: Antimatroids, betweenness, convexity. In: László, W.C., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 57–64. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-76796-1_3 CrossRef

Edelman, P.H.: Abstract convexity and meet-distributive lattices. In: Combinatorics and Ordered Sets, Arcata, CA, pp. 127–150 (1986)

Edelman, P.H., Jamison, R.E.: The theory of convex geometries. Geom. Dedicata 19(3), 247–270 (1985)MathSciNetCrossRefMATH

Ehrig, H., Pfender, M., Schneider, H.J.: Graph grammars: an algebraic approach. In: IEEE Conference on SWAT (1973)

Engle, K.: Sperner theory. In: Hazewinkle, M. (ed.) Encyclopedia of Mathematics. Springer, Heidelberg (2001)

Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM J. Algebra Discrete Methods 7(3), 433–444 (1986)MathSciNetCrossRefMATH

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)MATH

10.

MacLane, S.: Categories for the Working Mathematician, 2nd edn. Springer, New York (1998). https://doi.org/10.1007/978-1-4612-9839-7 MATH

11.

Ore, O.: Mappings of closure relations. Ann. Math. 47(1), 56–72 (1946)MathSciNetCrossRefMATH

12.

Pfaltz, J., Šlapal, J.: Transformations of discrete closure systems. Acta Math. Hung. 138(4), 386–405 (2013)MathSciNetCrossRefMATH

13.

Pfaltz, J.L.: Neighborhood expansion grammars. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 30–44. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46464-8_3 CrossRef

14.

Pfaltz, J.L.: Finding the mule in the network. In: Alhajj, R., Werner, B. (eds.) International Conference on Advances in Social Network Analysis and Mining, ASONAM 2012, Istanbul, Turkey, pp. 667–672, August 2012

15.

Pfaltz, J.L.: Mathematical continuity in dynamic social networks. Soc. Netw. Anal. Min. (SNAM) 3(4), 863–872 (2013)MathSciNetCrossRef

16.

Pfaltz, J.L.: The irreducible spine(s) of undirected networks. In: Lin, X., Manolopoulos, Y., Srivastava, D., Huang, G. (eds.) WISE 2013. LNCS, vol. 8181, pp. 104–117. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41154-0_8 CrossRef

17.

Pfaltz, J.L.: Computational processes that appear to model human memory. In: Figueiredo, D., Martín-Vide, C., Pratas, D., Vega-Rodríguez, M.A. (eds.) AlCoB 2017. LNCS, vol. 10252, pp. 85–99. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58163-7_6 CrossRef

18.

Pierce, B.C.: Basic Category Theory for Computer Scientists. MIT Press, Cambridge (1991)MATH

19.

Rozenberg, G. (ed.): The Handbook of Graph Grammars. World Scientific, Singapore (1997)MATH

Titel: A Category of “Undirected Graphs”
verfasst von: John L. Pfaltz
Verlag: Springer International Publishing
Buch: Graph Transformation, Specifications, and Nets
Print ISBN: 978-3-319-75395-9

Electronic ISBN: 978-3-319-75396-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-75396-6_12

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Carina Kießling von der Strategieberatung Roland Berger/© Monika Walther Fotografie | ATZ, Beijing Auto Show 2024: Deutsche Hersteller wollen angreifen./© EKH-Pictures / Generated with AI / Stock.adobe.com, Buchstaben, die aus einem Megaphon kommen/© MicroStockHub/Getty Images/iStock, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.