notation.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Notation}
   6
   7 {\obeylines\parskip=0pt
   8 \def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
   9 \def\[#1]{[\thmref{#1}]}
  10 \n{$T[x,y]$}{the path in a tree~$T$ joining $x$ and $y$ \[heavy]}
  11 \n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
  12 \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
  13 \n{$G-e$}{graph $G$ with edge $e$ removed}
  14 \n{$G+e$}{graph $G$ with edge $e$ added}
  15 \n{$w(e)$}{weight of an edge $e$}
  16 \n{$V(G)$}{set of vertices of a graph~$G$}
  17 \n{$E(G)$}{set of edges of a graph~$G$}
  18 \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
  19 \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
  20 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
  21 \n{MST}{minimal spanning tree \[mstdef]}
  22 \n{MSF}{minimal spanning forest \[mstdef]}
  23 \n{$X \choose k$}{a set of $k$-element subsets of a set~$X$}
  24 \n{$G/e$}{multigraph contraction \[contract]}
  25 \n{$G.e$}{simple graph contraction \[simpcont]}
  26 \n{$\alpha(n)$}{the inverse Ackermann's function}
  27 }
  28
  29 \section{Multigraphs and contractions}
  30
  31 Since the formalism of multigraphs is not fixed in the literature, we will
  32 better define it carefully, following \cite{diestel:gt}:
  33
  34 \defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
  35 set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
  36 with the vertices, and $M$ is a mapping $E\mapsto V \cup {V \choose 2}$
  37 which assigns to each edge either a pair of vertices or a single vertex
  38 (if the edge is a loop).
  39
  40 \proclaim{Notation}%
  41 When the meaning is clear from the context, we use our notation originally
  42 defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
  43 shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
  44 consider multigraphs with no multiple edges nor loops and simple graphs to be
  45 the same objects, although they formally differ.
  46
  47 \defn\thmid{contract}%
  48 Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
  49 produces a multigraph $G/e=(V',E',M')$ such that:
  50 $$\eqalign{
  51 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
  52 E' &= E(G) - \{e\},\cr
  53 M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
  54 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
  55 }$$
  56
  57 Sometimes we need contraction for simple graphs as well. It corresponds to performing
  58 the multigraph contraction, unifying parallel edges and deleting loops.
  59
  60 \defn\thmid{simpcont}%
  61 Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
  62 produces a graph $G.e=(V',E')$ such that:
  63 $$\eqalign{
  64 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
  65 E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
  66 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
  67 }$$
  68
  69 \endpart