graph theory, DS, Tree, shortest path problem

Graph theory

1. MODULE 8
G R A P H S A N D G R A P H M O D E L S
R E P R E S E N T I N G G R A P H S A N D G R A P H I S O M O R P H I S M
P A T H S A N D C I R C U I T S
S H O R T E S T P A T H P R O B L E M S

2. MODULE 8
G R A P H S A N D G R A P H M O D E L S

3. DEFINITION AND EXAMPLES
A graph �=(�,�) consists of a nonempty set of vertices, �, and a set of edges, � connecting pairs of vertices.
Suppose a network is made up of computer centers and
communication links between computers. We can represent each
location with a vertex and each communication link with an edge.
Notice that each edge connects two different vertices,
i.e., no edge connects a vertex to itself. Also, no two
different edges connect the same pair of vertices.
A graph in which each edge connects two
different vertices, and no two edges connect the
same pair of vertices is called a simple graph
A computer network may contain multiple links between computer
centers. In this case we would need more than one edge connecting two
vertices.
Graphs that have multiple edges connecting
the same vertices are called multigraphs

4. MORE EXAMPLES
Now consider a computer network where a communication link
connects a data center with itself, perhaps a feedback loop for
diagnostic purposes.
An edge that connects a vertex to itself is called a loop
So far, the examples have been undirected graphs. However, there
may be the situation in our computer network example where
links may only operate in one direction.
In this example we now have a directed graph that
indicates the direction that the links will operate.
A directed graph, sometimes called a digraph, �=(�,�) consists of a
nonempty set of vertices � and a set of directed edges �.

5. TERMINOLOGY
Two vertices � and � in an undirected graph � are called adjacent in � if � and � are endpoints of an edge � of �.
Such an edge � is called incident with the vertices � and � and is said to connect � and �.
The degree of a vertex in an undirected graph is the number of edges incident with it,
except that a loop at a vertex contributes twice to the degree of that vertex. The
degree of a vertex � is typically denoted deg(�).
Chicago and New York are adjacent vertices, whereas Chicago
and San Francisco are not adjacent.
The degree of Chicago is 9
Handshaking Theorem
Let �=(�,�) be an undirected graph with � edges. Then
2�=෍
??????∈??????
deg(�)
The set of all neighbors of a vertex � of �=(�,�), denoted by ??????(�) is called the
neighborhood of �. If ?????? is a subset of �. we denote ??????(??????) the set of all vertices in �
that are adjacent to at least one vertex in ??????. So, ????????????=ڂ
??????∈????????????(�).
??????�ℎ�����={�������,??????�� ??????���,���ℎ������,������}

6. TERMINOLOGY
When (�,�) is an edge of the directed graph �, the vertex � is called the initial vertex of (�,�) and � is
called the terminal or end vertex of (�,�). The initial vertex and terminal vertex of a loop are the same.
For the directed edge between San Francisco
and Los Angeles, San Francisco is the initial
vertex and Los Angeles is the terminal vertex.
There are two directed edges connecting Denver and
Chicago. In one direction Chicago is the initial vertex.
In the other direction Chicago is the terminal vertex.
The in-degree of Chicago is 3 and
the out-degree of Chicago is 4
Theorem
Let �=(�,�) be a graph with directed edges. Then
෍
??????∈??????
���
−
(�)=෍
??????∈??????
���
+
(�)=|�|

7. BIPARTITE GRAPHS
A simple graph � is called bipartite if its vertex set � can be partitioned into two disjoint sets �
1 and �
2 such that every edge in the graph
connects a vertex in �
1 and a vertex in �
2 (so that no edge in � connects either two vertices in �
1 or two vertices in �
2).
Are the graphs � and � bipartite?
Arbitrarily assign red to the vertex �.
All vertices that are adjacent to �
must be a different color than red.
All vertices adjacent to �,�,�,
or � must be red to avoid
having an edge with two blue
endpoints. So � and � must
be red.
A simple graph is bipartite if and only if it is possible to assign one of two different colors to
each vertex of the graph so that no two adjacent vertices are assigned the same color.
Now that all vertices have
been assigned a color, we
can check all edges and
every edge connects a red
vertex with a blue vertex
Again, assign red to the vertex � and
blue to the vertices adjacent to �.
This means the vertex � will have to be red.
The vertex � is adjacent to a both red
and blue vertices so a third color must
be used. Hence, � is not bipartite.

8. COMPLETE BIPARTITE GRAPHS
A complete bipartite graph ??????
�,� is a graph that has its vertex set partitioned into two subsets of � and � vertices, respectively
with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.

