From 097f244236b682cc77c6ecf25be4150091d8daf9 Mon Sep 17 00:00:00 2001
From: Norbert Preining <norbert@preining.info>
Date: Sun, 2 Oct 2022 03:04:14 +0000
Subject: CTAN sync 202210020304

---
 info/mathtrip/src/graph.tex | 77 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 info/mathtrip/src/graph.tex

(limited to 'info/mathtrip/src/graph.tex')

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}
+   }
+}
-- 
cgit v1.2.3