Graphs via Adjacency Matrices

Chapter 20

Intro

Königsberg Bridge Problem

The river Pregel flows around the island of Kneiphof and then divides into two branches.

Euler's first figure of the seven bridges of Königsberg problem from ‘Solutio problematis ad geometriam situs pertinentis.’

Euler's first figure of the seven bridges of Königsberg problem from ‘Solutio problematis ad geometriam situs pertinentis.’

Starting at one land area, can you cross all 7 bridges exactly once and return to the start?

In 1736, Euler invented graph theory by representing this problem as a graph to solve the problem.

Euler determined that only 0 or 2 vertices (lands) can have an odd number of edges (bridges). All 4 lands have an odd number of bridges, so there is no solution.

Graph Theory

Over the past 250 years, graph theory has been applied to a variety of problems, including:

• modeling and analysis of electrical circuits,

• chemical compounds,

• highway maps,

• finding the shortest route,

• project planning,

• linguistics,

• genetics,

• social science,

• etc.

Set Theory Notation

• Member (): is an element of the set .

• Subset (): every element of that is an element of .

• Intersection (): contains all the elements in and .
  and

• Union (): set of all the elements that are in or in .
  or

• Ordered Pairs (): set of all the ordered pairs of elements of and .
  

Graph Definitions and Notations

Graph

• is a finite nonempty set of vertices of .

• .
  Elements in are the pairs of elements of .
  is the set of edges.

Directed Graphs

Directed graph or digraph: elements of are ordered pairs.

• Pairs (, ) and (, ) represent different edges.

Undirected Graphs

• Undirected graph: elements are not ordered pairs.

  • Pairs (, ) and (, ) represent the same edge.

Graph Definitions and Notations

• Subgraph of : if and .

  • Every vertex and edge of is in .

• Adjacent: there is an edge from one vertex to the other; i.e.,

• Loop: edge to and from a single vertex,

• Parallel edges: associated with the same pair of vertices.

• Simple graph: has no loops or parallel edges

• Connected vertices: there is a path from to .

• Path from to is if there is sequence of vertices such that , , and is an edge for all .

• Simple path: path in which all vertices, except possibly the first and last, are distinct.

• Cycle: simple path in which the first and last vertices are the same.

• Connected: paths exist from each vertex to all other vertices.

• If there is an edge from to (i.e., ), then is adjacent to and is adjacent from .

• Strongly connected: any two vertices in are connected.

Graph Data Structures

To process and manipulate graphs, we must store graphs in computer memory.

A graph is commonly represented in one of two ways:

1. Adjacency matrices

2. Adjacency lists

Adjacency Matrices

Given a graph, , with vertices ,

the adjacency matrix, of , is matrix such that

Undirected Example

	[0]	[1]	[2]	[3]	[4]
[0]	0	1	1	0	0
[1]	1	0	1	1	1
[2]	1	1	0	1	1
[3]	0	1	1	1	0
[4]	0	1	1	0	0

The adjacency matrix of an undirected graph is symmetric.

Adjacency Matrix: Directed Example

	[0]	[1]	[2]	[3]	[4]
[0]	0	1	1	0	0
[1]	0	0	1	1	1
[2]	1	0	0	1	1
[3]	0	0	0	1	0
[4]	0	0	0	0	0

The adjacency matrix of a directed graph is asymmetric.

Adjacency Matrix: Weighted Directed Example

A weighted directed graph and it's representation using adjacency matrix.

A weighted directed graph and it's representation using adjacency matrix.

If the edges have weights, they are stored in the matrix.

Operations Commonly Performed on a Graph

• Create the graph.

• Clear the graph (make the graph empty).

• Determine whether the graph is empty.

• Traverse the graph.

• Visualize the graph.

• Modify the graph.

Graph Traversals

• Traversing a graph is like traversing a binary tree,
  except that:

  • A graph may have cycles.

  • May not be able to traverse the entire graph from a single vertex.

• Most common graph traversal algorithms

  • Depth-first traversal

  • Breadth-first traversal

Depth-First Traversal

Recursive depth-first traversal algorithm at a given node, .

1. Mark node as visited.

2. Visit the node.

3. For each vertex adjacent to ,
   If is not visited,
   begin the depth-first traversal at .

Depth-First Traversal: Example

Depth-first ordering of vertices (starting at 0):
0, 1, 4, 3, 2, 5, 7, 8

Breadth-First Traversal of a Graph

• Like traversing a binary tree, level by level.

• Nodes at each level are visited one after another.

• Use a queue to implement the breadth-first search algorithm.

Breadth-First Traversal: Example

Breadth-first ordering of vertices (starting at 0):
0, 1, 3, 4, 2, 5, 7, 8

Shortest Path in a Weighted Graph

In a weighted graph, every edge has a nonnegative weight.

• The weight of the path, , is the sum of the weights of all edges on the path .

• The source is the first vertex of a path.

• The shortest path is the path with the smallest weight.

Shortest Path Algorithm

We will implement the greedy algorithm, developed by Dijkstra.

1. Initialize an array, smallestWeight, all infinity and
   weightFound to false.

2. Set smallestWeight[start] to 0 and
   currentVertex to start.

3. Find the vertex, v, that is closest to the currentVertex for which the shortest path has not been determined.

4. Mark v as the (next) vertex for which the smallest weight is found.

5. For each vertex w in G, such that the shortest path from start to w has not been determined and an edge (v, w) exists, if the weight of the path to w via v is smaller than the current weight, update the weight of w to the weight of v plus the weight of the edge (v, w).

Given vertices, repeat steps 3 through 5, times.

Shortest Path Algorithm: Example

1 / 1

Shortest Path Algorithm: Enhancements

This demonstrated algorithm keeps track of the total weight of the shortest path. Consider what you would add to record the actual path.

Instead of using a sequence search to find the minimum weight, which is , a priority queue could be used.

Lab 22: Graphs via Adjacency Matrix

Let’s look at the lab based on today’s lecture.