{%hackmd @RintarouTW/About %}

# Graph Theory

graph {graph [rankdir=LR];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
 a--b--c--b
 b--d--b
 a--c
 a--d
}

## Simple Directed Graph

:::info
$$
\cases{
V:Vertices\\
E:Edges \in V\times V\\
}
$$

**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

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

## Undirected Graph

:::info
The E(edges) are undirected, $\forall e=(a,b)\in E, (b,a)\in E$
:::

Complete Graph ($K_n$)
:::info
each pair of distinct vertices are directly connected to one another.
$$
\forall v_i,v_j\in V, v_i\neq v_j, (v_i, v_j) \in E
$$

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

digraph {graph [rankdir=TB];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
 A->B->C->A,D
 A->D->B
}

:::

Single-elimination tournament graph (tree-like):

digraph {graph [rankdir=TB];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
 A->B,D
 B->C
}

- 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

:::info
let $G=(V,E)$ be a graph of any kind:
- directed / undirected
- multigraph / unidirected

$G'=(V', E')$ is a subgraph of $G$,
$$\iff V'\subseteq V\land e\in E'$$
when $e\in E$ and the vertices of $e$ are in $V'$.
:::

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.

:::info
Isomorphic Graphs
Two graphs $(V,E)$ and $(V',E')$ are isomorphic if there exists a bijection
$$f:V\rightarrow V'$$
, such that
$$(v_i, v_j)\in E\iff (f(v_i), f(v_j))\in E'$$
:::

## Data Structure of Graphs

digraph {graph [rankdir=TB];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
1->2,4
2->3,4
3->3
4->1
}

- Adjacency Matrix : $\bmatrix{a_{ij}}$, where $a_{ij}$ indicates $(v_i,v_j) = v_i\rightarrow v_j$
$$
G=\pmatrix{
0&1&0&1\\
0&0&1&1\\
0&0&1&0\\
1&0&0&0\\
}
$$
- 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

:::info
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_irv_j\iff (v_i,v_j) \in E$$
**$r_{ij}$** indicating if there is an edge connecting $v_i$ to $v_j$.

$$
r=\bmatrix{r_{ij}}
$$

:::info
$v_ir^kv_j\iff$ 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.

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

digraph {graph [rankdir=TB];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
1->4,5
2->1
3->1,4,5
4->2,6
5->2,6
6->1
}

Search for (2, 3), the path from $v_2$ to $v_3$
$$
D_0 = [2]\\
D_1 = [1]\\
D_2 = [4,5]\\
D_3 = [6]\\
D_4 = [3]
$$

### 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\neq 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

:::info
Goal : Traverse all edges once.
:::

<img src="https://i.imgur.com/C1nb1Vn.png" style="filter:invert(.9)"/><br>

### 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.

$$
Eulerian\ Path \in Eulerian\ Circuit \in Eulerian\ Graph
$$

### Euler's Theorem

:::info
An undirected graph has an Eulerian path$\iff$ 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

:::info
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\implies (n-1) \in Odd$.
:::

## Hamilton

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

<img src="https://i.imgur.com/1IeD3Ze.png" style="filter:invert(.9)"/><br>

### 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.

$$
Hamilton\ Path \in Hamilton\ Circuit \in Hamilton\ Graph
$$

#### The $n$-cube

:::info
$n\geq 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

graph {graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
000--001,010,100
001--011,101
010--011,110
100--101,110
011,110,101--111
}

Example of Gray Code in $Q_3$ (aka. The 3-cube).

$G_1 = \pmatrix{0\\1}$ = The 1-cube.
$G_{n+1} = \pmatrix{\color{red}{0}G_n\\\color{white}{1}G_n^r}$, $G_n^r$ : is the reverse of $G_n$

$\therefore G_2 = \pmatrix{\color{red}{0}0\\\color{red}{0}1\\\color{white}{1}1\\\color{white}{1}0}$, $G_3 = \pmatrix{\color{red}{0}00\\\color{red}{0}01\\\color{red}{0}11\\\color{red}{0}10\\\color{white}{1}10\\\color{white}{1}11\\\color{white}{1}01\\\color{white}{1}00}$

## Graph Optimization

:::info
Weighted Graph
A weighted graph, $(V,E,w)$ is a graph $(V,E)$ with a weight function $w:E\rightarrow R$.
$\forall e\in E, w(e)$ is the weight of edge $e$.
:::

### The salesman problem

:::info
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

:::info
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

:::info
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.
:::

<img src="https://i.imgur.com/xCMcxaW.png" style="filter:invert(.9)"/><br>

The Maximum Flow Problem

- **the capacity** : $e_i$
- **flow** : $f:E\rightarrow \mathbb{R}$
- $\forall e_i\in E, 0\leq f(e_i)\leq e_i$ : flow can't be larger than the capacity
- $\forall v\in V,v\neq source\land v\neq 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

:::info
Flow Augmenting Path
- $w(e)-f(e) \gt 0$ : flows forward (unused capacity)
- $w(e)-f(e) \lt 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.

:::info
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

:::info
If $G=(V,E)$ is a connected planar graph with $v$ vertices, $v\geq 3$ and $e$ edges,
$$
e\leq 3v-6
$$
:::

### Graph Coloring

<img src="https://i.imgur.com/vKVAYyo.png" style="filter:invert(.9)"/><br>

:::info
Graph Coloring
Undirected Graph, $G=(V,E)$ with a "coloring function" $f:V\rightarrow H, (v_i,v_j)\in E\implies f(v_i)\neq 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)\leq 4$

The Five-Color Theorem

If $G$ is a planar graph, then $\chi(G)\leq 5$

###### tags: `math` `graph`