學海無涯，思境無維；數乃六藝，理之始也。
或有一得足矣 愚千慮

$$$$

Graph Theory

Simple Directed Graph

$$\{\begin{array}{l}V:Vertices\\ E:Edges\in V\times V\end{array}$$

initial vertex and terminal vertex

degree of a vertex

• indeg(v) : indegree of v, the number of edges that terminated at v.
• outdeg(v) : outdegree of v, the number of edges that initiate at v.
• deg(v) = indeg(v) + outdeg(v)

path : A path between

$x$ and

$y$ vertices can always be described by its edge list.

• The initial vertex of
  $e_1$ is x.
• The terminal vertex of
  $e_n$ is y.
• The number of edges in the edge list(n) is path length
• A edge could only exist once in a path.

circuit : A circuite is a path that terminates at it's initial vertex.

subpath : A subpath is any portion of the path describe by one or more consecutive edges in the edge list.

• any path is it's own subpath (but improper)
• all other non-empty subpath are called proper subpath

A path or circuite is simple, if contains no proper subpath that's a circuit.

Multigraph

The graph with a vertex(s) that contains more than one edge to other vertices.

Undirected Graph

The E(edges) are undirected,

$\mathrm{\forall }e=(a,b)\in E,(b,a)\in E$

Complete Graph (

$K_n$)

each pair of distinct vertices are directly connected to one another.

$$\mathrm{\forall }{v}_i,v_j\in V,v_i\ne v_j,(v_i,v_j)\in E$$

Round-robin (Tournament Graph) is a complete graph.

Single-elimination tournament graph (tree-like):

• once vertex(the champion) has no edge terminating at it and at least one edge initiating from it.
• every other vertex is the terminal vertex of exactly one edge.
• there is a path from the champion vertex to every other vertex.

Subgraph

let

$G=(V,E)$ be a graph of any kind:

• directed / undirected
• multigraph / unidirected

$G^{\prime }=(V^{\prime },E^{\prime })$ is a subgraph of

$G$,

$$⟺V^{\prime }\subseteq V\wedge e\in E^{\prime }$$
when

$e\in E$ and the vertices of

$e$ are in

$V^{\prime }$.

Induced subgraph (Remove vertices and the corresponding edges) : If the only removed edges are thost that include the removed vertices.

Spanning subgraph (Remove the edges only) : no vertices removed from

$G$, only edges.

Graph Isomorphism

The actual position(embedding) of vertices isn't an essential part of a graph.

Isomorphic Graphs
Two graphs

$(V,E)$ and

$(V^{\prime },E^{\prime })$ are isomorphic if there exists a bijection

$$f:V\to V^{\prime }$$
, such that

$$(v_i,v_j)\in E⟺(f(v_i),f(v_j))\in E^{\prime }$$

Data Structure of Graphs

• Adjacency Matrix :
  $\left[\begin{array}{c}{a}_{ij}\end{array}\right]$, where
  $a_{ij}$ indicates
  $(v_i,v_j)=v_i\to v_j$
  
  $$G=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 1\\ 0& 0& 1& 0\\ 1& 0& 0& 0\end{array}\right)$$
• Edge Dictionary : a list of edges that initiate at that vertex.
  
  $$\{1:[2,4],2:[3,4],3:[3],4:[1]\}$$
• Edge List :
  
  $$[(1,2),(1,4),(2,3),(2,4),(3,3),(4,1)]$$

Connectivity

Let

$v$ and

$w$ be vertices of a directed graph.

• is connected :
  $v$ is connceted to $w $ if there is a path from
  $v$ to
  $w$.
• strongly connceted : if they are connected in both directions.
• connected graph : for each pair of distinct vertices (v,w),
  $v$ is connected to
  $w$ or
  $w$ is connected to
  $v$. (complete directed graph?)
• strongly connected graph : every pair of the connected graph is strongly connected(require both direction). For undirected graph, the edges are all bi-directional, so all connected undirected graph are strongly connected graph.

Maximal Path Theorem

For a graph with

$n$ vertices, the longest path would be

$(n-1)$.

