Graph
Introduction of Graph
Definition of Graph
Multigraphs
Pseduographs
Directed Graphs
Directed Multigraphs
Graphs Models
Graph Terminology
We will learn the following terms:
 Adjacent
 connect
 endpoint
 neighborhood
 degree
 initial
 terminal
 indegree
 outdegree
 complete
 cycles
 wheels
 ncubes
 bipartite
 subgraph
 union
Special Types of Graphs
Bipartite Graphs
New Graphs from Olds
Graph Representation & Isomorphism
Graph Representation
Adjacency List
Adjacency Matrices
Incidence Matrices
Graph Isomorphism
Connectivity
Path
In a undirected graph, a path of length $n$ from $u$ to $v$ is a sequence of adjacent edges going from vertex $u$ to $v$.
 A path is a circuit , or close walk, if $u=v$
 A path traverses then vertices along it
 A path is simple if it contains no edge more than once. When a path is simple, we can denote this path by these vertices sequence $x_{0},x_{1},⋯,x_{n}$
Path in Directed Graphs
Same as in undirected graphs, but the path must go in the direction of the arrows.
 When there are no multiple edged in the directed graph, this path is denoted by its vertices sequence same as that in undirected graph
 A path of length greater than zero and begins and ends at the same vertex is called a circuit or cycle
Connectedness
An undirected graphs is connected if there is a path between every pair of distinct vertices in the graph. An undirected graph that is not connected is called disconnected. We say that we disconnect a graph when we remove vertices or edges, or both, to produce disconnected subgraph.
Theorem: There is a simple path between any pair of vertices in a connected undirected graph.
Cut Vertices & Cut Edge
We call a connected graph is a connected component
 The removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called cut vertices or articulation points.
 An edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge.
 A cut vertex or cut edge separates 1 connected component into 2 if removed.
Vertex Connectivity & Edge Connectivity
Connected graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex.
A subset $V_{′}$ of the vertex set $V$ of $G=(V,E)$ is a vertex cut, or separating set, if $G−V_{′}$ is disconnected. We define the vertex connectivity of a noncomplete graph $G$ as the minimum number of vertices in a vertex cut, denoted by $K(G)$. The larger $K(G)$ is, the more connected we consider $G$ to be. A graph is kconnected, if $K(G)≥k$.
Same as vertex connectivity, we can define the edge connectivity. A set of edges $E_{′}$ is called an edge cut of $G$ if the subgraph $G−E_{′}$ is disconnected. The edge connectivity $λ$ of a graph $G$, denoted by $λ(G)$, is the minimum number of edges in an edge cut of $G$.
And we have $K(G)≤λ(G)≤min{deg(v),v∈V}$
Directed Connectedness
A directed graph is strongly connected if there is a directed path from $a$ to $b$ for any two vertices $a$ and $b$.
That means there is path from $a$ to $b$ and also a path from $b$ to $a$
It is weakly connected if and only if the underlying undirected graph is connected. And we can get strongly implies weakly but not viceverse.
Counting Paths using Adjacency Matrices
Let $A$ be the adjacency Matrices of graph $G$. The number of different paths of length $r$ from $v_{i}$ to $v_{j}$, where $r$ is a positive integer,equals the $(i,j)$th entry of $A_{r}$.
Paths & Isomorphism
The connectedness and the existence of a circuit or simple circuit of length $k$ are graph invariants with respect to isomorphism.
Euler and Hamilton Paths
LEADIN: Bridges of Königsberg Problem七桥问题
Eulerian Graph
An Euler Circuit in a graph $G$ is a simple circuit containing every edge of $G$.
An Euler Path in $G$ is a simple path containing every edge of $G$.
An Euler Tour is a a walk in a graph if it starts and ends in the same place and uses each edge exactly once.
An Euler Trail is a walk in a graph if it uses each edge exactly once.
A connected graph $G$ is Eulerian when it has at least two vertices has an Euler circuit. And a graph is Eulerian if and only if G is connected and has no vertices of odd degree.
A connected graph $G$ has an Euler trail from node $a$ to some other node $b$ if and only if $G$ is connected and $a=b$ are the only two nodes of odd degrees.
Constructing Euler Circuit Algorithm
procedure Euler(G: connected multigraph with all vertices of even degree)
circuit := a circuit in G begining at an arbitrarily chosen vertex with edges
successively added to form a path that returns to this vertex
H := G whith the edges of this circuit removed
while H has edges:
subcircuit := a circuit in H beginning at a vertex in H that also is an
endpoint of an edge of circuit
H := H with edges of subcircuit and all isolated vertices removed
circuit := circuit with subcircuit inserted at the appropriate vertex
return circuit {circuit is an Euler circuit}
Hamilton Graph
A graph has a Hamiltonian tour if there is a tour that visits every vertex exactly once (and returns to its starting point).
A graph with a Hamiltonian tour is called a Hamiltonian graph.
A Hamiltonian path is a path that contains each vertex exactly once.
A Hamiltonian circuit is a circuit that traverses each vertex in $G$ exactly once.
At this time, we don't have nice characterization of Hamiltonian graphs the way there was with Eulerian graphs. But we have some experience in this area. For example, there are some properties imply a graph not a Hamilton, such as (1) vertex with degree 1, (2) vertex with two degrees must be in the circuit. When a circuit is being constructed and this circuit has passed through a vertex, then all remaining edges incident with this vertex, other than the two used circuit, can be removed from consideration. And a Hamilton circuit can't contain a smaller circuit within it.
Hamiltonian Path Theorems
 Dirac's Theorem: If $G$ is connected, simple, has $n≥3$ vertices, and $∀vdeg(v)≥2n $, then $G$ has a Hamiltonian circuit.
 Ore's Corollary: If $G$ is connected, simple, has $n≥3$ nodes, and $deg(u)+deg(v)≥n$ for every pair $u,v$ of nonadjacent nodes, then $G$ has a Hamiltonian circuit.
