1. Different kinds of graphs

Different kinds of graphs

Graph

Graphs are drawings with dots and (not necessarily straight) lines and arrows.

graph A {
	label="multigraph"
	w
	x--y
	x--x,z
	z--x
}
 
graph B {
	label="simple graph"
	a,b--c
	b--d
	a--b
}
 
digraph C {
	label="directed graph"
	1->1,2,3,4
	2->1,2,4
	3->3
}

graph A {
	graph[nodesep="0.5"]
	node[shape=point]
	w[xlabel="w"]
	x[xlabel="x"]
	y[xlabel="y"]
	x[xlabel="x"]
	label="multigraph"
	w
	x--y
	x--x,z
	z--x
}
 
graph B {
	graph[nodesep="0.5"]
	node[shape=point]
	a[xlabel="a"]
	b[xlabel="b"]
	c[xlabel="c"]
	label="simple graph"
	a,b--c
	b--d
	a--b
}
 
digraph C {
	graph[nodesep="0.5"]
	node[shape=point]
	1[xlabel="1"]
	2[xlabel="2"]
	3[xlabel="3"]
	4[xlabel="4"]
	label="directed graph"
	1->1,2,3,4
	2->1,2,4
	3->3
}

Link to original

Vertices

The dots in a graph are called vertices (or nodes).

Link to original

Edges

The lines or arrows in a graph are called edges.

Link to original

graph {
	node [label="node"]
	A--B [label="  edge"]
}

Type	Edges	Multiple edges	Loop edges
(simple) graph	undirected	no	no
multigraph	undirected	yes	yes
directed graph	directed	no	yes

title: Example 1: Niche overlap graphs in ecology
Competitions between species in an ecosystem can be modelled using a **niche overlap graph**.
 
```graphviz
graph N {
	layout=neato
	splines=true
	
	node [shape=point]
	1 [pos="0,0!" xlabel=Racoon]
	2 [pos="1,0!" xlabel=Hawk]
	3 [pos="2,0!" xlabel=Owl]
	4 [pos="0,-1!" xlabel=Opossum]
	5 [pos="1,-1!" xlabel=Squirrel]
	6 [pos="2,-1!" xlabel=Crow]
	7 [pos="0,-2!" xlabel=Shrew]
	8 [pos="1,-2!" xlabel=Mouse]
	9 [pos="2.4,-2!" xlabel=Woodpecker]
 
	1--2,3,5
	2--3,6
	3--6
	4--5,7,9
	5--6,9
	7--8,9
}

title: Example 2: Road networks
 
```graphviz
graph {
	layout=neato
 
	node[shape=point]
	O[xlabel=Oxford, pos="0,0!"]
	L[xlabel=London, pos="3,0!"]
	C[xlabel=Cambridge, pos="0,-3!"]
	B[xlabel=Brighton, pos="3,-3!"]
	
	O--O,L,L,L,C,C
	L--L,B,B
	C--L,L,B
}

title: Example 3: Representing binary relations
$$
	R = \{ (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,4), (3,3) \}
$$
 
```graphviz
digraph A {
	1->1,2,3,4
	2->1,2,4
	3->3
}

Link to original

2. Basic terminology

Basic terminology: undirected graphs

If there an edge $e$ between vertices $u$ and $v$, we say that:

• $u$ and $v$ are adjacent
• $e$ is incident with $u$ and $v$

Degree (Graphs)

The degree of a vertex is the number of edges incident with it.

Link to original

• Isolated vertex

  An isolated vertex is ==a vertex of degree zero. So an isolated vertex is not adjacent to any vertex==.

  Link to original

• Pendant vertex

  A pendant vertex is ==a vertex of degree one. A pendant vertex is adjacent to exactly one other vertex==.

  Link to original

Handshaking Theorem

Handshaking theorem states that $\text{number of edges}=\frac{\text{sum of the degrees of vertices}}{2}$.

Link to original

title: Example 1
 
$$
	\begin{aligned}
		\text{degree}(a) &= 2 \\
		\text{degree}(b) &= \text{degree}(c) = \text{degree}(f) = 4 \\
		\text{degree}(e) &= 3 \\
		\text{degree}(d) &= 1, \text{so } d \text{ is pendant} \\
		\text{degree}(g) &= 0, \text{so } g \text{ is isolated} \\
	\end{aligned}
$$
 
```graphviz
graph A {
	f,e--b,c
	f--e
	b--c
	a--b,f
	d--c
	g
}

