Graphs in Discrete mathematics for computing

Graphs and types

1. Discrete Math For Computing II
Main Text:
Topics in enumeration; principle of inclusion and
exclusion, Partial orders and lattices. Algorithmic
complexity; recurrence relations, Graph theory.
Prerequisite: CS 2305
"Discrete Mathematics and its Applications"
Kenneth Rosen, 5th Edition, McGraw Hill.

2. Contact Information
B. Prabhakaran
Department of Computer Science
University of Texas at Dallas
Mail Station EC 31, PO Box 830688
Richardson, TX 75083
Email: [email protected]
Phone: [phone];Fax: [phone]
URL: http://www.utdallas.edu/~praba/cs3305.html
Office: ES 3.706
Office Hours: 3.30 –4.00 pm & 5.15 –6pm. Tuesdays;
5.15 –6pm Thursdays
Other times by appointments through email
Announcements: Made in class and on course web page.
TA: TBA.

3. Course Outline
Selected topics in chapters 6 through 9.
Chapter 6: Advanced Counting Techniques:
recurrence relations, principle of inclusion and
exclusion
Chapter 7: Relations: properties of binary relations,
representing relations, equivalence relations, partial
orders
Chapter 8: Graphs: graph representation,
isomorphism, Euler paths, shortest path algorithms,
planar graphs, graph coloring
Chapter 9: Trees: tree applications, tree traversal,
trees and sorting, spanning trees

4. Course ABET Objectives
Ability to construct and solve recurrence relations
Ability to use the principle of inclusion and exclusion to solve
problems
Ability to understand binary relations and their applications
Ability to recognize and use equivalence relations and partial
orderings
Ability to use and construct graphs and graph terminology
Ability to apply the graph theory concepts of Euler and Hamilton
circuits
Ability to identify and use planar graphs and shortest path
problems
Ability to use and construct trees and tree terminology
Ability to use and construct binary search trees

5. Evaluation
2 Mid-terms: in class. 75 minutes. Mix of MCQs
(Multiple Choice Questions) & Short Questions.
1 Final Exam: 75 minutes or 2 hours (depending on
class room availability). Mix of MCQs and Short
Questions.
2 -3 Quizzes: 5-6 MCQs or very short questions. 15
minutes each.
Homeworks/assignments: 3 or 4 spread over the
semester.

6. Homeworks
Each homework will be for 10 marks.
Homeworks Submission:
Submit on paper to TA/Instructor.

7. Grading
Home works: 5%
Quizzes: 10%
Mid-terms : 50%
Final: 35%

8. Likely Letter Grades
A-, A, A+: 90 -100%
B-, B, B+: 80 -90%
C-, C, C+: 70 -80%
D-, D, D+: 60 -70%
F: Below 60%
Class average will influence above the ranges.

9. Schedule
Quizzes: Dates announced in class & web, a week
ahead. Mostly just before midterms and final.
Mid-term 1 : February 10, 2005
Mid-term 2: March 24, 2005
Final Exam: 11am, April 26, 2005 (As per UTD
schedule)
Subject to minor changes
Quiz and homework schedules will be announced in
class and course web page, giving sufficient time for
preparation.

10. Cheating
Academic dishonesty will be taken seriously.
Cheating students will be handed over to
Head/Dean for further action.
Remember: home works (and exams too !)
are to be done individually.
Any kind of cheating in home works/exams
will be dealt with as per UTD guidelines.

11. Spring Break !
Conference Travel in the week starting March 1
st
.
Propose a 2-hour make up class (with 15 minute
break between the hours) on a Monday morning ?

12. Graph Theory
Chapter 8

13. Varying Applications (examples)
Computer networks
Distinguish between two chemical compounds
with the same molecular formula but different
structures
Solve shortest path problems between cities
Scheduling exams and assign channels to
television stations

14. Topics Covered
Definitions
Types
Terminology
Representation
Sub-graphs
Connectivity
Hamilton and Euler definitions
Shortest Path
Planar Graphs
Graph Coloring

15. Definitions -Graph
Ageneralizationofthesimpleconceptofaset
ofdots,links,edgesorarcs.
Representation:GraphG=(V,E)consistssetofvertices
denotedbyV,orbyV(G)andsetofedgesE,orE(G)

16. Definitions –Edge Type
Directed:Orderedpairofvertices.Representedas(u,v)
directedfromvertexutov.
Undirected:Unorderedpairofvertices.Representedas{u,v}.
Disregardsanysenseofdirectionandtreatsbothendvertices
interchangeably.
u v
u v

17. Definitions –Edge Type
Loop:Aloopisanedgewhoseendpointsareequal
i.e.,anedgejoiningavertextoitselfiscalledaloop.
Representedas{u,u}={u}
MultipleEdges:Twoormoreedgesjoiningthe
samepairofvertices.
u

18. Definitions –Graph Type
Simple(Undirected)Graph:consistsofV,anonemptysetof
vertices,andE,asetofunorderedpairsofdistinctelementsof
Vcallededges(undirected)
RepresentationExample:G(V,E),V={u,v,w},E={{u,v},{v,
w},{u,w}}
u
v
w

