X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=notation.tex;h=341f135c07b314580e0793a8f6ca1fdd964ca474;hb=45c3472ad54cd6ceef01c44a07d71b97e9fe3eb9;hp=1f75d13271551f4aab51417dd55021ce5828a1ba;hpb=e0783236c7c0618f4a3ad1f8e584423cfbb085fa;p=saga.git

diff --git a/notation.tex b/notation.tex
index 1f75d13..341f135 100644
--- a/notation.tex
+++ b/notation.tex
@@ -21,6 +21,7 @@
 \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
 \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
+\n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
 \n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
 \n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
 \n{MST}{minimum spanning tree \[mstdef]}
@@ -29,6 +30,7 @@
 \n{$X \choose k$}{a set of all $k$-element subsets of a set~$X$}
 \n{$G/e$}{multigraph contraction \[contract]}
 \n{$G.e$}{simple graph contraction \[simpcont]}
+\n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
 \n{$\alpha(n)$}{the inverse Ackermann's function}
 \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
 \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
@@ -39,9 +41,35 @@
 \n{$\log n$}{a binary logarithm of the number~$n$}
 \n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
 \n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
-\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$}
-\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]}
+\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
+\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n \le m/n \}$ \[itjarthm]}
 \n{$W$}{word size of the RAM \[wordsize]}
+\n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
+\n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
+\n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
+\n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]}
+\n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
+\n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
+\n{$\equiv$}{congruence modulo a~given number}
+\n{$\<LSB>(x)$}{the position of the lowest bit set in~$x$ \[lsbmsb]}
+\n{$\<MSB>(x)$}{the position of the highest bit set in~$x$ \[lsbmsb]}
+\n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
+\n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
+\n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
+\n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
+\n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
+\n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
+\n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
+\n{$\prec$}{an~arbitrary linear order}
+\n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
+\n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
+\n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
+\n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
+\n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
+\n{$K_k$}{the complete graph on~$k$ vertices}
+\n{$C_k$}{the cycle on~$k$ vertices}
 }
 
 %--------------------------------------------------------------------------------
@@ -86,4 +114,12 @@ 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
 }$$
 
+\defn\id{setcont}%
+We can also extend the above definitions to contractions by a~set of vertices or edges.
+For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
+$f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
+does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
+as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
+where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$.
+
 \endpart