]> mj.ucw.cz Git - saga.git/blob - notation.tex
Korektury.
[saga.git] / 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]{[\ref{#1}]}
10 \n{$\bb R$}{the set of all real numbers}
11 \n{$\bb N$}{the set of all natural numbers, including 0}
12 \n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
13 \n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
14 \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
15 \n{$G-e$}{graph $G$ with edge $e$ removed}
16 \n{$G+e$}{graph $G$ with edge $e$ added}
17 \n{$w(e)$}{weight of an edge $e$}
18 \n{$V(G)$}{set of vertices of a graph~$G$}
19 \n{$E(G)$}{set of edges of a graph~$G$}
20 \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
21 \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
22 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
23 \n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
24 \n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
25 \n{MST}{minimum spanning tree \[mstdef]}
26 \n{MSF}{minimum spanning forest \[mstdef]}
27 \n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
28 \n{$X \choose k$}{a set of all $k$-element subsets of a set~$X$}
29 \n{$G/e$}{multigraph contraction \[contract]}
30 \n{$G.e$}{simple graph contraction \[simpcont]}
31 \n{$\alpha(n)$}{the inverse Ackermann's function}
32 \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
33 \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
34 \n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
35 \n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
36 \n{${\bb E}X$}{expected value of a~random variable~$X$}
37 \n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
38 }
39
40 \section{Multigraphs and contractions}
41
42 Since the formalism of multigraphs is not fixed in the literature, we will
43 better define it carefully, following \cite{diestel:gt}:
44
45 \defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
46 set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
47 with the vertices, and $M$ is a mapping $E\mapsto V \cup {V \choose 2}$
48 which assigns to each edge either a pair of vertices or a single vertex
49 (if the edge is a loop).
50
51 \proclaim{Notation}%
52 When the meaning is clear from the context, we use our notation originally
53 defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
54 shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
55 consider multigraphs with no multiple edges nor loops and simple graphs to be
56 the same objects, although they formally differ.
57
58 \defn\id{contract}%
59 Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
60 produces a multigraph $G/e=(V',E',M')$ such that:
61 $$\eqalign{
62 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
63 E' &= E(G) - \{e\},\cr
64 M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
65 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
66 }$$
67
68 Sometimes we need contraction for simple graphs as well. It corresponds to performing
69 the multigraph contraction, unifying parallel edges and deleting loops.
70
71 \defn\id{simpcont}%
72 Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
73 produces a graph $G.e=(V',E')$ such that:
74 $$\eqalign{
75 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
76 E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
77 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
78 }$$
79
80 \endpart