CITS2200 - Lecture 19

← Back to Home

CITS2200 - Lecture 18
Graphs - Slides

Graphs

• A graph is a pair $(V,E)$ where:
  • $V$ is a set of nodes (called vertices)
  • $E$ is a collection of pairs of vertices (called edges)
• Both vertices and edges can store data

Terminology

• Endpoint $-$ two vertices an edge connects
• Adjacent $-$ two vertices sharing an edge
• Degree $-$ number of edges touching a vertex
• Parallel edges $-$ two edges with the same endpoints
• Self-loop $-$ edge where both endpoints are the same vertex

Applications

• Electronic circuits (e.g. PCBs)
• Transportation networks
• Computer networks (e.g. local area network, internet, etc.)
• Databases

---

Edge Types

• Directed edge $-$ ordered pair of vertices $(u,v)$

  • $u$ → origin
  • $v$ → destination

• Undirected edge $-$ unordered pair of vertices

  

A graph where all edges are directed is called a directed graph
A graph where all edges are undirected is called an undirected graph

---

Paths & Cycles

Path $-$ sequence of alternating vertices and edges

• Starts and ends at a vertex
• Simple paths have no repeated vertices or edges

Cycle $-$ path that starts and ends with the same vertex

• Simple cycles have no repeated vertices or edges

---

Key Properties of Graphs

Property 1 $-$ sum of degree of every vertex equals twice the # of edges
$\sum \mathrm{deg}(v)=2m$

• $m$ $-$ number of edges

Property 2 $-$ in an undirected graph with no self loops:
$m\le \frac{n(n-1)}{2}$

• $n$ $-$ number of vertices
• Each vertex can connect to at most $n-1$ others

---

Graph Representations

Three ways to store a graph in memory:

• Edge list $-$ simple but slow for lookups
• Adjacency list $-$ most common python implementation
• Adjacency matrix $-$ fast checking of adjacent vertices, but wastes space

All options have different trade-offs:

Operation	Edge List	Adjacency List	Adjacency Matrix
Space in memory	$O(n+m)$	$O(n+m)$	$O(n^2)$
incidentEdges(v)	$O(m)$	$O(\mathrm{deg}(v))$	$O(n)$
areAdjacent(v,w)	$O(m)$	*	$O(1)$
insertVertex	$O(1)$	$O(1)$	$O(n^2)$
insertEdge	$O(1)$	$O(1)$	$O(1)$
removeVertex	$O(m)$	$O(\mathrm{deg}(v))$	$O(n^2)$
removeEdge	$O(1)$	$O(1)$	$O(1)$

*$O(\min (\mathrm{deg}(v),\mathrm{deg}(w)))$

---

CITS2200 - Lecture 20