Adjacency Matrix Method

A graph

$G=(V,E)$

The adjacency matrix

$r$ that G defines

$$v_i,v_j\in G,v_{i}r{v}_j⟺(v_i,v_j)\in E$$

$r_{ij}$ indicating if there is an edge connecting

$v_i$ to

$v_j$.

$$r=\left[\begin{array}{c}{r}_{ij}\end{array}\right]$$

$v_i{r}^k{v}_j⟺$ if there exists a path with length

$k$ between

$v_i$ to

$v_j$.

Shortest Path - Breadth-First Search (BFS)

Find the path of two connected vertices.

Search for the vertices that is not found yet in each iteration.

$$\{\begin{array}{l}V=v_1,v_2,\dots ,v_n\\ v_i.found\text{: true if the vertex }{v}_i\text{ is already found during the search}\\ v_i.from\text{: the vertex number that indicates where the vertex }{v}_i\text{ was found(connected) from.}\\ D_k\text{: the depth sets, }k\text{ is the depth(path length) that store the set of vertices that's was found in that specific depth(length)}\end{array}$$

Search for (2, 3), the path from

$v_2$ to

$v_3$

$$\begin{gathered} D_0=[2] \\ {D}_1=[1] \\ {D}_2=[4,5] \\ {D}_3=[6] \\ {D}_4=[3] \end{gathered}$$

Distance Matrix

By using the BFS, we can get the distance between any two vertices. Then construct them into a matrix called distance matrix.

$d_{ij}$ is the distance(depths) from

$v_i$ to

$v_j$

Examine the matix to get

• Eccentricity of a Vertex: The maximum distance from a vertex to all other vertices.
  $e(v)=max(d(v,w))\mid v,w\in V,v\ne w$
• Diameter of a graph : the maximum eccentricty distance of vertices as diameter.
  $d(G)$
• Radius of a Graph : the minimum eccentricty of vertices in the graph.
  $r(G)$
• Center of a Graph : The set of vertices with minimal eccentricity.
  $C(G)=\{v\in V\mid e(v)=r(G)\}$

Eulerian

Goal : Traverse all edges once.

Eulerian Path, Circuit and Graph

• Eulerian Path : a path whose edge list contains each edge of the graph exactly once.
• Eulerian Circuit : when an Eulerain path is a
  circuit.
• Eulerian Graph : when the graph contains an Eulerian circuit.

$$EulerianPath\in EulerianCircuit\in EulerianGraph$$

Euler's Theorem

An undirected graph has an Eulerian path

$⟺$ it's connected and has 0 or 2 vertices with an odd degree. if no vertex has an odd degree, then the graph is Eulerian

A.K.A.

$indeg(v)=outdeg(v)$ except initial (possible with one more outdegree) and terminal (possible with one more indegree) vertices.

Complete Eulerian Graphs

The complete undirected graphs

$K_{2k+1},k\in \mathbb{P}$ are Eulerian, if

$k>1$, then

$K_{2k}$ is not Eulerian.

Since all vertices in the complete graph(

$K_n$) have

$n-1$ edges(degree), therefore when

$n\in Even⟹(n-1)\in Odd$.

Hamilton

Goal : Traverse all vertices once without using the same edge twice.

Hamilton Path, Circuit and Graph

• Hamilton Path : a path whose vertex list contains each vertex of the graph exactly once except when it's a circuit.
• Hamilton Circuit : when an Eulerain path is a
  circuit(terminal=initial).
• Hamilton Graph : when the graph contains an Hamilton circuit.

$$HamiltonPath\in HamiltonCircuit\in HamiltonGraph$$

The

$n$-cube

$n\ge 1,B_n$ :

$n$ bits binary string
The

$n$-cube is the undirected graph with a vertex for each string in

$B_n$ and an edge connecting each pair of strings that differ in exactly on position. The

$n$-cube is normally denoted

$Q_n$.

Analog-to-digital Convertion(ADC) and the Gray Code

Example of Gray Code in

$Q_3$ (aka. The 3-cube).

$G_1=\left(\begin{array}{c}0\\ 1\end{array}\right)$ = The 1-cube.

$G_{n+1}=\left(\begin{array}{c}0G_n\\ 1G_n^r\end{array}\right)$,

$G_n^r$ : is the reverse of

$G_n$

$\therefore G_2=\left(\begin{array}{c}00\\ 01\\ 11\\ 10\end{array}\right)$,

$G_3=\left(\begin{array}{c}000\\ 001\\ 011\\ 010\\ 110\\ 111\\ 101\\ 100\end{array}\right)$

Graph Optimization

Weighted Graph
A weighted graph,

$(V,E,w)$ is a graph

$(V,E)$ with a weight function

$w:E\to R$.

$\mathrm{\forall }e\in E,w(e)$ is the weight of edge

$e$.

The salesman problem

Travers all vertices with minimun cost(sum of weights) of the circuit.

The Closet Neighbor Algorithm

Pick the closet(the most light weighted) edge only. It may not be the optimal answer.

The Unit Square Problem

Control the robot arm to weld on all the vertices in the graph with shortest path(circuit).

The Strip Algotirhm

Networks and the Maximum Flow Problem

Network
A network is a simple weighted directed gram that contains two distinguished vertices called the source and the sink with the properties:

• the indegree of the source and the outdegree of the sink are both zero.
  $indeg(source)=outdeg(sink)=0$
• source is connected to sink.

The Maximum Flow Problem

• the capacity :
  $e_i$
• flow :
  $f:E\to \mathbb{R}$
  • $\mathrm{\forall }{e}_i\in E,0\le f(e_i)\le e_i$ : flow can't be larger than the capacity
  • $\mathrm{\forall }v\in V,v\ne source\wedge v\ne sink,\sum f(x,v)=\sum f(v,y)$
    for all vertices except source and sink, the sum of flow into v (
    $f(x,v)$) is equal to it's sum of flow out of v (
    $f(v,y)$).
  • $\sum f(source,x)=\sum f(y,sink)$
    Flow out of source equals Flow into sink.
• The value of a Flow : the two values flow into the sink and flow out of the source were the same, so the common value is called "the value of the flow". denoted by
  $V(f)$.

Ford and Fulkerson Algorithm (FFA)
9.5.24

Flow Augmenting Path

• $w(e)-f(e)>0$ : flows forward (unused capacity)
• $w(e)-f(e)<0$ : flows in reverse direction

Other Graph Optimization Problems

• The Minimum Spanning Tree Problem
• The Minimum Matching Problem
• The Graph Center Problem
  find the vertex(called a center) of the graph that the distance from the center to every other vertex is as small as possible.

Planarity and Coloring

• Planarity : a graph be drawn in a plane and no edges intersect(cross).
• Coloring : color all vertices and no two vertices that are connected by an edge have the same color. (drawing a map so no two bordering countries are colored the same)

The Kuratowski Reduction Theorem states that if a graph is nonplanar then it “contains” either a

$K_{3,3}$ or a

$K_5$

Euler's Formula

A planar graph devices the plane into one or more regions.

• Two points on the plane lie in the same region if u can draw a curve connecting the two points that does not pass through an edge.

If

$G=(V,E)$ is a connected planar graph with

$r$ regions,

$v$ vertices, and

$e$ edges,

$$v+r-e=2$$

9.6.10 A Bound on Edges of a Planar Graph

If

$G=(V,E)$ is a connected planar graph with

$v$ vertices,

$v\ge 3$ and

$e$ edges,

$$e\le 3v-6$$

Graph Coloring

Graph Coloring
Undirected Graph,

$G=(V,E)$ with a "coloring function"

$f:V\to H,(v_i,v_j)\in E⟹f(v_i)\ne f(v_j)$, and H has the smallest possible cardinality.

The cardinality of

$H$ is called chromatic number of

$G$, denoted by

$\chi (G)$.

The Four-Color Theorem

If

$G$ is a planar graph, then

$\chi (G)\le 4$

The Five-Color Theorem

If

$G$ is a planar graph, then

$\chi (G)\le 5$

tags: math graph