[Discrete Mathematics] lecture 8 - Graphs

Introduction

Graph is a particular class of discrete structure for representing relations. We deal with various types of graphs, their representations and trees.

Graphs

Definition 1
A simple graph $G = \left<V,E\right>$ consists of
‣ a set $V$ of vertices(=nodes)
‣ a set $E$ of edges(=arcs, links), which are unordered pairs of distinct elements in $V$.

 

Definition 2
A multigraph is a graph with multiple edges. Formally defined as:
A multigraph $G =  \left< V, E, f \right>$ consists of a set $V$ of vertices, a set $E$ of edges and a function $f : E \rightarrow \left\{(u, v) \: | \:u, v \in V \wedge u \neq v \right\}$, which maps each edge to a pair of vertices. 

Definition 3
A pseudograph is a graph with loops.
A pseudograph $G =  \left< V, E, f \right>$  where $f : E \rightarrow V \times V$. Edge $e \in E$ is a loop if $f (e) = (u, u)$.  

Definition 4
A directed graph is a graph with direction.
A directed graph $G =  \left< V, E, f \right>$  consists of a set of vertices $V$ and a binary relation $E$ on $V$.

Definition 5
A directed multigraph is a graph with direction and multiple edges.
A directed graph $G =  \left< V, E, f \right>$  consists of a set of vertices $V$, a set of $E$ of edges, and a function $f : E \rightarrow V \times V$ . 

Definition 6 (from Relations)
Consider a directed graph $G = \left<V, E\right>$ where $V$ is a set of vertices and $E$ is a set of edges.
‣ A walk is a sequence of edges of $G$
‣ A length of a walk is the number of edges in the walk.
‣ A trail is a walk in which all edges are distinct
‣ A path is a trail in which all vertices are distinct
‣ A cycle is a walk that begins and ends at the same vertex.
‣ A loop is a cycle of length 1.
‣ A sling is a cycle of length 2.

 

A brief summary

Term	Edge	Multiple Edges	Self Loops
Simple graph	Undirected	X	X
Multigraph	Undirected	O	X
Pseudograph	Undirected	O	O
Directed graph	Directed	X	O
Directed multigraph	Directed	O	O

Simple properties

$ \text{deg} $  denotes the number of incident edges.

$ \text{deg} ^+$ is the number of edges going from a vertex.

$ \text{deg} ^-$ is the number of edges going into a vertex.

Definition 7
Let $G$ be a directed graph where $v$ is a vertex of $G$.
‣ The in-degree of $v$, denoted $\deg^-(v)$, is the number of edges coming to $v$.
‣ The out-degree of $v$, denoted $\deg^+(v)$, is the number of edges going from $v$.
‣ The degree of $v$, denoted $\deg(v) = \deg^-(v) + \deg^+(v)$, is the sum of $v$’s in-degree and out-degree. 

Theorem 1
Let $G= \left<V, E\right>$ be an undirected graph. Then,
$$\sum_{v \in V} \text{deg}(v) = 2 |E|$$.

Corollary 2
Any undirected graph has an even number of vertices of odd degree.

Theorem 3
Let $G= \left<V, E\right>$ be a directed graph. Then
$$ \sum_{v \in V} \text{deg}^-(v ) = \sum_{v \in V} \text{deg}^+(v ) =\frac{1}{2} \sum_{v \in V} \text{deg}^(v ) = |E|$$.

Special graphs

Definition 8
For any $n \in \mathbb{N}$, a complete graph on $n$ vertices, $K_n$, is a simple graph with $n$ nodes in which every node is adjacent to every other node. That is, for all $u, v \in V$, if $u \ne v$, then $(u, v) \in E$.

Cycle graph

Definition 9
For any $n \geq 3$, a cycle on $n$ vertices, $C_n$, is a simple graph where the set of vertices is $ V = \{v_1, v_2, \dots, v_n\} $ and the set of edges is $ E = \{(v_1, v_2), (v_2, v_3), \dots, (v_{n-1}, v_n), (v_n, v_1)\}. $

Wheel graphs