19. Definitions –Graph Type
Multigraph:G(V,E),consistsofsetofverticesV,setof
EdgesEandafunctionffromEto{{u,v}|u,vV,u≠v}.
Theedgese1ande2arecalledmultipleorparalleledgesiff
(e1)=f(e2).
RepresentationExample:V={u,v,w},E={e
1,e
2,e
3}
u
v
we
1
e
2
e
3

20. Definitions –Graph Type
Pseudograph:G(V,E),consistsofsetofverticesV,setofEdgesE
andafunctionFfromEto{{u,v}|u,vÎV}.Loopsallowedin
suchagraph.
RepresentationExample:V={u,v,w},E={e
1,e
2,e
3,e
4}
u
v
we
1
e
3
e
2
e
4

21. Definitions –Graph Type
Directed Graph:G(V, E), set of vertices V, and set of Edges E,
that are ordered pair of elements of V (directed edges)
RepresentationExample: G(V, E), V = {u, v, w}, E = {(u, v), (v,
w), (w, u)}
u
w
v

22. Definitions –Graph Type
DirectedMultigraph:G(V,E),consistsofsetofverticesV,set
ofEdgesEandafunctionffromEto{{u,v}|u,vV}.The
edgese1ande2aremultipleedgesiff(e1)=f(e2)
RepresentationExample:V={u,v,w},E={e
1,e
2,e
3,e
4}
u
u
u
e
1
e
2
e
3
e
4

23. Definitions –Graph Type
Type Edges Multiple Edges
Allowed ?
Loops Allowed ?
Simple Graph undirected No No
Multigraph undirected Yes No
Pseudograph undirected Yes Yes
Directed Graph directed No Yes
Directed
Multigraph
directed Yes Yes

24. Terminology–Undirected graphs
u and v are adjacentif {u, v} is an edge, e is called incident with u and v. u
and v are called endpointsof {u, v}
Degree of Vertex (deg (v)): the number of edges incident on a vertex. A
loop contributes twice to the degree (why?).
Pendant Vertex:deg (v) =1
Isolated Vertex:deg (v) = 0
RepresentationExample:ForV={u,v,w},E={{u,w},{u,w},(u,v)},
deg(u)=2,deg(v)=1,deg(w)=1,deg(k)=0,wandvarependant,kis
isolated
u
k
w
v

25. Terminology–Directed graphs
Fortheedge(u,v),uisadjacenttovORvisadjacentfromu,u–Initial
vertex,v–Terminalvertex
In-degree(deg
-
(u)):numberofedgesforwhichuisterminalvertex
Out-degree(deg
+
(u)):numberofedgesforwhichuisinitialvertex
Note:Aloopcontributes1tobothin-degreeandout-degree(why?)
Representation Example: For V = {u, v, w} , E = { (u, w), ( v, w), (u, v) },deg
-
(u) = 0, deg
+
(u) = 2, deg
-
(v) = 1,
deg
+
(v) = 1, and deg
-
(w) = 2, deg
+
(u) = 0
u
w
v

26. Theorems: Undirected Graphs
Theorem 1
The Handshaking theorem:
(why?)Every edge connects 2 vertices


Vv
ve2

27. Theorems: Undirected Graphs
Theorem 2:
An undirected graph has even number of vertices with odd degreeeven
Voof









2
21
V v
1,
V vV u V v
deg(v) termsecond
even also is termsecond Hence
2e. is sum sinceeven is inequalitylast the
of side handright on the termslast two theof sum The
even. is inequalitylast theof side handright in the first term The
V for veven is (v) deg
deg(v) deg(u) deg(v) 2e
verticesdegree odd torefers V2 and verticesdegreeeven ofset theis 1 Pr

28. Theorems: directed Graphs
Theorem 3: deg
+
(u) = deg
-
(u) = |E|  

29. Simple graphs –special cases
Complete graph:K
n, is the simple graph that contains exactly
one edge between each pair of distinct vertices.
RepresentationExample: K
1, K
2, K
3, K
4
K
2K
1
K
4
K
3

30. Simple graphs –special cases
Cycle:C
n, n ≥ 3 consists of n vertices v
1, v
2, v
3… v
nand edges
{v
1, v
2}, {v
2, v
3}, {v
3, v
4} … {v
n-1, v
n}, {v
n, v
1}
RepresentationExample: C
3, C
4
C
3 C
4

31. Simple graphs –special cases
Wheels:W
n, obtained by adding additional vertex to Cn and
connecting all vertices to this new vertex by new edges.
Representation Example: W
3, W
4
W
3 W
4

32. Simple graphs –special cases
N-cubes:Q
n, vertices represented by 2n bit strings of length n.
Two vertices are adjacent if and only if the bit strings that they
represent differ by exactly one bit positions
Representation Example: Q
1, Q
2
0
10
1
00
11
Q
1
01
Q
2

