Contractions rulez.

[saga.git] / notation.tex

diff --git a/notation.tex b/notation.tex
index dd76722d50e0d1b2392929d59393d8f583e7e2c2..09994e8e58e1a514dc022c4e242f572b0c8ff83f 100644 (file)
--- a/notation.tex
+++ b/notation.tex
@@ -20,6 +20,49 @@
 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
 \n{MST}{minimal spanning tree \[mstdef]}
 \n{MSF}{minimal spanning forest \[mstdef]}
+\n{$X \choose k$}{a set of $k$-element subsets of a set~$X$}
+\n{$G/e$}{multigraph contraction \[contract]}
+\n{$G.e$}{simple graph contraction \[simpcont]}
 }
 
+\section{Multigraphs and contractions}
+
+Since the formalism of multigraphs is not fixed in the literature, we will
+better define it carefully, following \cite{diestel:gt}:
+
+\defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
+set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
+with the vertices, and $M$ is a mapping $E\mapsto V \cup {V \choose 2}$
+which assigns to each edge either a pair of vertices or a single vertex
+(if the edge is a loop).
+
+\proclaim{Notation}%
+When the meaning is clear from the context, we use our notation originally
+defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
+shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
+consider multigraphs with no multiple edges nor loops and simple graphs to be
+the same objects, although they formally differ.
+
+\defn\thmid{contract}%
+Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
+produces a multigraph $G/e=(V',E',M')$ such that:
+$$\eqalign{
+V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
+E' &= E(G) - \{e\},\cr
+M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
+m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
+}$$
+
+Sometimes we need contraction for simple graphs as well. It corresponds to performing
+the multigraph contraction, unifying parallel edges and deleting loops.
+
+\defn\thmid{simpcont}%
+Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
+produces a graph $G.e=(V',E')$ such that:
+$$\eqalign{
+V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
+E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
+m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
+}$$
+
 \endpart