Graphs

• G = (V,E)
• V is the vertex set.
• Vertices are also called nodes and points.
• E is the edge set.
• Each edge connects two different vertices.
• Edges are also called arcs and lines.
• Directed edge has an orientation (u,v).
u v
 Graphs

• Undirected edge has no orientation (u,v).

u v

• Undirected graph => no oriented edge.

• Directed graph => every edge has an
orientation.
 Undirected Graph

2
3
8
1 10

4
5
9
11

6
7
Directed Graph (Digraph)

2
3
8
1 10

4
5
9
11

6
7
Applications—Communication Network

2
3
8
1 10

4
5
9
11

6
7

• Vertex = city, edge = communication link.

 Driving Distance/Time Map

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

• Vertex = city, edge weight = driving

distance/time.
 Street Map

2
3
8
1 10

4
5
9
11

6
7

• Some streets are one way.

 Complete Undirected Graph

Has all possible edges.

n=1 n=2 n=3 n=4

Number Of Edges—Undirected Graph

• Each edge is of the form (u,v), u != v.

• Number of such pairs in an n vertex graph
is n(n-1).
• Since edge (u,v) is the same as edge (v,u),
the number of edges in a complete
undirected graph is n(n-1)/2.
• Number of edges in an undirected graph is
<= n(n-1)/2.
Number Of Edges—Directed Graph

• Each edge is of the form (u,v), u != v.

• Number of such pairs in an n vertex graph
is n(n-1).
• Since edge (u,v) is not the same as edge
(v,u), the number of edges in a complete
directed graph is n(n-1).
• Number of edges in a directed graph is <=
n(n-1).
 Vertex Degree

2
3
8
1 10

4
5
9
11

6
7

Number of edges incident to vertex.

degree(2) = 2, degree(5) = 3, degree(3) = 1
 Sum Of Vertex Degrees

8
10

9
11

Sum of degrees = 2e (e is number of edges)

 In-Degree Of A Vertex

2
3
8
1 10

4
5
9
11

6
7

in-degree is number of incoming edges

indegree(2) = 1, indegree(8) = 0
 Out-Degree Of A Vertex

2
3
8
1 10

4
5
9
11

6
7

out-degree is number of outbound edges

outdegree(2) = 1, outdegree(8) = 2
 Sum Of In- And Out-Degrees

each edge contributes 1 to the in-degree of

some vertex and 1 to the out-degree of
some other vertex

sum of in-degrees = sum of out-degrees = e,

where e is the number of edges in the
digraph
Graph Operations And
Representation
 Sample Graph Problems

• Path problems.
• Connectedness problems.
• Spanning tree problems.
 Path Finding
Path between 1 and 8.
2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

Path length is 20.

Another Path Between 1 and 8

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

Path length is 28.

 Example Of No Path

2
3
8
1 10

4
5
9
11

6
7

No path between 2 and 9.

 Connected Graph

• Undirected graph.
• There is a path between every pair of
vertices.
Example Of Not Connected

2
3
8
1 10

4
5
9
11

6
7
Connected Graph Example

2
3
8
1 10

4
5
9
11

6
7
Connected Components

2
3
8
1 10

4
5
9
11

6
7
 Connected Component

• A maximal subgraph that is connected.

 Cannot add vertices and edges from original
graph and retain connectedness.
• A connected graph has exactly 1
component.
 Not A Component

2
3
8
1 10

4
5
9
11

6
7
 Communication Network

2
3
8
1 10

4
5
9
11

6
7

Each edge is a link that can be constructed (i.e., a

feasible link).
Communication Network Problems

• Is the network connected?

 Can we communicate between every pair of
cities?
• Find the components.
• Want to construct smallest number of
feasible links so that resulting network is
connected.
 Cycles And Connectedness

2
3
8
1 10

4
5
9
11

6
7

Removal of an edge that is on a cycle does not affect

connectedness.
 Cycles And Connectedness

2
3
8
1 10

4
5
9
11

6
7

Connected subgraph with all vertices and minimum

number of edges has no cycles.
 Tree

• Connected graph that has no cycles.

• n vertex connected graph with n-1 edges.
 Spanning Tree

• Subgraph that includes all vertices of the

original graph.
• Subgraph is a tree.
 If original graph has n vertices, the spanning
tree has n vertices and n-1 edges.
 Minimum Cost Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

• Tree cost is sum of edge weights/costs.

 A Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Spanning tree cost = 51.

 Minimum Cost Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Spanning tree cost = 41.

 A Wireless Broadcast Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Source = 1, weights = needed power.

Cost = 4 + 8 + 5 + 6 + 7 + 8 + 3 = 41.
 Graph Representation

• Adjacency Matrix
• Adjacency Lists
 Linked Adjacency Lists
 Array Adjacency Lists
 Adjacency Matrix
• 0/1 n x n matrix, where n = # of vertices
• A(i,j) = 1 iff (i,j) is an edge

1 2 3 4 5
2
3 1 0 1 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 1
4 4 1 0 0 0 1
5
5 0 1 1 1 0
 Adjacency Matrix Properties
1 2 3 4 5
2
3 1 0 1 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 1
4 4 1 0 0 0 1
5
5 0 1 1 1 0
• Diagonal entries are zero.
• Adjacency matrix of an undirected graph is
symmetric.
 A(i,j) = A(j,i) for all i and j.
 Adjacency Matrix (Digraph)
1 2 3 4 5
2
3 1 0 0 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 0
4 4 0 0 0 0 1
5
5 0 1 1 0 0
• Diagonal entries are zero.
• Adjacency matrix of a digraph need not be
symmetric.
 Adjacency Matrix

• n2 bits of space
• For an undirected graph, may store only
lower or upper triangle (exclude diagonal).
 (n-1)n/2 bits
• O(n) time to find vertex degree and/or
vertices adjacent to a given vertex.
 Adjacency Lists
• Adjacency list for vertex i is a linear list of
vertices adjacent from vertex i.
• An array of n adjacency lists.

aList[1] = (2,4)
2 aList[2] = (1,5)
3
aList[3] = (5)
1
aList[4] = (5,1)
4
5 aList[5] = (2,4,3)
 Linked Adjacency Lists
• Each adjacency list is a chain.
2 aList[1]
3
[2]
1 [3]
[4]
4
5 aList[5]

Array Length = n
# of chain nodes = 2e (undirected graph)
# of chain nodes = e (digraph)
 Array Adjacency Lists
• Each adjacency list is an array list.
2 aList[1]
3
[2]
1 [3]
[4]
4
5 aList[5]

Array Length = n
# of list elements = 2e (undirected graph)
# of list elements = e (digraph)
 Weighted Graphs

• Cost adjacency matrix.

 C(i,j) = cost of edge (i,j)
• Adjacency lists => each list element is a
pair (adjacent vertex, edge weight)