Basic terminology: directed graphs

If there is an edge $e$ going from vertex $u$ to $v$, we say that:

• $u$ is adjacent to $v$
• $u$ is the initial or start vertex of $e$
• $v$ is the terminal or end vertex of $e$

The in-degree of a vertex $v$ is the number of edges with $v$ as their terminal vertex. The out-degree of a vertex $v$ is the number of edges with $v$ as their initial vertex.

Note: A loop at a vertex contributes to both the in and out degrees.

$$\begin{array}{rl}\text{number of edges}& =\text{sum of the in-degrees of vertices}\\ & =\text{sum of the out-degrees of vertices}\end{array}$$

title: Example 2
 
$$
	\begin{aligned}
		\text{in-degree}(a) &= \text{in-degree}(a) = \text{in-degree}(d) = 2 \\
		\text{in-degree}(c) &= \text{in-degree}(e) = 3 \\
		\text{in-degree}(f) &= 0 \\
		\text{out-degree}(a) &= 4 \\
		\text{out-degree}(b) &= 1 \\
		\text{out-degree}(c) &= \text{out-degree}(d) = 2 \\
		\text{out-degree}(e) &= 3 \\
		\text{out-degree}(f) &= 0
	\end{aligned}
$$
 
```graphviz
digraph A {
	a->a,b,c,e
	b->d
	c->c
	d->e,c
	e->a,d,e
	f
}

Link to original

3. Adjacency Matrix

Adjacency Matrix

To build an adjacency matrix: ?

1. List the vertices in some order horizontally left to right.
2. Then using the same order, list them vertically top to bottom.
3. The entry in the $i^{\text{th}}$ row and the $j^{\text{th}}$ column is the number of edges going from vertex $i$ to vertex $j$.

If the graph is undirected, then the number in the $i^{\text{th}}$ row and the $j^{\text{th}}$ column $=$ the number in the $j^{\text{th}}$ row and the $i^{\text{th}}$ column.

title: Example 1
$$
\begin{array}{c|ccc}
	& x & y & w & z \\
	\hline x & 1 & 1 & 0 & 2 \\
	\hline y & 1 & 0 & 0 & 0 \\
	\hline w & 0 & 0 & 0 & 0 \\
	\hline z & 2 & 0 & 0 & 0 \\
\end{array}
\hspace{48px}
\begin{array}{c|ccc}
	& y & x & w & z \\
	\hline y & 0 & 1 & 0 & 0 \\
	\hline x & 1 & 1 & 0 & 2 \\
	\hline w & 0 & 0 & 0 & 0 \\
	\hline z & 2 & 0 & 0 & 0 \\
\end{array}
$$
 
```graphviz
graph G {
	w
	x--x,y,z,z
}

title: Example 2
$$
\begin{array}{c|ccc}
	& a & b & c & d \\
	\hline a & 1 & 1 & 1 & 1 \\
	\hline b & 1 & 1 & 0 & 1 \\
	\hline c & 0 & 0 & 1 & 0 \\
	\hline d & 0 & 0 & 0 & 0 \\
\end{array}
\hspace{48px}
\begin{array}{c|ccc}
	& b & c & d & a \\
	\hline b & 1 & 0 & 1 & 1 \\
	\hline c & 0 & 1 & 0 & 0 \\
	\hline d & 0 & 0 & 0 & 0 \\
	\hline a & 1 & 1 & 1 & 1 \\
\end{array}
$$
 
