Graph

Definition

Defines a set of vertices $V$ and a collection of pairs of vertices $E$ called edges

• Edges can be directed (ordered) or undirected (unordered) vertex pairs

Properties

Where $n$ is the # of vertices, $m$ is the # of edges

• Sum of degrees of all vertices is $2m$
• In a simple undirected graph $m\le [n(n-1)]/2$
• In a simple directed graph $m\le n(n-1)$

Terminology

Edge incidence

Edges are incident on their endpoints

Adjacent vertices

Adjacent vertices are connected by an edge

Degree (of vertex)

Number of edges on a vertex

Cycle

A path that starts and ends at the same vertex

Simple cycle

A cycle where all vertices are distinct

Connected graph

A graph $G=(V,E)$ is connected if there’s a path between every pair of vertices in $V$

Connected component

A subgraph of a graph, where the subgraph is a connected graph and the subgraph is not connected to any other vertices outside the graph

• i.e.: A maximal connected subgraph of a graph
• Can be computed using Depth first search and Breadth first search

Tree

A graph that is connected and has no cycles

• A tree with $n$ vertices has $(n-1)$ edges

Forest

A graph without cycles - i.e.: its connected components are trees

Spanning tree

A connected subgraph of a graph, where the subgraph has the same vertex set (uses all of the OG vertices)

• A spanning tree isn’t unique, unless the graph is a Tree

Spanning forest

A spanning forest of a graph is a Spanning tree that is a Forest

Terminology (undirected graphs)

Parallel edges (undirected)

Share the same two endpoints

Self-loop (undirected)

Edge with only one endpoint

Simple graph (undirected)

No parallel edges or self-loops in the entire graph

Terminology (directed graphs)

Tail and head

A directed edge goes from its tail to head

Out-degree

Number of edges out of a vertex

In-degree

Number of edges into a vertex

Parallel edges (directed)

Share the same tail and head - must be going the same direction - not parallel just because the endpoints are the same

Self-loop (directed)

Edge with head and tail

Simple graph (directed)

No parallel edges or self loops, but anti-parallel pairs (two edges with same endpoints but diff. directions) are allowed

Main operations

• numVertices(): Returns the number of vertices of the graph.
• vertices(): Returns an iteration of all the vertices of the graph
• numEdges(): Returns the number of edges of the graph.
• edges(): Returns an iteration of all the edges of the graph
• getEdge(u,v): Returns the edge from vertex u to vertex v, if one exists; otherwise return null
• endVerticesOf(e): Returns an array containing the two endpoint vertices of edge e. If the graph is directed, the first vertex is the origin and the second is the destination.
• opposite(v,e): For edge e incident to vertex v, returns the other vertex of the edge; an error occurs if e is not incident to v.
• degree(v) - in/outDegree(v): Returns number of edges upon the vertex (alt. for directed)
• incidentEdges - in/outEdges(v): Returns an iteration of all edges from vertex v (alt. directed)
• insertVertex(x): Creates and returns a new Vertex storing some element x
• insertEdge(u,v,x): Creates and returns a new Edge from vertex u to vertex v, storing element x; an error occurs if there already exists an edge from u to v.
• removeVertex(v): Removes vertex v and all its incident edges from the graph
• removeEdge(e): Removes edge e from the graph

Implementations

• Edge list graph data structure
• “Modern” adjacency list with incidence containers
  • Basic adjacency list graph data structure (less efficient)
• Adjacency matrix graph data structure

Tip

It can improve efficiency when using these implementations for the vertex/edge objects to store their position in the sequence

Comparisons

Operation	Adjacency list	Edge list	Adjacency matrix
Space	$O(n+m)$	$O(n+m)$	$O(n^2)$
insertVertex(x)	$O(1)$	$O(1)$	$O(n^2)$
insertEdge(u,v,x)	$O(1)$	$O(1)$	$O(1)$
removeVertex(v)	$O(deg(v))$	$O(m)$	$O(n^2)$
removeEdge(e)	$O(1)$	$O(1)$	$O(1)$
degree(v)	$O(1)$	$O(m)$	$O(1)$
incidentEdges(v)	$O(deg(v))$	$O(m)$	$O(n)$
getEdge(u,v)	$O(min(deg(u),deg(v)))$	$O(m)$	$O(1)$
endVerticesOf(e)	$O(1)$	$O(1)$	$O(1)$
opposite(v,e)	$O(1)$	$O(1)$	$O(1)$
vertices()	$O(n)$	$O(n)$	$O(n)$
edges()	$O(m)$	$O(m)$	$O(n^2)$
numVertices()	$O(1)$	$O(1)$	$O(1)$
numEdges()	$O(1)$	$O(1)$	$O(1)$