Graphs

Graphs

---

Basic Terminology

directed graph $G=(V,E)$

- V : set of vertices

- E : binary relation on V, called edges

 - edge(a,b) is incident with vertices a and b, incident from a, incident into b

 - a is initial vertex and b is terminal vertex of edge(a,b)

loop : edge that is incident from and into same vertex

adjacent : two vertices joined by an edge. a is adjacent to b and b is adjecent from a for edge(a,b)

isolated : a vertex that had no edge incident with it

 

undirected graph $G=(V,E)$

isomorphic : two graphs that have one-to-one correspondence between their vertices and edges

 

subgraph $G'=(V',E')$ : $E'\subseteq E$, $V'\subseteq V$ and $E'$ are incident only with $V'$

spanning subgraph : subgraph which is $V'=V$

complement of subgraph $G''=(V'',E'')$ : $E''=E-E'$ and $V''$ contains only vertices with $E''$ are incident

 

undirected complete graph of n vertices $K_n$ : there exist edges between all pairs of distinct vertices

complement of graph G : complement to respecet to $K_n$, denoted $\bar{G}$

directed complete graph of n vertices : there is exactly one arrow between each pair of distinct vertices

---

Multigraphs and Weighted graphs

directed multigraph $G=(V,E)$ : V : set of vertices, E : multiset of ordered pairs from VxV

undirected multigraph $G=(V,E)$ : defined similar manner

 

weighted graph $(V,E,f,g)$, $(V,E,f)$, or $(V,E,g)$

- V : set of vertices

- E : set of edges

- f : function whose domain is V, assignment of weights to vertices

- g : function whose domain is E, assignment of weights to edges

---

Paths and Circuits

path : sequene of edges $(e_{i_1},e_{i_2},\cdots ,e_{i_k})$

- terminal vertox of e_{ij} coincides with initial vertex of e_{i(j+1)} for $1\leq j\leq k-1$

simple path : path does not include same edge twice

elementary path : path does not meet same vertex

 

circuit : path that terminal vertex of $e_{ik}$ coincides with initail vertex of $e_{i1}$

simple circuit : circuit does not include same edge twice

elementary circuit : circuit does not meet same vertex

 

we can also represent path or circuit by sequence of vertices

 

Theorem 5.1

In a graph with n vertices, if there is a path from $v_1$ to $v_2$, then there is a path of no more than n-1 edges from $v_1$ to $v_2$

proof)

Suppose there is path from $v_1$ to $v_2$. Let ($v_1, \cdots , v_i, \cdots , v_2$) be the path.

If there are L edges in path, there are L+1 edges in sequence.

For L larger than n-1, there must be vertex $v_k$ appears more than once in the sequence (by pigeonhole principle)

We can delete edges between $v_k$ to $v_k$ so that path has n-1 or fewer edges. (Contradicts)

 

For undirected graph, connected there is path between every two vertices, disconnected otherwise

For directed graph, connected there is path between every two vertices ignoring directions, disconnected otherwise

 

strongly connected : every two vertices a and b has path from a to b and from b to a

---

Shortest Paths in Weighted Graphs

length of weighted graph : sum of weights of edges in paht

shortest path algorithm : Dijkstra's Algorithm (Dynamic Programming)

 

Let T be a subset of V with $a\notin T$. Let P denote subset of V-T.

For each vertex $t\in T$ let I(t) denote length of shortest path among all paths from a to t that do not include any other vertex in T. We call I(t) the index of t with respect to P

 

Among all vertices in T, let $t_1$ be a smallest index vertex. Claim that shortest distance a to $t_1$ is equal to I($t_1$)

proof)

Assume there is path from a to $t_1$ whose length is less than I($t_1$).

Path must include one or more vertices in T-{$t_1$}.

Let $t_2$ be the first vertex in T-{$t_1$} we encounter this so that I($t_2$) is less than I($t_1$). Contradiction

 

Suppose for every vertex $p\in P$, there is shortest path from a to p which includes only vertices in P.

Assume that for each vertex $t\in T$ already computed its index with respect to P, I(t).

Let x be a vertex in T. Let P' be $P\cup {x}$ and T' be $T-{x}$. Let I'(t) denote index of vertex in T' with respect to P'

We claim that

$I'(t) = min[I(t), I(x) + w(x,t)]$

proof)

1. A path includes neither vertex in T' nor vertex x : index of t with respect to P' is I(t)

2. A path consisting of path from a to x that includes no vertex in T, followed by edge {x,t} : index of t with respect to P' is I(x) + w(x,t)

3. Do not consider path from a to x followed by path from x to y and y to t since a to x, x->y is not the shortest path from a to y

 

Procedure of Dijkstra, the shortest distance from a to any vertex in G

1. Let P={a} and T=V-{a}. For every vertex $t\in T$, let I(t) = w(a,t)