```graphviz
digraph G {
	a->a,b,c,d
	b->a,b,d
	c->c
}

Link to original

4. Paths in simple graphs

Paths in simple graphs

Path

A path $p=⟨v_1,v_2,\dots ,v_k,v_{k+1}⟩$ is a sequence of vertices where $(v_i,v_{i+1})$ is an edge for each $i=1,2,\dots ,k$.

Link to original

Length (path)

The length of a path is the number of edges in it.

Link to original

Simple path

A path is called simple if it does not contain the same edge twice.

Link to original

Hamiltonian path

A Hamiltonian path is a [[Simple path|simple path]] passing through every vertex exactly once.

Link to original

title: Example 1
 
$$
(a,b,c,f,b,e) \text{ is a simple path in } G \text{ of length } 5
$$
 
```graphviz
graph G {
	a--d
	a--e
	d--c
	d--e
	e--f
	
	edge [colorscheme=orrd9]
	a--b [color=9 penwidth=3]
	b--c [color=8 penwidth=3]
	c--f [color=7 penwidth=3]
	f--b [color=6 penwidth=3]
	b--e [color=5 penwidth=3]
}

title: Example 2
 
$$
(a,b,c,d,a,b) \text{ is a path in } G \text{ of length } 5 \text{ but it is not simple as it contains } a-b \text{ twice}
$$
 
```graphviz
graph G {
	a--e
	d--c
	e--f
	b--c
	c--f
	f--b
	
	edge [colorscheme=greens9]
	a--b [color=9 penwidth=5]
	b--e [color=8 penwidth=3]
	d--e [color=7 penwidth=3]
	a--d [color=6 penwidth=3]
}

title: Example 3
 
$$
(d,a,e,b,f,c) \text{ is a Hamiltonian path in } G
$$
 
```graphviz
graph G {
	d--c
	e--f
	b--c
	a--b
	d--e
	
	edge [colorscheme=blues9]
	a--d [color=9 penwidth=3]
	a--e [color=8 penwidth=3]
	b--e [color=7 penwidth=3]
	f--b [color=6 penwidth=3]
	c--f [color=5 penwidth=3]
}

Link to original

5. Cycles in simple graphs

Cycles in simple graphs

Cycle

A cycle is a path beginning and ending with the same vertex.

Link to original

Length (cycle)

The length of a cycle is the number of edges in it.

Link to original

Simple cycle

A cycle is called simple if it does not contain the same edge twice.

Link to original

Hamiltonian cycle

A Hamiltonian cycle is a [[Simple cycle|simple cycle]] passing through every vertex exactly once.

Link to original

title: Example 1
 
$$
(a,d,c,b,a) \text{ is a simple cycle in } G \text{ of length } 4
$$
 
```graphviz
graph G {	
	a--e
	b--e
	b--f
	c--f
	d--e
	e--f
	
	a--d [penwidth=3]
	c--d [penwidth=3]
	b--c [penwidth=3]
	b--a [penwidth=3]
}

title: Example 1
 
$$
(b,e,d,a,e,b) \text{ is a cycle in } G \text{ of length } 5 \text{ but it is not simple}
$$
 
```graphviz
graph G {	
	a--e [penwidth=3]
	b--e [penwidth=6]
	b--f
	c--f
	d--e [penwidth=3]
	e--f
	a--d [penwidth=3]
	c--d
	b--c
	b--a
}

title: Example 1
 
$$
(c,f,e,d,a,b,c) \text{ is a Hamiltonian cycle in } G
$$
 
