11

Introduction
 Graphs provide a rich and powerful way to model relations in complex problems. Graphs can be used to model many real world problems, such as network and transport links.
 This week we will:
 Review basic graph terminology.
 Cover implementation details of different kinds of graphs.
 Study possible uses of graphs.

Definitions
 Vertex – a node in a graph
 Edge – link connecting two nodes (relationship)
 Adjacent – two nodes connected by an edge
 Undirected Graph  a graph in which the edges have no directional component. It is possible to move in both directions along an edge between two vertices
 Directed graph (digraph)  a graph in which the edges have directional components. It is possible to move from one vertex to the other only in the indicated direction
 Path – a sequence of distinct vertices, each adjacent to the next
 Cycle – a path containing at least three vertices such that the last vertex is adjacent to the first
 Connected graph – an undirected graph in which there is a path from any vertex to any other vertex
 Indegree – the indegree of a node is the number of edges that end at that node
 Outdegree – the outdegree of a node is the number of edges that start at that node
 Network – a graph in which the edges are weighted
 Weighted graph – a weighted graph is a graph with weights/cost assigned to each edge
 Graph – represents relationship among nodes, and is defined as a set of vertices (V) and a set of edges (E)

Adjacency
 Two nodes that have an edge connection between them are said to be adjacent. If the edge is directed then the adjacency will only be as dictated by the edge direction.
 Vertices
 The vertices in the graph above can be represented as,
 $$ V = \{0, 1, 2, 3, 4, 5, 6 \} $$
 Edges
 The edges in the graph can be represented as:
 $$ E = \{\{0, 1\}, \{0, 5\}, \{0, 6\}, \{1, 2\}, \{1, 3\}, \{1, 5\}, \{2, 6\}, \{3, 2\}, \{4, 3\}, \{5, 3\}, \{6, 5\}\} $$
 Indegree and Outdegree
 In and Outdegree for few of the vertices are as shown:
 Adjacency
 For the above graph, the vertices adjacent to vertex 5 is vertex 3 and those adjacent to vertex 1 are {2, 3, 5}.
 Undirected graphs
 In an undirected graph it is possible to move in both directions along an edge between two vertices.
 Vertices
 Each vertex is part of the set V of vertices in the graph
 $$ V = \{0,1,2,3,4, 5, 6\} $$
 Edges
 Each edge can be represented as a pair of vertices
 $$ E = \{\{0, 1\}, \{0, 5\}, \{0, 6\}, \{1, 2\}, \{1, 3\}, \{1, 5\}, \{2, 6\}, \{3, 2\}, \{4, 3\}, \{5, 3\}, \{6, 5\}\} $$
 Adjacency
 For the above graph, the vertices adjacent to vertex 5 are {0, 1, 3, 6} and those adjacent to vertex 1 are {0, 2, 3, 5}.
An Example Digraph (directed graph) 
Graph ADT Operations

addVertex( )  creates a new vertex addEdge( )  creates a new edge removeVertex( )  removes the vertex and its associated edges removeEdge( )  removes the edge vertexSize( )  returns the number of vertices in the graph edgeSize( )  returns the number of edges in the graph inDegree( )  returns number of incoming edges to a vertex outDegree( )  returns the number of outgoing edges from a vertex adjacent( )  checks if the given vertices are adjacent


Graph Representation
 Adjacency List for a directed graph
 This representation uses a linked list to represent the set of adjacent vertices. The connectivity (adjacency) of each vertex can then be represented through a linked list.
 The outdegree of each vertex can easily be counted using this representation e.g., vertex 3 doesn’t connect to any other vertices, out degree is 0. Vertex 1 connects to 3 others and has an outdegree of 3. For the indegree count number of times a vertex appears in the list of connected nodes e.g., vertex 2 appears twice, indegree is therefore 2.
 Adjacency Matrix for a directed graph
 In case of an undirected graph (shown above), the matrix will be symmetrical, that is, both A(i, j) and A(j,i) values would be the same. For example consider A(3,4) and A(4,3) being 1 indicating that one can move from 3 to 4 and also from 4 to 3.
 Adjacency Matrix for the undirected graph
 Characteristics of Adjacency List
 No wasted memory space.
 Sequential access only to find adjacent access.
 Characteristics of Adjacency Matrix
 Space is wasted.
 Easy to determine adjacency.
A directed graph. An undirected graph. 
Graph Application
 Shortest path
 Determine the shortest path between a given vertex and other vertices. This is important to reduce costs significantly through efficient routing of goods and services.
 Critical path analysis
 Critical Path Analysis helps you to identify the minimum length of time needed to complete a project. Any delay on the critical path events are likely to delay the whole project. Thus the project can be completed in the allocated time by allocating resources appropriately.

Shortest Path Algorithm  Introduction
 Many real world problems require computing the shortest path in a network. This is very important problem to solve for transport links, networks, pipelines etc. For such problems we can associate a cost to each edge (that is a weighted graph) and then measure the least cost that would be involved between any two given nodes. The cost could be a measure of distance for example in a transportation link. One popular algorithm to find the shortest path between a given vertex and all other vertices is Dijkstra’s algorithm.
 A weighted graph
 A weighted graph will have a weight assigned to the edges. It is possible to have an edge between two vertices have a different weight in each direction. An example weighted graph is shown below.
 Shortest path
 The shortest path between any two vertices is the one with the smallest sum of the weighted edges
 Example: what is the shortest path between vertex 0 and vertex 3?
 Shortest path problem
 Consider the following graph. We need to determine the shortest path from the vertex 0 to vertex 3.
 There are two paths to consider:
 Path 1: 0 → 1 → 4 → 3
 Path 3: 0 → 1 → 3
 by calculating the edge weights it can be found that the path 0 → 1 → 4 → 3 as shown on the graph with red lines is the shortest path in getting from vertex 0 to vertex 3.

Summary
 A graph ADT is used to represent the relationships between nodes such as in a network.
 The graph can be implemented either as an adjacency list or an adjacency matrix.
 There are many applications of graphs such as finding the shortest path or the critical path.