9. MODULE 8
R E P R E S E N T I N G G R A P H S A N D
G R A P H I S O M O R P H I S M

10. ADJACENCY MATRICES
Suppose �=(�,�) is a simple graph where �=�. Suppose the vertices of � are �
1,�
2,…,�
�. The adjacency matrix Α of �, is the �×�
zero–one matrix with 1 as its (�,�)th entry when �
� and �
� are adjacent and 0 as its (�,�)th entry when they are not adjacent. In other words,
if its adjacency matrix is Α=�
��, then
Use an adjacency matrix to represent the given graph.
First, assume we list the vertices in alphabetical order �,�,�,�
to represent the rows and columns of our adjacency matrix.
Again, assume we list the vertices in alphabetical order �,�,�,�,�
to represent the rows and columns of our adjacency matrix.
Use an adjacency matrix to represent the given graph.

11. ADJACENCY MATRICES
Adjacency matrices can also be used to represent undirected graphs with loops and multiple edges. A loop at a vertex is represented
by a 1 at the �,��ℎ position of the matrix. When multiple edges connect the same pair of vertices �
� and �
� (or there are multiple loops
at the same vertex) the matrix is no longer a zero–one matrix, because the �,��ℎ entry will be the number of edges between �
� and �
�.
Represent each of the graphs below with an adjacency matrix.

12. ISOMORPHIC GRAPHS
The simple graphs �
1=(�
1,�
1) and �
2=(�
2,�
2) are isomorphic if there exists a one-to-one and onto function � from �
1 to �
2 such that
� and � are adjacent in �
1 if and only if �(�) and �(�) are adjacent in �
2, for all �,�∈�
1. Such a function � is called an isomorphism.
An isomorphism between two simple graphs is a one-to-one correspondence that preserves the adjacency relationship.
There are �! possible one-to-one correspondences between the vertex sets of two simple graphs with � vertices.
Sometimes it is not as hard to show two simple graphs are not isomorphic since isomorphic graphs must have all of the following:
1.The same number of vertices.
2.The same number of edges.
3.The degrees of the vertices in each graph must be the same.

13. ISOMORPHIC GRAPHS
Determine if the following graphs are isomorphic. Determine if the following graphs are isomorphic.
Start by letting ��
1=�
1. Then consider adjacencies.
�
1 is adjacent to �
2 and �
5. �
1 is adjacent to �
3 and �
4.
So let ��
2=�
3 and ��
5=�
4.
�
2 is adjacent to �
1 and �
3 and ��
2=�
3 is adjacent to
�
1 and �
5. So let ��
3=�
5 since ��
1=�
1.
�
3 is adjacent to �
2 and �
4 and ��
3=�
5 is adjacent
to �
2 and �
3. Let ��
4=�
2 since ��
2=�
3.
Notice, the number of vertices and edges are the
same. Also, the degrees of each vertex match.
There are 5 vertices and 7 edges in each graph. However,
the degrees of the vertices don’t match.
The degrees in the graph on the left are 3,2,3,3,3.
The degrees in the graph on the right are 2,4,2,3,3.

14. MODULE 8
P A T H S A N D C I R C U I T S

15. PATHS AND CIRCUITS
A path is a sequence of edges that begins at a vertex and travels from vertex to vertex along the edges of a graph.
An example of a path from � to � would be ��� or ����
An undirected graph is connected if there is a path between every pair of distinct vertices of the graph.
This is a disconnected graph since no path
exists between � and any other vertex.
This is a connected graph
A path of length greater than zero that begins and ends at the same vertex is called a circuit.
An example of a circuit would be �����

16. DEFINITIONS
A path or circuit is called simple if it does not contain the same edge more than once
An Euler path in � is a simple path containing every edge of �
An Euler circuit in � is a simple circuit containing every edge of �
Which of these graphs have an Euler path? Which have an Euler circuit?
�
1 has an Euler circuit, i.e. �������
�
2 has no Euler path and hence no Euler circuit
�
3 has and Euler path, i.e. ��������, but no Euler circuit
Your turn: Which of these graphs have an
Euler path? Which have an Euler circuit?
Answer: �
1 has neither, �
2 has an Euler path but no Euler
circuit, �
3 has an Euler circuit and hence an Euler path.
Note: If � has an Euler circuit, then
� necessarily has an Euler path
�
1 �
2 �
3