```graphviz
graph G {	
	a--e
	b--e
	b--f
	c--f [penwidth=3]
	d--e [penwidth=3]
	e--f [penwidth=3]
	a--d [penwidth=3]
	c--d
	b--c [penwidth=3]
	b--a [penwidth=3]
}

Link to original

6. Special graphs, subgraphs, connectedness

Special graphs

Complete graph

The complete graph on $n$ vertices ($n$-clique), denoted by $\boxed{K_n}$, is the simple graph that contains an edge between each pair of distinct vertices.

Link to original

Draw the graphs of $K_3$, $K_5$, and $K_6$. ?

graph 3 {
	label="K₃"
	layout=circo
	node [shape=point]
	1--2,3
	2--3
}
 
graph 5 {
	label="K₅"
	layout=circo
	node [shape=point]
	1--2,3,4,5
	2--3,4,5
	3--4,5
	4--5
}
 
graph 6 {
	label="K₆"
	layout=circo
	node [shape=point]
	1--2,3,4,5,6
	2--3,4,5,6
	3--4,5,6
	4--5,6
	5--6
}

Complete cycle

The complete cycle(??), $n$-cycle is denoted by $\boxed{C_n}$, for $n \ge 4$.

Link to original

graph 4 {
	label="C₄"
	layout=circo
	node [shape=point]
	1--2
	2--3
	3--4
	4--1
}
 
graph 5 {
	label="C₅"
	layout=circo
	node [shape=point]
	1--2
	2--3
	3--4
	4--5
	5--1
}

Subgraphs

When edges and vertices are removed from a graph, without removing end-points of any remaining edges, a smaller graph is obtained.

Such a graph is called a subgraph of the original graph.

title: Subgraphs of $K_6$
 
```graphviz
graph A {
	layout=circo
	node [shape=point]
	1--3,4,5,6
	2--3,4,5,6
	3--4,5,6
	4--5,6
	5--6
}
 
graph B {
	layout=circo
	node [shape=point]
	1--2,3
	2--3,4
	3--4
}
 
graph B {
	layout=circo
	node [shape=point]
	1--2,3
	2--3
}

Connected graphs

A simple graph is called connected if there is a path between every pair of distinct vertices.

graph G {
	node [shape=point]
	
	subgraph cluster_G {
		label="connected"
		a--b,c,d
		b--c
		d,h--e
		g--h,f
	}
	
	subgraph cluster_H {
		label="not connected"
		1--2,3
		2--3
		4--5
		6--7,8
	}
}

A connected component of a graph is a maximal connected subgraph.

• If a graph is connected, then it has only 1 connected component, itself.

• But if it is not connected, then it can have more:

  graph 1 {
    layout=circo
    node [shape=point]
    a [xlabel="a"]
    b [xlabel="b"]
    c [xlabel="c"]
  	label="G₁"
    a--b,c
    b--c
  }
   
  graph 2 {
    layout=circo
    node [shape=point]
    d [xlabel="d"]
    e [xlabel="e"]
  	label="G₂"
    d--e
  }
   
  graph 3 {
    layout=circo
    node [shape=point]
    g [xlabel="g"]
    h [xlabel="h"]
    f [xlabel="f"]
  	label="G₃"
    g--h,f
  }

  are the three connected components of:

  graph G {
    node [shape=point]
    	
  	subgraph cluster_H {
    	a [xlabel="a"]
    	b [xlabel="b"]
    	c [xlabel="c"]
    	d [xlabel="d"]
    	e [xlabel="e"]
    	f [xlabel="f"]
    	g [xlabel="g"]
    	h [xlabel="h"]
    	label="G₁"
    	a--b,c
    	b--c
    	d--e
    	g--h,f
     }
  }

Link to original

7-10. Graph isomorphism

Graph isomorphism

Isomorphic

Graphs $G$ and $H$ are isomorphic if there is an isomorphism between them: A function $f$ from the vertices of $G$ to the vertices of $H$ such that:

• $f$ is a bijection (function)

• $f$ takes edges to edges:

  For all vertices $x,y$ in $G$, if	Edges-to-edges (1) graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"];y--x} Link to original	then	Edges-to-edges (2) graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"];y--x} Link to original	in $H$.

• $f$ takes non-edges to non-edges:

  For all vertices $x,y$ in $G$, if	Non-edges-to-non-edges (1) graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"]} Link to original	then	Non-edges-to-non-edges (2) graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"]} Link to original	in $H$.

Link to original

title: Example
 
![](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%206.%20Graphs/Diagrams/Pasted%20image%2020211103154548.png)
 
