Graph Theory

Lars Noschinski 🌐

April 28, 2013

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

This development provides a formalization of directed graphs, supporting (labelled) multi-edges and infinite graphs. A polymorphic edge type allows edges to be treated as pairs of vertices, if multi-edges are not required. Formalized properties are i.a. walks (and related concepts), connectedness and subgraphs and basic properties of isomorphisms.

This formalization is used to prove characterizations of Euler Trails, Shortest Paths and Kuratowski subgraphs.

License

BSD License

Topics

Session Graph_Theory