17. EXISTENCE
A connected graph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree
A connected graph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree
Summary: An Euler path exists if exactly 0 or 2 vertices have odd degree. An Euler circuit exists if 0 vertices have odd degree
Which of these graphs have an Euler path? Which have an Euler circuit?
The degrees of the
vertices in �
1 are
2,3,2,3. So an Euler
path exists, but no
Euler circuit
The degrees of the
vertices in �
2 are
2,3,4,3,2,4,4. So an
Euler path exists,
but no Euler circuit.
There are 6 vertices
with odd degree in
�
3 so no Euler path
exists and hence,
no Euler circuit.

18. DEFINITIONS
A Hamilton path is a simple path in a graph � that passes through every vertex exactly once.
A Hamilton circuit is a simple circuit in a graph � that passes through every vertex exactly once.
Note: The term “simple” implies we cannot repeat edges. However, we do not have to use every edge like Euler paths and circuits.
Which of these graphs have a Hamilton circuit or, if not, a Hamilton path?
�
1 has a Hamilton
circuit and hence,
a Hamilton path,
i.e. ������
�
2 has no Hamilton
circuit, but does have
a Hamilton path, i.e.
����
�
3 does not have a
Hamilton path and hence,
no Hamilton circuit

19. MODULE 8
S H O R T E S T P A T H P R O B L E M S

20. WEIGHTED GRAPHS
Occasionally, weights are assigned to the edges of a graph. For example, distances, costs, etc.

21. TRAVELING SALESPERSON
PROBLEM
What is the shortest route a traveling salesperson should take to visit a set of cities?
This problem reduces to finding a Hamilton circuit in a complete graph, i.e. a graph that contains one edge between each pair of vertices.
This graph shows five cities
with the weights of each edge
given by the distance in miles
between each city
How can we find a Hamilton circuit
that has the shortest length?

22. BRUTE FORCE ALGORITHM
The brute force algorithm lists all Hamilton circuits and selects the one with the minimum total length.
This will always produce an optimum
result, but is inefficient in most cases
In a graph with � vertices, once a starting point has been selected, there will be �−1! different Hamilton circuits to examine
Half of those are duplicates (in reverse order), so we only need to examine Τ�−1!2 to find the answer but this can still be quite a large number

23. NEAREST NEIGHBOR ALGORITHM
For the nearest neighbor algorithm (NNA), we select a starting point and move to the nearest unvisited neighbor.
Repeat this until the circuit is complete.
Recall, the shortest circuit starting with Detroit was:
Detroit–Toledo–Kalamazoo–Grand Rapids–Saginaw–Detroit
Using the NNA:
1.The closest neighbor to Detroit is Toledo
2.The closest unvisited neighbor to Toledo is Kalamazoo
3.The closest unvisited neighbor to Kalamazoo is Grand Rapids
4.The closest unvisited neighbor to Grand Rapids is Saginaw
5.Return to Detroit
With the repeated nearest neighbor algorithm, we work the
the NNA at each vertex then choose the optimum circuit

24. FINAL EXAM

25. FINAL EXAM (STEP 1) –
REGISTRATION MODULE
•Go to the module and locate Final Exam Registration Instructions
•Carefully read through the instructions before completing Step 1
•Navigate to Panopto on the left side of your screen
•Go to the Registration folder then Registration [Assignments]
•Select Create and begin recording with audio, video, and screen sharing on
•While your video is recording, navigate to the Final Exam Registration Survey in the module and complete the
survey
•Stop the recording and submit your video to the Final Exam Registration Video Submission assignment
•Must be completed no later that 11:59pm CT on the last day of week 9

26. FINAL EXAM (STEP 2) – FINAL
EXAM ACCESS CODE
•Cannot be completed if Step 1 has not been completed and approved
•To be done in conjunction with taking the final exam
•Do not begin until you are ready to complete the exam in one sitting
•Navigate to the Final Exam [Assignments] folder inside the Final Exam folder in Panopto
•Select Create and begin recording with audio, video, and screen sharing on
•Return to the module and complete the quiz to get the access code for the final exam and leave the
recording on
•Not available August 22
nd
at 12am CT

27. FINAL EXAM (STEP 3) – TAKE THE
EXAM
•With your recording still on, navigate to the module and select the final exam
•Enter the password and begin
•Complete the questions and add work for each
•When you are done, submit the exam and stop the recording
•Return to the module and submit your recording to the Final Exam Video Submission assignment

28. STANDARD SELF -PROCTORED EXAM
RULES

29. SPECIFIC FINAL EXAM RULES

30. FINAL EXAM DETAILS
•Available Thursday, August 22
nd
@12am CT through Saturday, August 24
th
@11:59pm CT
•2-hour time limit
•Do not open the exam until you are ready to complete it
•10 questions
•Comprehensive
•Add your work to every problem (required)

31. QUESTIONS?