Definition 10
For any $n \geq 3$, a wheel, $W_n$, is a simple graph obtained by taking the cycle $C_n$ and adding one extra vertex $v_{\text{hub}}$ and $n$ extra edges: $ \{(v_{\text{hub}}, v_1), (v_{\text{hub}}, v_2), \dots, (v_{\text{hub}}, v_n)\}. $

Hyper cube $Q_5$

Definition 11
For any $n \in \mathbb{N}$, the hypercube $Q_n$ is a simple graph consisting of two copies of $Q_{n-1}$ connected together at corresponding nodes. The base case is: $ Q_0 \text{ has one node.} $

Biparite graph

Definition 12
A simple graph $G$ is called bipartite if its vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge in the graph connects a vertex in $V_1$ and a vertex in $V_2$. That is, no edge in $G$ connects either two vertices in $V_1$ or two vertices in $V_2$.

Complete biparite graph

Definition 13
Let $m, n$ be positive integers. The complete bipartite graph $K_{m,n}$ is the graph whose vertex set can be partitioned as $V = V_1 \cup V_2$ such that: 
‣ $|V_1| = m$ and $|V_2| = n$
‣ $\forall u \in V_1$ and $\forall v \in V_2$, there is an edge between $u$ and $v$
‣ No edge has both its endpoints in $V_1$ or both in $V_2$ 

Definition 14
A subgraph of a graph $G = (V, E)$ is a graph $H = (W, F)$ where $W \subseteq V$ and $F \subseteq E$. 

Definition 15
The union $G_1 \cup G_2$ of two simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ is the simple graph: $$ G_1 \cup G_2 = (V_1 \cup V_2,\ E_1 \cup E_2). $$

Representing Graphs

This part will be summarized using example for this graph:

1. Adjacency lists
   

   vertex	adjacent vertices
   a	b c
   b	a c e f
   c	a b f
   d
   e	b
   f	b c

2. Adjacency matrices
   

   	a	b	c	d	e	f
   a	0	1	1	0	0	0
   b	1	0	1	0	1	1
   c	1	1	0	0	0	1
   d	0	0	0	0	0	0
   e	0	1	0	0	0	0
   f	0	1	1	0	0	0

3. Incidence matrice  (this is for multigraph)

   	a	b	c	d	e	f
   AB	1	1	0	0	0	0
   AC	1	0	1	0	0	0
   BC	0	1	1	0	0	0
   BF	0	1	0	0	0	1
   BE	0	1	0	0	1	0
   CF	0	0	1	0	0	1

Definition 16
Simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are \textbf{isomorphic} if there exists a bijection $f : V_1 \to V_2$ such that $ \forall u, v \in V_1,\quad (u, v) \in E_1 \iff \big(f(u), f(v)\big) \in E_2. $

Isomorphic garphs

→ Difficult to identify.

Check these conditions first:

• $|V_1|=|V_2|$ and $|E_1|=|E_2|$
• The number of vertices with $k$ degree is the same in both graphs
• For every proper subgraph $g$ of one graph, there is a proper subgraph of the other graph that is isomorphic to $g$. (Not very useful though)

Connectedness

Definition 17
An undirected graph is connected if and only if there is a path between every pair of distinct vertices in the graph.

 

Definition 18
A directed graph is strongly connected if there is a directed path from $u to $v$ for any vertices $u$ and $v$ (i.e., mutually reachable).
It is weakly connected if the underlying undirected graph (i.e., with edge directions removed) is connected.

 

Trees

A tree is an acyclic directed graph such that
‣ there is exactly one node, called the root of the tree, which has in-degree 0.
‣ every node other than the root has indegree 1.
‣ for every node of the tree, there is a directed path from the root to the node, which means a weekly connected graph.

Definition 20
‣ A tree is called an m-ary tree if every internal node has no more than m children.
‣ A tree is called a full m-ary tree if every internal node has exactly $m$ children.
‣  An m-ary tree with $m = 2$ is called a binary tree.

Theorem 4
A tree with $n$ nodes has $n-1$ edges.

Theorem 5
A full m-ary tree with $k$ internal nodes contain $m \times k +1$ nodes