33. Bipartite graphs
InasimplegraphG,ifVcanbepartitionedintotwodisjoint
setsV
1andV
2suchthateveryedgeinthegraphconnectsa
vertexinV
1andavertexV
2(sothatnoedgeinGconnects
eithertwoverticesinV
1ortwoverticesinV
2)
Applicationexample:RepresentingRelations
Representationexample:V
1={v
1,v
2,v
3}andV
2={v
4,v
5,v
6},
v
1
v
2
v
3
v
4
v
5
v
6
V
1
V
2

34. Complete Bipartite graphs
K
m,nisthegraphthathasitsvertexsetportionedintotwo
subsetsofmandnvertices,respectivelyThereisanedge
betweentwoverticesifandonlyifonevertexisinthefirst
subsetandtheothervertexisinthesecondsubset.
Representationexample:K
2,3,K
3,3
K
2,3 K
3,3

35. Subgraphs
A subgraph of a graph G = (V, E) is a graph H =(V’, E’) where V’ is a
subset of V and E’ is a subset of E
Application example: solving sub-problems within a graph
Representation example: V = {u, v, w}, E = ({u, v}, {v, w}, {w, u}}, H
1
, H
2
u
v w
u
u
w
v
v
H
1
H
2G

36. Subgraphs
G = G1 U G2 wherein E = E1 U E2 and V = V1 U V2, G, G1 and G2 are
simple graphs of G
Representationexample:V1={u,w},E1={{u,w}},V2={w,v},
E1={{w,v}},V={u,v,w},E={{{u,w},{{w,v}}
u
vw w
vw
u
G1
G2
G

37. Representation
Incidence(Matrix):Mostusefulwheninformationabout
edgesismoredesirablethaninformationaboutvertices.
Adjacency(Matrix/List):Mostusefulwheninformation
abouttheverticesismoredesirablethaninformationaboutthe
edges.Thesetworepresentationsarealsomostpopularsince
informationabouttheverticesisoftenmoredesirablethan
edgesinmostapplications

38. Representation-Incidence Matrix
G=(V,E)beanunditectedgraph.Supposethatv
1,v
2,v
3,…,v
n
aretheverticesande
1,e
2,…,e
maretheedgesofG.Thenthe
incidencematrixwithrespecttothisorderingofVandEisthenx
mmatrixM=[m
ij],where
Canalsobeusedtorepresent:
Multipleedges:byusingcolumnswithidenticalentries,since
theseedgesareincidentwiththesamepairofvertices
Loops:byusingacolumnwithexactlyoneentryequalto1,
correspondingtothevertexthatisincidentwiththeloop



otherwise 0
ith vincident w is e edge when 1
m
ij
ij

39. Representation-Incidence Matrix
Representation Example: G = (V, E)
v w
u
e1
e3
e2
e
1e
2e
3
v1 0 1
u1 1 0
w 0 1 1

40. Representation-Adjacency Matrix
ThereisanNxNmatrix,where|V|=N,theAdjacenctMatrix
(NxN)A=[a
ij]
Forundirectedgraph
Fordirectedgraph
Thismakesiteasiertofindsubgraphs,andtoreversegraphsifneeded.



otherwise 0
G of edgean is ) v,(v if 1
a
ji
ij 



otherwise 0
G of edgean is } v,{v if 1
a
ji
ij

41. Representation-Adjacency Matrix
Adjacency is chosen on the ordering of vertices. Hence, there
as are as many as n! such matrices.
The adjacency matrix of simple graphs are symmetric (a
ij= a
ji)
(why?)
When there are relatively few edges in the graph the adjacency
matrix is a sparse matrix
Directed Multigraphs can be represented by using aij = number
of edges from v
ito v
j

42. Representation-Adjacency Matrix
Example: Undirected Graph G (V, E)
v u w
v 0 1 1
u 1 0 1
w 1 1 0
u
v w

43. Representation-Adjacency Matrix
Example: directed Graph G (V, E)
v u w
v 0 1 0
u 0 0 1
w 1 0 0
u
v w

44. Representation-Adjacency List
Eachnode(vertex)hasalistofwhichnodes(vertex)itisadjacent
Example:undirectdgraphG(V,E)
u
v w
node Adjacency List
u v , w
v w, u
w u , v

45. Graph -Isomorphism
G1=(V1,E2)andG2=(V2,E2)areisomorphicif:
Thereisaone-to-oneandontofunctionffromV1to
V2withthepropertythat
aandbareadjacentinG1ifandonlyiff(a)andf(b)are
adjacentinG2,forallaandbinV1.
Functionfiscalledisomorphism
ApplicationExample:
Inchemistry,tofindiftwocompoundshavethesame
structure

46. Graph -Isomorphism
Representationexample:G1=(V1,E1),G2=(V2,E2)
f(u
1)=v
1,f(u
2)=v
4,f(u
3)=v
3,f(u
4)=v
2,
u
1
u
3
u
4
u
2
v
3
v
4
v
1 v
2

47. Connectivity
BasicIdea:InaGraphReachabilityamongvertices
bytraversingtheedges
ApplicationExample:
-Inacitytocityroad-network,ifonecitycanbe
reachedfromanothercity.
-Problemsifdeterminingwhetheramessagecanbe
sentbetweentwo
computerusingintermediatelinks
-Efficientlyplanningroutesfordatadeliveryinthe
Internet

48. Connectivity –Path
APathisasequenceofedgesthatbeginsatavertex
ofagraphandtravelsalongedgesofthegraph,
alwaysconnectingpairsofadjacentvertices.
Representationexample:G=(V,E),PathP
represented,fromutovis{{u,1},{1,4},{4,5},{5,
v}}
1
u
3
4
5
2
v

49. Connectivity –Path
Definition for Directed Graphs
APathoflengthn(>0)fromutovinGisasequenceofn
edgese
1,e2,e
3,…,e
nofGsuchthatf(e
1)=(xo,x
1),f(e
2)=
(x
1,x
2),…,f(e
n)=(x
n-1,x
n),wherex
0=uandx
n=v.Apathis
saidtopassthroughx
0,x
1,…,x
nortraversee
1,e
2,e
3,…,e
n
ForSimpleGraphs,sequenceisx0,x
1,…,x
n
Indirectedmultigraphswhenitisnotnecessarytodistinguish
betweentheiredges,wecanusesequenceofverticesto
representthepath
Circuit/Cycle:u=v,lengthofpath>0
SimplePath:doesnotcontainanedgemorethanonce

50. Connectivity –Connectedness
Undirected Graph
Anundirectedgraphisconnectedifthereexistsisa
simplepathbetweeneverypairofvertices
RepresentationExample:G(V,E)isconnectedsince
forV={v
1,v
2,v
3,v
4,v
5},thereexistsapath
between{v
i,v
j},1≤i,j≤5
v
1
v
2
v
3
v
5
v
4

51. Connectivity –Connectedness
UndirectedGraph
ArticulationPoint(Cutvertex):removalofavertex
producesasubgraphwithmoreconnectedcomponentsthanin
theoriginalgraph.Theremovalofacutvertexfroma
connectedgraphproducesagraphthatisnotconnected
CutEdge:Anedgewhoseremovalproducesasubgraphwith
moreconnectedcomponentsthanintheoriginalgraph.
Representationexample:G(V,E),v
3isthearticulationpointor
edge{v
2,v
3},thenumberofconnectedcomponentsis2(>1)
v
1
v
2
v
3
v
4
v
5

52. Connectivity –Connectedness
Directed Graph
Adirectedgraphisstronglyconnectedifthereisapathfrom
atobandfrombtoawheneveraandbareverticesinthe
graph
Adirectedgraphisweaklyconnectedifthereisa
(undirected)pathbetweeneverytwoverticesintheunderlying
undirectedpath
AstronglyconnectedGraphcanbeweaklyconnectedbutthe
vice-versaisnottrue(why?)

53. Connectivity –Connectedness
Directed Graph
Representationexample:G1(Strongcomponent),G2(Weak
Component),G3isundirectedgraphrepresentationofG2orG1
G2
G1 G3

54. Connectivity –Connectedness
Directed Graph
Strongly connected Components: subgraphs of a
Graph G that are strongly connected
Representation example: G1 is the strongly connected
component in G
G1
G

55. Isomorphism -revisited
A isomorphic invariant for simple graphs is the
existence of a simple circuit of length k , k is an
integer > 2 (why ?)
Representationexample:G1andG2areisomorphicsincewe
havetheinvariants,similarityindegreeofnodes,numberof
edges,lengthofcircuits
G1 G2

56. Counting Paths
Theorem:LetGbeagraphwithadjacencymatrixAwithrespecttothe
orderingv
1,v2,…,V
n(withdirectedonundirectededges,withmultiple
edgesandloopsallowed).Thenumberofdifferentpathsoflengthrfrom
VitoVj,whererisapositiveinteger,equalsthe(i,j)
th
entryof
(adjacencymatrix)A
r.
Proof:ByMathematicalInduction.
BaseCase:ForthecaseN=1,a
ij=1impliesthatthereisapathoflength1.This
istruesincethiscorrespondstoanedgebetweentwovertices.
WeassumethattheoremistrueforN=randprovethesameforN=r+1.
Assumethatthe(i,j)
th
entryofA
r
isthenumberofdifferentpathsoflengthrfrom
v
itov
j.Byinductionhypothesis,b
ikisthenumberofpathsoflengthrfromv
itov
k.

57. Counting Paths
Caser+1:InA
r+1
=A
r
.A,
The(i,j)
th
entryinA
r+1
,b
i1a
1j+b
i2a
2j+…+b
ina
nj
whereb
ikisthe(i,j)
th
entryofA
r
.
Byinductionhypothesis,b
ikisthenumberofpathsoflengthrfromv
i
tov
k.
The(i,j)
th
entryinA
r+1
correspondstothelengthbetweeniandj
andthelengthisr+1.Thispathismadeupoflengthrfromv
itov
k
andoflengthfromv
ktovj.Byproductruleforcounting,thenumberof
suchpathsisb
ik*a
kjTheresultisb
i1a
1j+b
i2a
2j+…+b
ina
nj,the
desiredresult.

58. Counting Paths
a-------b
| |
| |
c-------d
A=0110 A
4
=8008
1001 0880
1001 0880
0110 8008
Numberofpathsoflength4fromatodis(1,4)thentryofA
4
=8.

59. The Seven Bridges of Königsberg, Germany
TheresidentsofKönigsberg,Germany,wonderedifit
waspossibletotakeawalkingtourofthetownthat
crossedeachofthesevenbridgesoverthePreselriver
exactlyonce.Isitpossibletostartatsomenodeand
takeawalkthatuseseachedgeexactlyonce,and
endsatthestartingnode?

60. The Seven Bridges of Königsberg, Germany
Youcanredrawtheoriginalpictureaslongasforeveryedgebetween
nodesiandjintheoriginalyouputanedgebetweennodesiandjin
theredrawnversion(andyouputnootheredgesintheredrawn
version).
Original:
2
3
4 1
Redrawn:
4
2 3

61. The Seven Bridges of Königsberg, Germany
Has no tour that uses each edge exactly once.
(Even if we allow the walk to start and finish in different places.)
Can you see why?
Euler:

62. Euler -definitions
AnEulerianpath(Euleriantrail,Eulerwalk)inagraphisa
paththatuseseachedgepreciselyonce.Ifsuchapathexists,
thegraphiscalledtraversable.
AnEuleriancycle(Euleriancircuit,Eulertour)inagraph
isacyclethatuseseachedgepreciselyonce.Ifsuchacycle
exists,thegraphiscalledEulerian(alsounicursal).
Representationexample:G1hasEulerpatha,c,d,e,b,d,a,b
a b
c d e

63. The problem in our language:
Show that is not Eulerian.
In fact, it contains no Euler trail.

64. Euler -theorems
1.AconnectedgraphGisEulerianifandonlyifGisconnected
andhasnoverticesofodddegree
2.AconnectedgraphGishasanEulertrailfromnodeato
someothernodebifandonlyifGisconnectedandabare
theonlytwonodesofodddegree

65. Euler –theorems (=>)
AssumeGhasanEulertrailTfromnodeatonodeb(aandb
notnecessarilydistinct).
For every node besides aand b, Tuses an edge to exit for each
edge it uses to enter. Thus, the degree of the node is even.
1.If a=b, then aalso has even degree. Euler circuit
2.If ab, then aand bboth have odd degree. Euler path

66. Euler -theorems
1.AconnectedgraphGisEulerianifandonlyifGisconnected
andhasnoverticesofodddegree
a b
c d
e
f
Building a simple path:
{a,b}, {b,c}, {c,f}, {f,a}
Euler circuit constructed if all edges
are used. True here?

67. Euler -theorems
1.AconnectedgraphGisEulerianifandonlyifGisconnected
andhasnoverticesofodddegree
c d
e
Delete the simple path:
{a,b}, {b,c}, {c,f}, {f,a}
C is the common vertex for this
sub-graph with its “parent”.

68. Euler -theorems
1.AconnectedgraphGisEulerianifandonlyifGisconnected
andhasnoverticesofodddegree
c d
e
Constructed subgraph may not be connected.
C is the common vertex for this sub-graph
with its “parent”.
C has even degree.
Start at c and take a walk:
{c,d}, {d,e}, {e,c}

69. Euler -theorems
1.AconnectedgraphGisEulerianifandonlyifGisconnected
andhasnoverticesofodddegree
a b
c d
e
f
“Splice” the circuits in the 2 graphs:
{a,b}, {b,c}, {c,f}, {f,a}
“+”
{c,d}, {d,e}, {e,c}
“=“
{a,b}, {b,c}, {c,d}, {d,e}, {e,c}, {c,f}
{f,a}

70. Euler Circuit
1.CircuitC:=acircuitinGbeginningatanarbitrary
vertexv.
1.Addedgessuccessivelytoformapaththatreturnstothis
vertex.
2.H:=G–abovecircuitC
3.WhileHhasedges
1.Sub-circuitsc:=acircuitthatbeginsatavertexinHthat
isalsoinC(e.g.,vertex“c”)
2.H:=H–sc(-allisolatedvertices)
3.Circuit:=circuitC“spliced”withsub-circuitsc
4.CircuitChastheEulercircuit.

71. Representation-Incidence Matrix
e
1 e
2 e
3
a 1 0 0
b 1 1 0
c 0 1 1
d 0 0 1
e 0 0 0
f 0 0 0
a b
c d
e
f
e1
e2
e3
e4
e5
e6
e7
e4 e
5e
6 e
7
0 0 0 1
0 0 0 0
0 1 1 0
1 0 0 0
1 1 0 0
0 0 1 1

72. Homework 1
WriteaprogramtoobtainEulerCircuits.
InputgraphscanbeEulerian,noneedforchecking“non”
Eulergraphs
Includeasimpleuserinterfaceto“input”thegraph.
Minimumof10edges(nomorethan15edgesneeded)
Simpledocumentation
Includeasamplegraph,ifneeded,totest
Anyprogramminglanguage
SubmissiononWebCT
DueonJanuary27
th
11.55pm.

73. Hamiltonian Graph
Hamiltonianpath(alsocalledtraceablepath)isapaththatvisits
eachvertexexactlyonce.
AHamiltoniancycle(alsocalledHamiltoniancircuit,vertextouror
graphcycle)isacyclethatvisitseachvertexexactlyonce(exceptfor
thestartingvertex,whichisvisitedonceatthestartandonceagainat
theend).
AgraphthatcontainsaHamiltonianpathiscalledatraceablegraph.
AgraphthatcontainsaHamiltoniancycleiscalledaHamiltonian
graph.AnyHamiltoniancyclecanbeconvertedtoaHamiltonianpath
byremovingoneofitsedges,butaHamiltonianpathcanbeextended
toHamiltoniancycleonlyifitsendpointsareadjacent.

74. A graph of the vertices of a dodecahedron.
Is it Hamiltonian?
Yes
.

75. ThisonehasaHamiltonianpath,butnota
Hamiltoniantour.
Hamiltonian Graph

76. Hamiltonian Graph
This one has an Euler tour, but no Hamiltonian path.

77. Hamiltonian Graph
Similarnotionsmaybedefinedfordirectedgraphs,whereedges(arcs)
ofapathoracyclearerequiredtopointinthesamedirection,i.e.,
connectedtail-to-head.
TheHamiltoniancycleproblemorHamiltoniancircuitproblemingraph
theoryistofindaHamiltoniancycleinagivengraph.TheHamiltonian
pathproblemistofindaHamiltonianpathinagivengraph.
Thereisasimplerelationbetweenthetwoproblems.TheHamiltonian
pathproblemforgraphGisequivalenttotheHamiltoniancycle
probleminagraphHobtainedfromGbyaddinganewvertexand
connectingittoallverticesofG.
BothproblemsareNP-complete.However,certainclassesofgraphs
alwayscontainHamiltonianpaths.Forexample,itisknownthatevery
tournamenthasanoddnumberofHamiltonianpaths.

78. Hamiltonian Graph
DIRAC’STheorem:ifGisasimplegraphwithn
verticeswithn≥3suchthatthedegreeofevery
vertexinGisatleastn/2thenGhasaHamilton
circuit.
ORE’STheorem:ifGisasimplegraphwithn
verticeswithn≥3suchthatdeg(u)+deg(v)≥n
froeverypairofnonadjacentverticesuandvinG,
thenGhasaHamiltoncircuit.

79. Shortest Path
Generalize distance to weighted setting
Digraph G= (V,E) with weight function W: ER (assigning
real values to edges)
Weight of path p= v
1v
2… v
kis
Shortest path = a path of the minimum weight
Applications
static/dynamic network routing
robot motion planning
map/route generation in traffic1
1
1
( ) ( , )
k
ii
i
w p w v v





80. Shortest-Path Problems
Shortest-Path problems
Single-source (single-destination). Find a
shortest path from a given source (vertex s) to
each of the vertices. The topic of this lecture.
Single-pair. Given two vertices, find a shortest
path between them. Solution to single-source
problem solves this problem efficiently, too.
All-pairs. Find shortest-paths for every pair of
vertices. Dynamic programming algorithm.
Unweighted shortest-paths –BFS.

81. Optimal Substructure
Theorem: subpaths of shortest paths
are shortest paths
Proof (”cut and paste”)
if some subpath were not the shortest
path, one could substitute the shorter
subpath and create a shorter total path

82. Negative Weights and Cycles?
Negative edges are OK, as long as there are no
negative weight cycles (otherwise paths with
arbitrary small “lengths” would be possible)
Shortest-paths can have no cycles (otherwise we
could improve them by removing cycles)
Any shortest-path in graph Gcan be no longer
than n –1 edges, where nis the number of
vertices

83. Shortest Path Tree
The result of the algorithms –a shortest path tree. For each
vertex v, it
records a shortest path from the start vertex s to v.
v.parent() gives a predecessor of v in this shortest path
gives a shortest path length from s to v, which is recorded in
v.d().
The same pseudo-code assumptions are used.
VertexADT with operations:
adjacent():VertexSet
d():int and setd(k:int)
parent():Vertex and setparent(p:Vertex)

84. Relaxation
For each vertex v in the graph, we maintain v.d(), the estimate
of the shortest path from s, initialized to at the start
Relaxing an edge (u,v) means testing whether we can improve
the shortest path to vfound so far by going through u
5
u v
vu
2
2
9
5 7
Relax(u,v)
5
u v
vu
2
2
6
5 6
Relax(u,v)
Relax(u,v,G)
if v.d() > u.d()+G.w(u,v) then
v.setd(u.d()+G.w(u,v))
v.setparent(u)

85. Dijkstra's Algorithm
Non-negative edge weights
Greedy, similar to Prim's algorithm for MST
Like breadth-first search (if all weights = 1, one can simply use
BFS)
Use Q, a priority queue ADT keyed by v.d() (BFS used FIFO
queue, here we use a PQ, which is re-organized whenever some
ddecreases)
Basic idea
maintain a set Sof solved vertices
at each step select "closest" vertex u, add it to S, and relax
all edges from u

86. Dijkstra’s ALgorithm
Solution to Single-source (single-destination).
Input: Graph G, start vertex s
relaxing
edges
Dijkstra(G,s)
01foreachvertexuG.V()
02 u.setd()
03 u.setparent(NIL)
04s.setd(0)
05S //SetSisusedtoexplainthe
algorithm
06Q.init(G.V())//QisapriorityqueueADT
07whilenotQ.isEmpty()
08 uQ.extractMin()
09 SS{u}
10 foreachvu.adjacent()do
11 Relax(u,v,G)
12 Q.modifyKey(v)

87. Dijkstra’s Example
 
 
0s
u v
yx
10
5
1
23
9
46
7
2
10 
5 
0s
u v
yx
10
5
1
23
9
46
7
2
Dijkstra(G,s)
01foreachvertexuG.V()
02 u.setd()
03 u.setparent(NIL)
04s.setd(0)
05S
06Q.init(G.V())
07whilenotQ.isEmpty()
08 uQ.extractMin()
09 SS{u}
10 foreachvu.adjacent()do
11 Relax(u,v,G)
12 Q.modifyKey(v)

88. Dijkstra’s Example
u v
8 14
5 7
0s
yx
10
5
1
23
9
46
7
2
8 13
5 7
0s
u v
yx
10
5
1
23
9
46
7
2
Dijkstra(G,s)
01foreachvertexuG.V()
02 u.setd()
03 u.setparent(NIL)
04s.setd(0)
05S
06Q.init(G.V())
07whilenotQ.isEmpty()
08 uQ.extractMin()
09 SS{u}
10 foreachvu.adjacent()do
11 Relax(u,v,G)
12 Q.modifyKey(v)

89. Dijkstra’s Example
8 9
5 7
0
u
v
yx
10
5
1
23
9
46
7
2
8 9
5 7
0
u v
yx
10
5
1
23
9
46
7
2
Dijkstra(G,s)
01foreachvertexuG.V()
02 u.setd()
03 u.setparent(NIL)
04s.setd(0)
05S
06Q.init(G.V())
07whilenotQ.isEmpty()
08 uQ.extractMin()
09 SS{u}
10 foreachvu.adjacent()do
11 Relax(u,v,G)
12 Q.modifyKey(v)

90. Dijkstra’s Algorithm
O(n
2
) operations
(n-1) iterations: 1 for each vertex added to
the distinguished set S.
(n-1) iterations: for each adjacent vertex of
the one added to the distinguished set.
Note: it is single source –single
destination algorithm

91. Traveling Salesman Problem
Given a number of cities and the costs of traveling from one to
the other, what is the cheapest roundtrip route that visits each
city once and then returns to the starting city?
An equivalent formulation in terms of graph theory is: Find the
Hamiltonian cycle with the least weight in a weighted graph.
It can be shown that the requirement of returning to the
starting city does not change the computational complexity of
the problem.
A related problem is the (bottleneck TSP): Find the Hamiltonian
cycle in a weighted graph with the minimal length of the longest
edge.

92. Planar Graphs
 Agraph(ormultigraph)GiscalledplanarifGcanbedrawnintheplanewith
itsedgesintersectingonlyatverticesofG,suchadrawingofGiscalledan
embeddingofGintheplane.
Application Example: VLSI design (overlapping edges requires extra layers),
Circuit design (cannot overlap wires on board)
Representation examples: K1,K2,K3,K4 are planar, Knfor n>4 are non-planar
K
4

93. Planar Graphs
Representation examples: Q
3

94. Planar Graphs
Representation examples: K
3,3is Nonplanar
v
1 v
2
v
5v
4
v
3
v
6
v
1
v
2v
4
v
4
v
5 v
1
v
2
v
5
v
3
R
1
R
2
R
21
R
1
R
22

95. Theorem :Euler's planar graph theorem
For a connectedplanar graph or multigraph:
v –e + r = 2
number
of vertices
number
of edges
number
of regions
Planar Graphs

96. Planar Graphs
Example of Euler’s theorem
K
4
R1
R2
R3
A planar graph divides the plane
into several regions (faces), one
of them is the infinite region.
v=4,e=6,r=4, v-e+r=2
R4

97. Planar Graphs
Proof of Euler’s formula: By Induction
Base Case:for G1 , e
1= 1, v
1= 2 and r
1= 1
n+1 Case:Assume, r
n= e
n–v
n+ 2 is true. Let {an+1, bn+1} be the
edge that is added to Gn to obtain Gn+1 and we prove that r
n= e
n–
v
n+ 2 is true. Can be proved using two cases.
R1
v
u

98. Planar Graphs
Case 1:
r
n+1= r
n + 1, e
n+1= e
n + 1, v
n+1= v
n=> r
n+1= e
n+1–v
n+1+ 2
R
a
n+1
b
n+1

99. Planar Graphs
Case 2:
r
n+1= r
n, e
n+1= e
n + 1, v
n+1= v
n + 1 => r
n+1= e
n+1–v
n+1+ 2
R
a
n+1
b
n+1

100. Planar Graphs
Corollary 1:Let G = (V, E) be a connected simple planar graph with
|V| = v, |E| = e > 2, and r regions. Then 3r ≤ 2e and e ≤ 3v –6
Proof:SinceGisloop-freeandisnotamultigraph,theboundaryof
eachregion(includingtheinfiniteregion)containsatleastthree
edges.Hence,eachregionhasdegree≥3.
Degreeofregion:No.ofedgesonitsboundary;1edgemayoccur
twiceonboundary->contributes2totheregiondegree.
Eachedgeoccursexactlytwice:eitherinthesameregionorin2
differentregions
R
a
n+1
b
n+1

101. Region Degree
R
R
Degree of R = 3
Degree of R = ?

102. Planar Graphs
Eachedgeoccursexactlytwice:eitherinthesameregionorin2
differentregions
2e=sumofdegreeofrregionsdeterminedby2e
2e≥3r.(sinceeachregionhasadegreeofatleast3)
r≤(2/3)e
FromEuler’stheorem,2=v–e+r
2≤v–e+2e/3
2≤v–e/3
So6≤3v–e
ore≤3v–6

103. Planar Graphs
Corollary 2:Let G = (V, E) be a connected simple planar graph then
G has a vertex degree that does not exceed 5
Proof:IfGhasoneortwoverticestheresultistrue
IfGhas3ormoreverticesthenbyCorollary1,e≤3v–6
2e≤6v–12
Ifthedegreeofeveryvertexwereatleast6:
byHandshakingtheorem:2e=Sum(deg(v))
2e≥6v.Butthiscontradictstheinequality2e≤6v–12
Theremustbeatleastonevertexwithdegreenogreaterthan5

104. Planar Graphs
Corollary 3:Let G = (V, E) be a connected simple planar graph with
v vertices ( v ≥ 3) , e edges, and no circuits of length 3 then e ≤ 2v
-4
Proof:SimilartoCorollary1exceptthefactthatnocircuitsoflength
3implythatdegreeofregionmustbeatleast4.

105. Planar Graphs
Elementarysub-division:Operationinwhichagraphare
obtainedbyremovinganedge{u,v}andaddingthevertexw
andedges{u,w},{w,v}
Homeomorphic Graphs:GraphsG1andG2aretermedas
homeomorphiciftheyareobtainedbysequenceofelementary
sub-divisions.
u v u vw

106. Planar Graphs
Kuwratoski’sTheorem:Agraphisnon-planarifandonlyifit
containsasubgraphhomeomorephictoK
3,3orK
5
RepresentationExample:GisNonplanar
a
b
c
j
d
i
e
g
f
k
ba
c
e
d
fg
h
G
H
K
5
e
d
c
b
a

107. Graph Coloring Problem
Graphcoloringisanassignmentof"colors",almostalways
takentobeconsecutiveintegersstartingfrom1withoutlossof
generality,tocertainobjectsinagraph.Suchobjectscanbe
vertices,edges,faces,oramixtureoftheabove.
Applicationexamples:scheduling,registerallocationina
microprocessor,frequencyassignmentinmobileradios,and
patternmatching

108. Vertex Coloring Problem
Assignmentofcolorstotheverticesofthegraphsuchthatproper
coloringtakesplace(notwoadjacentverticesareassignedthesame
color)
Chromaticnumber:leastnumberofcolorsneededtocolorthegraph
Agraphthatcanbeassigneda(proper)k-coloringisk-colorable,and
itisk-chromaticifitschromaticnumberisexactlyk.

109. Vertex Coloring Problem
The problem of finding a minimum coloring of a graph is NP-Hard
The corresponding decision problem (Is there a coloring which uses at
most kcolors?) is NP-complete
The chromatic number for C
n= 3 (n is odd) or 2 (n is even), K
n= n,
K
m,n= 2
Cn: cycle with n vertices; Kn: fully connected graph with n vertices;
Km,n: complete bipartite graph
C
5
K
4 K
2, 3
C
4

110. Vertex Covering Problem
The Four color theorem:the chromatic number of a planar
graph is no greater than 4
Example: G1 chromatic number = 3, G2 chromatic number = 4
(Most proofs rely on case by case analysis).
G1 G2