cs126 graphs

What is a graph?

• G = (V,E) where

• V is a set of nodes (vertices)

• E is a collection of pairs of vertices (edges)

Define directed edge.

• An ordered pair of vertices (u,v)

• u is the origin 

• v is the destination

Define undirected graph.

A graph of unordered pairs of vertices.

What are some applications of graphs?

• Electronic circuits

• Highway and Flight networks

• Computer networks (LAN, Internet, Web)

• Entity-relationship diagrams

Define endpoint / end vertex.

Vertices with incoming edges.

Define incident.

An edge incoming or outgoing from a vertex.

Define adjacent.

Vertices connected by an edge.

Define degree.

• The number of edges from a vertex

• Denoted deg(v)

Define parallel.

Edges that connect the same vertices.

Define self-loop.

An edge that connects a vertex to itself.

Define path.

• A sequence of alternating edges and vertices

• Starts and ends with a vertex

Define simple path.

A path such that all its vertices and edges are distinct.

Define cycle.

A path that starts and ends at the same vertex.

Define simple cycle.

A cycle such that all its vertices and edges are distinct.

What is Euler’s handshaking lemma?

Sum of the degrees of all vertices is 2 x the number of edges.

What is the rule about the number of edges in a tree?

If G is a tree with n vertices and m edges, m = n-1.

Define complete graph.

A simple and undirected graph where every pair of vertices is connected by a unique edge.

What is the number of edges in a complete graph of n nodes?

O(n²)

Name the (4) ways a graph can be implemented.

• Edge list

• Adjacency list

• Adjacency map

• Adjacency matrix

Describe how an edge list can be used to represent a graph.

• Vertex and Edge objects are stored in distinct, unordered lists

• Each vertex object contains:

  • element

  • reference to position in vertex sequence

• Each edge object contains:

  • element

  • origin vertex object

  • destination vertex object

  • reference to position in edge sequence

Describe how an adjacency list can be used to represent a graph.

• A vertex is mapped to a list of its adjacent vertices

• Two separate collections are kept for incoming and outgoing edges

Describe how an adjacency map can be used to represent a graph.

• A vertex is mapped to a hash-map of its adjacent vertices

• This means retrieving and removing edges can be done in (expected) O(1)

Describe how an adjacency matrix can be used to represent a graph.

• An n x n 2D array is used

• An integer key is associated with each vertex

• Each element stores the Edge object that connects the vertices, or null if no edge connects them

What are the advantages and disadvantages of using an adjacency matrix?

• Any edge can be accessed in O(1)

• It is inefficient for sparse graphs

What is the worst-case space cost for an edge list?

O(n+m)

What is the worst-case time cost of performing incidentEdges(v) on an edge list?

O(m)

What is the worst-case time cost of performing getEdge(u,v) on an edge list?

O(m)

What is the worst-case time cost of performing insertVertex(o) on an edge list?

O(1)

What is the worst-case time cost of performing insertEdge(v,w,o) on an edge list?

O(1)

What is the worst-case time cost of performing removeVertex(v) on an edge list?

O(m)

What is the worst-case time cost of performing removeEdge(e) on an edge list?

O(1)

What is the worst-case space cost for an adjacency list?

O(n+m)

What is the worst-case time cost of performing incidentEdges(v) on an adjacency list?

O(deg(v))

What is the worst-case time cost of performing getEdge(u,v) on an adjacency list?

O(min(deg(u), deg(v)))

What is the worst-case time cost of performing insertVertex(o) on an adjacency list?

O(1)

What is the worst-case time cost of performing insertEdge(v,w,o) on an adjacency list?

O(1)

What is the worst-case time cost of performing removeVertex(v) on an adjacency list?

O(deg(v))

What is the worst-case time cost of performing removeEdge(e) on an adjacency list?

O(1)

What is the worst-case space cost for an adjacency map?

O(n+m)

What is the worst-case time cost of performing incidentEdges(v) on an adjacency map?

expected O(1)

What is the worst-case time cost of performing getEdge(u,v) on an adjacency map?

O(1)

What is the worst-case time cost of performing insertVertex(o) on an adjacency map?

O(1)

What is the worst-case time cost of performing insertEdge(v,w,o) on an adjacency map?

O(1)

What is the worst-case time cost of performing removeVertex(v) on an  adjacency map?

O(deg(v))

What is the worst-case time cost of performing removeEdge(e) on an adjacency map?

expected O(1)

What is the worst-case space cost for an adjacency matrix?

O(n²)

What is the worst-case time cost of performing incidentEdges(v) on an  adjacency matrix?

O(n)

What is the worst-case time cost of performing getEdge(u,v) on an  adjacency matrix?

O(1)

What is the worst-case time cost of performing insertVertex(o) on an  adjacency matrix?

O(n²)

What is the worst-case time cost of performing insertEdge(v,w,o) on an  adjacency matrix?

O(1)

What is the worst-case time cost of performing removeVertex(v) on an  adjacency matrix?

O(n²)

What is the worst-case time cost of performing removeEdge(e) on an  adjacency matrix?

O(1)