Shortest Path Problems
Introduction
 A weight graph is one in which weight are assigned to all edges connecting each two vertices.
 Such number may have different meanings, such as instance, travelling distance, monthly cost or travelling time between two vertices.
 The length of a path in a weight graph is the sum of the weights of the edges of this path. This length is different from the number of edges in a path in a graph without weights.
Shortest Path Algorithm
Powered by Dijkstra
 起始点的路径标为0，其他路径标为无穷大，在后续遍历中更新
 定义一个已经标好最短路径的点的集合S
 将最短路径的点放进去
 从新放入的店开始，寻找其他点的最短路径
 重复3~4，直到达到路径的目标
Dijkstra's Algorithm Complexity
 Dijkstra's algorithm finds the length of a shortest path between two vertices in a connected simple undirected and weighted graph.
 Dijkstra's algorithm uses $O(n_{2})$ operations(additions and comparisons) to find.
Related Problems
 Determining the shortest path from $a$ to an assigned vertex
 Determining the shortest path of any two vertices in the graph
Finding the shortest path between any two vertices using distance matrix
Distance Matrix: Let G is a graph with n vertices. The distance matrix of G is $D=(d_{ij})_{n×n}$
 $d_{ij}$ represent the weights of the edges $(v_{i},v_{j})$
 If there is no edge between $v_{i}$ and $v_{j}$ then $d_{ij}=∞$
 $d_{ij}$ is the shortest length of the path from $v_{i}$ to $v_{j}$ with two edges
 $d_{ij}$ is the shortest length of the path from $v_{i}$ to $v_{j}$ with $k$ edges
To get the shortest length of path, we define $⊕$: Let $A=(a_{ij})_{n×n}$ and $B=(b_{ij})_{n×n}$, and $C=A⊕B$, where $c_{ij}=min(a_{ij},b_{ij})$.
So we can define $P=D⊕D_{2}⊕D_{3}⊕⋯⊕D_{n}$, and in such matrix, $p_{ij}$ represent the shortest length from $v_{i}$ to $v_{j}$.
Travelling Salesperson Problem
In an undirected simple weighted graph, we need to find the shortest length of Hamilton path.
This is a NP problem
Planar Graph
Definition
A graph is called planar if it can be drawn in the plane in such way that no two edges cross.
A planar representation of a graph splits the plane into regions that we call it faces, including an unbound region.
Euler Theorem
Let $G$ be a connected planar simple graph with $e$ edges , $v$ vertices. Let $r$ be the number of regions in a planar representation of $G$, then we have $r=e−v+2$
We can prove this theorem by mathematical induction. Constructing a sequence of subgraphs $G_{1},G_{2},⋯,G_{n}$ successively adding an edge at each stage.
 Basic step: G have no cycle, so $e_{1}=1$, $v_{1}=2$, $r_{1}=1$
 Inductive step: there are two ways to add an edge:
 Adding an edge by connecting two existing vertices, which add a new region
 Adding a new vertex and connect it with graph, which keeps region unchanged
Corollary

No matter how we redraw a planar graph it will have the same number of region

Every simple $n$node ($n≥3$) planar graph $G$ has at most $3n−6$ edges.

If $G$ a connected planar simple graph, then $G$ has a vertex of degree not exceeding five.
The main idea in proof: Every face has at least 3 edges no its boundary. Every edge lies on the boundary of at most 2 faces Thus $2e≥3r$

