User:Daviddaved/Graphs and manifolds

From Wikibooks, open books for an open world
Jump to: navigation, search

The main subjects of study of this book are the graphs, embedded in surfaces (2D manifolds), their local and global properties, and connections between them.

A graph G = {V, E} is a pair of sets, where E\in\P(V) is a subset of the power set P(V). We will refer to the elements of V as vertices, and elements of E as edges or hyper-edges.

A 2D manifold is a topological space, such that around every point p of the manifold there is an open set U homeomorphic to the unit disc D, and the homeomorphisms are coherent.

We will say that a graph G is embedded in a manifold M, if vertices ~ points, curves ~edges... In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface Σ is a representation of on Σ in which points of Σ are associated to vertices and simple arcs (homeomorphic images of [0,1]) are associated to edges in such a way that:

  • the endpoints of the arc associated to an edge are the points associated to the end vertices of ,
  • no arcs include points associated with other vertices,
  • two arcs never intersect at a point which is interior to either of the arcs.

A directed graph with boundary is a triple G = (V,\partial V,E}, where V is a set of points in a space, called vertices, \partial V is the subset of V called boundary vertices, and E is a set of directed pairs of elements of V, called edges.

For every edge (a,b) in E we call b a neighbor of a.