summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/graph.tex
diff options
context:
space:
mode:
Diffstat (limited to 'info/mathtrip/src/graph.tex')
-rw-r--r--info/mathtrip/src/graph.tex77
1 files changed, 77 insertions, 0 deletions
diff --git a/info/mathtrip/src/graph.tex b/info/mathtrip/src/graph.tex
new file mode 100644
index 0000000000..b3d318fda3
--- /dev/null
+++ b/info/mathtrip/src/graph.tex
@@ -0,0 +1,77 @@
+%This macro provides the math text for the second column of page 5
+%
+%The macro has one parameter:
+% 1) The width of the text
+\newcommand\TFiveGrapheOne[1]{%
+ \def\LineOfArray##1##2{##1&{\raggedright ##2}\\}
+ \parbox[t]{#1}{%
+ %Space dedicated to the explanation of the graph's
+ %vocabulary in the tabular environment
+ \deflength{\HSpace}{.70#1}
+ \TFiveGraphFontSize
+ %Since the column is narrow, ragged at right
+ %produces better spacing
+ %
+ \raggedright
+ \TFiveTitle{Definitions:}
+ \begin{tabular}{@{}l@{\hspace{.25em}}p{\HSpace}}
+ \LineOfArray{Loop}{An edge connecting a vertex to itself.}
+ \LineOfArray{Directed}{Each edge has a direction.}
+ \LineOfArray{Simple}{Graph with no loops or multi-edges.}
+ \LineOfArray{Walk}{A sequence $v_0e_1v_1\ldots e_\ell v_\ell$.}
+ \LineOfArray{Trail}{A walk with distinct edges.}
+ \LineOfArray{Path}{A trail with distinct vertices.}
+ \LineOfArray{Connected}{A graph where there exists a path between any two vertices.}
+ \LineOfArray{Component}{A maximal connected subgraph.}
+ \LineOfArray{Tree}{A connected acyclic graph.}
+ \LineOfArray{Free tree}{A tree with no root.}
+ \LineOfArray{DAG}{Directed acyclic graph.}
+ \LineOfArray{Eulerian}{Graph with a trail visiting each edge exactly once.}
+ \LineOfArray{Hamiltonian}{Graph with a cycle visiting each vertex exactly once.}
+ \LineOfArray{Cut}{A set of edges whose removal increases the number of components.}
+ \LineOfArray{Cut-set}{A minimal cut.}
+ \LineOfArray{Cut edge}{A size 1 cut.}
+ \LineOfArray{k-Connected}{A graph connected with the removal of any $k-1$ vertices.}
+ \LineOfArray{k-Tough}{$\forall S \subseteq V, S \neq \emptyset$ we have $k\cdot c(G-S) \leq \vert S \vert$.}
+ \LineOfArray{k-Regular}{A graph where all vertices have degree $k$.}
+ \LineOfArray{k-Factor}{A $k$-regular spanning subgraph.}
+ \LineOfArray{Matching}{A set of edges, no two of which are adjacent.}
+ \LineOfArray{Clique}{A set of vertices, all of which are adjacent.}
+ \LineOfArray{Ind. set}{A set of vertices, none of which are adjacent.}
+ \LineOfArray{Vertex cover}{A set of vertices which cover all edges.}
+ \LineOfArray{Planar graph}{A graph which can be embeded in the plane.}
+ \LineOfArray{Plane graph}{An embedding of a planar graph.}
+ \end{tabular}
+
+ \TFiveTitle{Planar graphs}
+ \AdjustSpace{1ex plus .5ex minus .2ex}
+ \begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
+ \Fm{\sum_{v\in V} \deg(v) = 2 m}
+ \end{DisplayFormulae}
+ \AdjustSpace{1ex plus .5ex minus .2ex}
+ If $G$ is planar then $n - m + f = 2$, so
+ \AdjustSpace{1ex plus .5ex minus .2ex}
+ \begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
+ \Fm{f \leq 2n - 4, \quad m \leq 3 n - 6}
+ \end{DisplayFormulae}
+ \AdjustSpace{1ex plus .5ex minus .2ex}
+ Any planar graph has a vertex with degree $\leq 5$.
+
+ \TFiveTitle{Notation:}
+ \begin{tabular}{@{}lp{\HSpace}}
+ \LineOfArray{$E(G)$}{Edge set}
+ \LineOfArray{$V(G)$}{Vertex set}
+ \LineOfArray{$c(G)$}{Number of components}
+ \LineOfArray{$G[S]$}{Induced subgraph}
+ \LineOfArray{$\deg(v)$}{Degree of $v$}
+ \LineOfArray{$\Delta(G)$}{Maximum degree}
+ \LineOfArray{$\delta(G)$}{Minimum degree}
+ \LineOfArray{$\chi(G)$}{Chromatic number}
+ \LineOfArray{$\chi_E(G)$}{Edge chromatic number}
+ \LineOfArray{$G^c$}{Complement graph}
+ \LineOfArray{$K_n$}{Complete graph}
+ \LineOfArray{$K_{n_1,n_2}$}{Complete bipartite graph}
+ \LineOfArray{$\ramsey(k,\ell)$}{Ramsey number}
+ \end{tabular}
+ }
+}