2. Select vertex in T that has smallest index with respect to P. Let x denote this vertex

3. If x is vertex we wish to reach from a, stop. Else, let P'=P$\cup${x} and T'=T-{x}.

  For every vertex in T', compute its index with respect to P'

4. repeat 2, 3 using P' as P and T' as T

---

Eulerian Paths and Circuits

Königsberg bridge problem

 

Eulerian path : path traverses each of edges once and only once 

Eulerian circuit : circuit traverses each of edges once and only once 

 

Lemma : In any graph, there is an even number of vertices of odd degree

 

Theorem 5.2

An undirected graph possesses an eulerian path if and only if it is connected and has either zero or two vertices of odd degree

proof)

(=>)Suppose the graph possesses an eulerian path. Graph must be connected is obvious.

Everytime the path meets vertex, path pass through two edges both incident from and into the vertex.

If two distinct vertices are two end of the eulerian path, there are only two vertices with odd degree.

If not, all vertices have even degree, and eulerian path becomes eulerian circuit.

(<=)Suppose we construct eulerian path starting at vertex that has odd degree.

For a vertex of even degree, whenever the path enters, it should always leave the vertex.

Therefore, when the construction ends, we must have reached the other vertex of odd degree

 

corollary 5.2.1

An undirected graph possesses an eulerian circuit if and only if it is connected and all the vertices have even degree

 

Theorem 5.3

- A directed graph possesses an eulerian circuit, incoming degree is equal to outgoing degree for all vertices

- A directed graph possesses an eulerian circuit, incoming degree is equal to outgoing degree for all vertices except two distinct vertices. For these two vertices, one has one larger outgoing degree and another has one larger incoming degree

---

Hamiltonian Paths and Circuits

hamiltonian path : path traverses each of vertices once and only once 

hamiltonian circuit : circuit traverses each of vertices once and only once 

 

complete graph $K_n$ $(n \geq 3)$ is Hamiltonian graph

complete bipartite graph $K_{m,n}$ is Hamiltonian if and only if $m=n>1$

 

Theorem 5.4

Let G be a linear graph of n vertices. If the sum of degrees for each pair of vertices in G is n-1 or larger, there exists a hamiltonian path in G

---

Traveling Salesperson Probelm (TSP)

TSP : find a hamiltoonian circuit of minimum length in weighted graph

 

Nearest-neighbor method

1. start with any vertex, find closest vertex and form initail path of one edge

2. Let x denote latest vertex added to path. Among all vertices not in path, pick one closest to x and add to path edges from x to the vertex. Repeat this until all vertices in G are included in path

3. Form a circuit by adding path between final vertex and starting vertex

 

Theorem 5.6

Let $d$ be a total distance of hamiltonian circuit of nearest-neighbor method

Let $d_0$ be a total distance of hamiltonian circuit of minimum hamiltonian circuit

${d \over d_0} \leq log \left \lceil n \over 2 \right \rceil + {1\over2}$

---

Planar Graphs

planar graph : graph that can be drawn on a plane with no edges cross one another

region : face of graph

- finite region : if the region is finite

- infinite region : if the region is infinite

- planar graph has exactly one infinite region

 

Theorem 5.7

For any connected planar graph

$v-e+r=2$ (Euler's formular for planar graphs, v : vertices, e : edges, r : region)

proof) by induction on the number of edges

For two graphs with single edge (simple and loop) is satisfied

Assume equation is satisfied in all graphs with n-1 edges

Lets prove equiation is satisfied in all graphs with n edges. Let G be a connected graph with n edges.

- If G has vertex of degree 1, removal of this vertex with the edge is G' and it is satisfied.

 Additional vertex and edge is both 1 and doesn't affact the equation

- If G has no vertex of degree 1, removal of any edge in boundary is G' and it is satisfied.

 Additional edge and region is both 1 and doesn't affact the equation

 

Lemma

In any connected linear planar graph that has no loops and paralles,

$e\leq 3v-6$ (necessary not sufficient condition)

proof)

Each finite region has three or more edges. Thus, total count is larger than or equal to 3r.

Edge is in boundaries of at most two regions, Thus, total count is less than or equal to 2e

Therefore, $2e\geq 3r$

Using Euler's formula, $v-e+2e/3\geq 2$

$3v-6\geq e$

 

planarity is not affacted in the following cases

- edge is divided into two edges by insertion of new vertex of degree 2

- two edges that are incident with a vertex of degree 2 are combined as a single edge by remove that vertex

 

isomorphic to within vertices of degree 2 : two graphs that are isomorphic with removing all vertices of degree 2

 

Theorem 5.8 (Kuratowski)

graph is planar if and only if it does not contain any subgraph that is isomorphic to within vertices of degree 2

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.