If a connected planar simple graph has $e$ edges and $n$ vertices with $n≥3$ and no circuit of length three, then $e≤2n−4$
Kuratowski Theorem
Kuratowski Graph
Kuratowski graphs are two typically nonplanar graphs.
In the Kuratowski graph, we can find that:
 If we replace edges in a Kuratowski graph by paths of whatever length, they remain nonreplace.
 If a graph contains a subgraph obtained by starting with $K_{5}$ or $K_{3,3}$ and replacing edges with paths, then $G$ is nonplanar.
Homeomorphic Graph
If a graph is planar, so will be any graph obtained by removing an edge ${u,v}$ and adding a new vertex $w$ with edges ${u,w}$ and ${w,v}$ . Such an operation is called an elementary subdivision .
The graphs are called homeomorphic if they are obtained from the same graph by a sequence of elementary subdivisions.
Kuratowski Theorem
A graph is planar if and only if it contains no subgraph obtained from $K_{5}$ or $K_{3,3}$ by replacing edges with paths.
Graph Coloring
Lead in: four colors are always enough to color any map drawn on a plane.
Coloring graphs
Suppose that $G=(V,E.γ)$ is a graph without no multiple edges, and $C=c_{1},c_{2},c_{3},⋯$ is any set of $n$ colors. Any function $f:V→C$ is called a coloring of the graph $G$ using $n$ colors.
A coloring is proper if any two adjacent vertices $v$ and $u$ have different colors. The smallest number of colors needed to produce a proper coloring of a graph $G$ is called the chromatic number of $G$, which is denoted by $χ(G)$.
Fourcolor Theorem
The vertices of ant planar graph can be 4colored in such a way that no two adjacent vertices receive the same color.
This is hard to prove.
FiveColor Theorem
Any planar graph can be colored with five colors.
Prove
Let $G$ be a nodeminimal counterexample to the theorem, for example, a planar graph that requires 6 colros.
As $G$ is a planar graph, we can get $G$ must have a node $q$ with degree $≤5$. Let the nodes adjacent to q be named as $v_{1},v_{2},v_{3},v_{4},v_{5}$, and this five nodes can not form $K_{5}$, also because this is a planar graph. So there must be two vertices $a_{1},a_{2}$ in this five vertices that have no edge between them.
So we can "contract" the edges $<q,v_{1}>$ and $<a,v_{2}>$ to get a new planar graph $G_{′}$, and the vertices $v_{1}$, $v_{2}$ and $q$ become a new vertices in $G_{′}$. $G_{′}$ is 5 colorable since it has fewer nodes than $G$, so we can find that we color the $G$ using the five colors in the $G_{′}$, which meaning the counter example is not counter.
Applications of Graph Coloring
 Fifteen different foods are to be held in refrigerated compartments within the same refrigator.
 How can the final exams be scheduled at a university so that no students has two exams at the same time.
 Frequency assignment. we need to assign different radio frequency to two radio station whose distance is to short.
Chromatic Polynomials
If $G$ is a graph and $n≥0$ is an integer, let $P_{G}(n)$ be the number of ways to color $G$ properly using $n$ or fewer colors.$P_{G}(n)$ is called the chromatic polynomials. And if we can find the chromatic polynomials ,we can easily get the chromatic number of $G$.
For example, for a linear graph $L_{4}$, we have the chromatic polynomials $x(x−1)_{3}$, so $P_{L_{4}}(0)=0$, $P_{L_{4}}(1)=0$ and $P_{L_{4}}(2)=2$, so $χ(L_{4})=2$.
Theorem 1
If $G$ is disconnected graph with components $G_{1},G_{2},G_{3},⋯,G_{m}$, then $P_{G}(x)$ is the product of the chromatic polynomials for each components.
$P_{G}(x)=P_{G_{1}}(x)P_{G_{2}}(x)⋯P_{G_{m}}(x)$
Subgraph and Quotient Graphs
One of the most important subgraphs is the one that arises by deleting one edge and no vertices. If $G=(V,E,γ)$ is a graph and $e∈E$, then we denote by $G_{e}$ the subgraph obtained by omitting the edge $e$ from $E$ and keeping all vertices.
Suppose that $G=(V,E,γ)$ is a graph without multiple edges between the same vertices and that $R$ is an equivalence relation on the set $V$. Construct the quotient graphs $G_{R}$ as follow: The vertices of $G_{R}$ are the equivalence classes of $V$ produced by $R$. If $[v]$ and $[w]$ are the equivalence classes of vertices $v$ and $w$, then there is an edge in $G_{R}$ from $[v]$ to $[w]$ if and only if some vertices in $[v]$ is connected to sone vertices in $[w]$ in the graph $G$.
Theorem 2
Let $G=(E,V,γ)$ be a graph without multiple edges, and let $e∈e$, say $e={a,b}$. So we have $G_{e}$, subgraph obtained by deleting $e$ and $G_{e}$, the quotient graph of $G$ obtained by merging the end points of $e$. And then with $x$ colors:
$P_{G}(x)=P_{G_{e}}(x)−P_{G_{e}}(x)$
Transport Networks
An important use of labeled graph is to model what are commonly called transport networks. The label on an edge represents the maximum flow that can be passed through that edge and is called the capacity of the edge.
Transport Network
A transport network, or a network, is a connected digraph $N$ with the following properties:
 There is a unique node, the source, that has indegree 0. We always label the source with node 1.
 There is a unique node, the sink, that has outdegree 0. If $N$ has n nodes, and we always label the sink with node n.
 The graph $N$ is labeled. The label, $C_{ij}$, on edge $(i,j)$ is a nonnegative number called the capacity of the edge.
