summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/graph.tex
blob: b3d318fda316f54d58b3d0466e9cbf4fec3dfbf8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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}
   }
}