The function $f$ defined by taking
 
$$
	f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E
$$
 
is an isomorphism, showing that graphs $G$ and $H$ are isomorphic.

Isomorphic or not?

We need to determine whether two graphs, say $G$ and $H$ are isomorphic or not.

$$\begin{array}{rl}\text{isomorphic}& =\text{there is an isomorphism}\\ \text{not isomorphic}& =\text{there is no isomorphism}\end{array}$$

• We can try all possible functions from $G$ to $H$, and check whether any of them is an isomorphism.
• But this might take a lot of time: there are $4^5=1024$ possible functions even for this example.

Invariants

Invariant

A property $\mathcal{P}$ of graphs is called an invariant if ==it is ‘preserved under isomorphisms’: If $G$ and $H$ are isomorphic graphs, and $G$ has property $\mathcal{P}$, then $H$ has property $\mathcal{P}$ as well==.

Link to original

title: Example 1: "Having $5$ vertices" is an invariant
If $G$ and $H$ are isomorphic graphs, and $G$ has $5$ vertices, then $H$ has $5$ vertices too.
 
This is because, if $G$ and $H$ are isomorphic, then there is an isomorphism $f$ between them.
 
- $f$ is a [[Bijection (function)|bijection (function)]] from the vertices of $G$ (domain) to the vertices of $H$ (codomain).
  ![[Bijection f between graphs]]
- As $f$ is one-to-one, $H$ has at least $5$ vertices.
- As $f$ is onto, $H$ has at most $5$ vertices.

title: Example 2: Determine whether $G$ and $H$ are isomorphic or not
 
We've just seen that the property "having $5$ vertices" is an invariant.
This property holds for $G$, but not for $H$. Therefore, $G$ and $H$ are not isomorphic.
 
```graphviz
graph G {
	label=G
	e--d,a
	d--a,c
	b--a,c
}
 
graph H {
	label=H
	w--z,x
	y--x,z
}

title: Example 3: Determine whether $G$ and $G'$ are isomorphic or not
 
In this case, we say "having a vertex of degree $3$" is an **invariant**.
 
This property holds in $G$ (e.g. $\text{degree}(a) = 3$), but does not hold in $G'$, showing that $G$ and $G'$ are not isomorphic.
 
```graphviz
graph G {
	label=G
	b--a,c
	d--a,c,e,f
	c--e
	a--e
	c--f
}
 
graph H {
	label="G'"
	g--h,i,k,j
	k--i,j,l
	j--l,i
	i--h
}

title: Example 4: Determine whether $G$ and $G'$ are isomorphic or not
 
The function $f$ defined by taking
 
$$
	f(a) = 4, f(b) = 2, f(c) = 3, f(d) = 1, f(e) = 5
$$
 
is an isomorphism (because $f$ is a bijection, takes edges to edges and non-edges to non-edges). This shows that graphs $G$ and $H$ are isomorphic.
 
```graphviz
graph G {
	label=G
	d--e,a,b
	e--c,a
	a--c,b
}
 
graph H {
	label="H"
	1--2,4,5
	2--4
	3--4,5
	4--5
}

title: Always keep in mind that if $h$ is an isomorphism between graphs $G$ and $H$, then for every vertex $x$ in $G$, the degrees of $x$ and $h(x)$ must be the same.

How to decide?

You are given a task to determine whether two graphs $G$ and $H$ are isomorphic or not.

It is not known:

• whether the problem is solvable in polynomial time we don’t know whether there is a method to check isomorphism without trying all functions
• whether the problem is definitely NOT solvable in polynomial time for many other problems, there are known proofs

We can try to determine in parallel whether:

• We can describe a bijection between the vertices of $G$ and $HG$ that ‘takes’ edges to edges, non-edges to non-edges. If we succeed, answer is yes.
• We can find an invariant $\mathcal{P}$ and show that $G$ has $\mathcal{P}$ but $H$ doesn’t, or the other way around. If we succeed, answer is no.

Link to original