Flow
A flow in a network is a function that assigns to each edge $(i,j)$ of $N$ a nonnegative number $F_{ij}$ that does not exceed $C_{ij}$.
And when talking about flow, we have:
 Conservation of flow
 Value of flow
For any network, an important question is to determine the maximum value of a flow through the network and to describe a flow that has the maximum value.
Although edge $(j,i)$ is not in $N$, there is no harm in consideration such a virtual flow as long as it only has effect of reducing the existing flow in the actual edge $(i,j$)
Labeling Algorithm
Let $N$ be a network with $n$ nodes and $G$ be the symmetric closure of $N$. All edges and paths used are in $G$.
 Begin with all flows set to 0.
 As we proceed, it will be convenient to track the excess capacities in the edges and how they change rather than tracking the increasing flows.
 When the algorithm terminates, it is easy to find the maximum flow from the final excess capacities.
STEP 1
 Let $N_{1}$ be the set of all nodes connected to the source by an edge with positive excess capacities.
 Label each node $N_{j}$ in $N_{1}$ with $[E_{j},1]$, where $E_{j}$ is the excess capacity $e_{ij}$ of edge $(1,j)$. The 1 in the label indicates that $j$ is connected to the source, node 1.
STEP 2

Let node $j$ in $N_{1}$ be the node with the smallest node number and let $N_{2}(j)$ be the set of all unlabeled nodes,
other than the source and those are joined to node $j$ and have positive excess capacity.

Suppose that node $k$ is in $N_{2}(j)$ and $(j,k)$ is the edge with positive excess capacity. Label node $k$ with $[E_{k},j]$, where $E_{k}$ is the minimum of $E_{j}$ and the excess capacity $e_{jk}$ of edge $(j,k)$.

When all the nodes in $N_{2}(j)$ are all labeled in this way, repeat this process for the other nodes in $N_{1}$. Let
$N_{2}=U_{j∈N_{1}}N_{2}(j)$
STEP 3

Repeat Step 2 , labeling all previously unlabeled nodes $N_{3}$ that can be reached from a node in $N_{2}$ by an edge having positive excess capacity.

Continue this process forming sets $N_{4}$, $N_{5}$, ... until after a finite number or steps

either the sink has not been labeled and no other nodes can be labeled. It can happened that no nodes have been labeled; remember that the source is not labeled or the sink has been reached.
In this case, the algorithm terminates and the total flow is a maximum flow.

or the sink has been labeled.
In this case, the sink has been labeled with $[E_{n},m]$ where $E_{n}$ is the amount of extra flow that can be made to reach the sink through the path.
STEP 4
We examine the path in reverse:
 If edge $(i,j)∈N$, we increase the flow in $(i,j)$ and decrease the excess capacity $e_{ij}$ by the sam amount. Simultaneously, we increase excess capacity of the virtual edge $(i.j)$
 If on the other hand , edge $(i,j)∈N$, we decrease the flow in $(j,i)$ and increase its excess capacity. Same as before, decrease the excess capcaity in $(i.j)$.
Back to the step 1.
What a complex algorithm!
Cut
A cut in a network is a set $K$ of edges having the property that every path from the source to the sink contains at least one edge from $K$.
The capacity of a cut $K$ is the sum of the capacities of all edges in $K$. If $F$ is any flow and $K$ is any cut, there must be $value(F)≤c(K)$.
And we have a theorem that a maximum flow $F$ in a network has value equal to the capacity of a minimum cut of the network.
Super Source & Super Sink
When we meet a network with sources or sinks more than one, we can add a virtual source or virtual sink to use the labeling algorithm, which is connected with the real source and sink with large enough edge. These virtual source and sink is are called super source and super sink.