UNIT III discrete mathematice notes availiable

notes

1. Graph theory
1

2. CONTENTS
Graph:BasicTerminologyandSpecialTypesof
Graphs,PathsandCircuits,Hamiltonianand
EulerPathsandCircuits,IsomorphicGraphs,
PlanerGraph,Dijkstra'sShortestPath
Algorithm.Trees:Trees,RootedTrees,Prefix
Codes,SpanningTrees,MinimumSpanning
Trees,Kruskal’sandPrim’sAlgorithmfor
MinimumSpanningTree.
2

3. Basic Terminology
Types of Graphs,
Paths
Circuits,
Hamiltonian and Euler Paths and
Circuits,
Isomorphic Graphs
Planer Graph
Dijkstra's Shortest Path Algorithm.
3
CMSC 203
-
Discrete Structures

4. INTRODUCTION TOGRAPHS
Definition:Agraphiscollectionofpointscalled
vertices&collectionoflinescallededges.
MathematicallygraphGisanorderedpairof(V,E)
Eachedgee
ijisassociatedwithanorderedpairof
vertices(V
i,V
j).
4

5. TYPESOFGRAPH:
There are basically two types of graphs, i.e., Undirected
graph and Directed graph.
Directed graph:
The directed graph can be made with the help of a set
of vertices, which are connected with the directed
edges. In the directed graph, the edges have a direction
which is associated with the vertices.
5

6. UNDIRECTEDGRAPH
The undirected graph can also be made of a set of
vertices which are connected together by the
undirected edges. All the edges of this graph are
bidirectional..
6

7. Null Graph:A graph will be known as the null
graph if it contains no edges. With the help of
symbol Nn, we can denote the null graph of n
vertices. The diagram of a null graph is described
as follows:
7
CMSC 203
-
Discrete Structures

8. SIMPLE& MULTIPLEGRAPHS
Definition:Agraphthathasneitherselfloopsor
paralleledgeiscalledasSimpleGraphotherwise
itiscalledasMultipleGraph.
ForExample,
G1(SimpleGraph) G2(MultipleGraph)
8

9. WEIGHTEDGRAPH
Definition:Ifeachedgeoreachvertexorbothare
associatedwithsomeweight(+veno.)thenthe
graphiscalledasWeightedGraph
9

10. SELFLOOPS& PARALLELEDGES
Definition:IftheendverticesV
i&V
jofanyedgee
ijaresame,
thenedgeeijcalledasSelfLoop.
ForExample,IngraphG,theedgee7isselfloop.
10

11. DEGREEOFAVERTEX(UNDIRECTEDGRAPH)
Definition: degree of a vertex is the number of edges
connecting to that vertex.
The degree of a vertex is indicated with the help of deg(v).
If there is a simple graph, which contains n number of
vertices,
11
Hence Deg(a) = 2Hence Deg(a) = 2
Deg(b) = 3
Deg(c) = 1
Deg(d) = 2.
Deg(a) = 0

12. DEGREEOFVERTEXINDIRECTEDGRAPH
number of edges coming to the vertex. With the help
of syntax deg
-
(v),
number of edges coming out from the vertex. With
the help of syntax deg
+
(v)
The degree of a vertex is equal to the addition of in-
degree of a vertex and out-degree of a vertex.
Deg(v)=deg-(v)+deg+(v)
12

13. 13
In-degree:
In-degree of a vertex a = deg(a) = 1
In-degree of a vertex b = deg(b) = 2
In-degree of a vertex c = deg(c) = 2
In-degree of a vertex d = deg(d) = 1
In-degree of a vertex e = deg(e) = 1
In-degree of a vertex f = deg(f) = 1
In-degree of a vertex g = deg(g) = 0
Out-degree:
Out-degree of a vertex a = deg(a) = 2
Out-degree of a vertex b = deg(b) = 0
Out-degree of a vertex c = deg(c) = 1
Out-degree of a vertex d = deg(d) = 1
Out-degree of a vertex e = deg(e) = 1
Out-degree of a vertex f = deg(f) = 1
Out-degree of a vertex g = deg(g) = 2

14. 14
In-degree
vertex a = deg(a) = 1
vertex b = deg(b) = 0
vertex c = deg(c) = 2
vertex d = deg(d) = 1
vertex e = deg(e) = 1
Out-degree:
vertex a = deg(a) = 1
vertex b = deg(b) = 2
vertex c = deg(c) = 0
vertex d = deg(d) = 1
vertex e = deg(e) = 1
Degree of a vertex a =
deg(a) = 1+1 = 2
Degree of a vertex b =
deg(b) = 0+2 = 2
Degree of a vertex c =
deg(c) = 2+0 = 2
Degree of a vertex d =
deg(d) = 1+1 = 2
Degree of a vertex e =
deg(e) = 1+1 = 2

15. MATRIXREPRESENTATIONOFGRAPHS
Agraphcanalsoberepresentedbymatrix.
Twowaysareusedformatrixrepresentationofgrapharegivenas
follows,
1.AdjacentMatrix
2.IncidentMatrix
Letsseeonebyone…
15

16. 1. ADJACENTMATRIX
a
ij=1,ifthereisasedgebetweenvi&vj.
a
ij=0,ifv
i&v
jarenotadjacent.
Aselfloopatvertexvicorrespondstoa
ij=1.
ForExample,
A(G)=
16

17. 2. INCIDENTMATRIX
GivenagraphGwithnvertices,eedges&noselfloops.The
incidencematrixx(G)=[X
ij]oftheothergraphGisann*ematrix
where,
X
ij=1,ifj
th
edgee
jisincidentoni
th
vertexv
i,
X
ij=0,otherwise.
Herenverticesarerows&eedgesarecolumns.
X(G)=
17

18. 1. ADJACENTMATRIX
TheA.M.ofmultigraphGwithnverticesisan
n*nmatrixA(G)=[a
ij]where,
a
ij=N,ifthereoneormoreedgearetherebetween
v
i&v
j&Nisno.ofedgesbetweenv
i&v
j.
a
ij=0,otherwise.
ForExample,
A(G)=
18

19. ADJACENCYMATRIXOFADIAGRAPH
Itisdefinedinsimilarfashionasitdefinedforundirectedgraph.
ForExample,
A(D)=
19

20. INCIDENTMATRIXOFDIAGRAPH
GivenagraphGwithn,e&noselfloopsismatrixx(G)=[X
ij]or
ordern*ewherenverticesarerows&eedgesarecolumnssuch
that,X
ij=1,ifjthedgee
jisincidentouti
th
vertexv
i
X
ij=-1,ifjthedgee
jisincidentintoi
th
vertexv
i
X
ij=0,ifjthedgee
jnotincidentoni
th
vertexv
i.
20

21. NULLGRAPH
Definition:Iftheedgesetofanygraphwithnverticesisanempty
set,thenthegraphisknownasnullgraph.
ItisdenotedbyN
nForExample,
N
3 N
4
21

22. PlanerGraph:Agraphwillbeknownas
theplanergraphifitisdrawninasingle
planeandthetwoedgesofthisgraphdonot
crosseachother.Inthisgraph,allthenodes
andedgescanbedrawninaplane.The
diagramofaplanergraphisdescribedas
follows:

22

23. Non-planergraph:Agivengraphwillbe
knownasthenon-planergraphifitisnot
drawninasingleplane,andtwoedgesof
thisgraphmustbecrossedeachother.The
diagramofanon-planergraphisdescribed
asfollows:
23

24. COMPLETEGRAPH
Definition:LetGbesimplegraphonnvertices.Ifthedegreeof
eachvertexis(n-1)thenthegraphiscalledascompletegraph.
Completegraphonnvertices,itisdenotedbyK
n.
IncompletegraphK
n,thenumberofedgesaren(n-1)/2,
For example,
24
K
1 K
2 K
3 K
4 K
5

25. REGULARGRAPH
Definition:Ifthedegreeofeachvertexissamesay‘r’inanygraph
Gthenthegraphissaidtobearegulargraphofdegreer.
Forexample,
25
K
3 K
4 K
5

26. ISOMORPHISM
Definition:Twographsarethoughtofasequivalent(called
isomorphic)iftheyhaveidenticalbehaviorintermsofgraph
theoreticproperties.
TwographsG(V,E)&G’(V’,E’)aresaidtobeisomorphictoeach
otherifthereisone-onecorrespondencebetweentheirvertices&
betweentheiredgessuchthatincidencerelationshipinpreserved.
ItisdenotedbyG1=G2
26

27. ISOMORPHISM
ForExample,
1 2 a b
4 3 d c
Itisimmediatelyapparentbydefinitionofisomorphismthattwo
isomorphicgraphsmusthave,
the same number of vertices,
the same number of edges, and
the same degrees of vertices.
27
b2
d3
c4
a1

28. SUBGRAPH
Definition:A sub graphof a graph G = (V, E) is a graph G’ = (V’,
E’) where V’V and E’E.
For Example:
G G1 G2
28

29. SPANNINGGRAPH
Definition:LetG=(V,E)beanygraph.ThenG’issaidtobethe
spanningsubgraphofthegraphGifitsvertexsetV’isequalto
vertexsetVofG.
For Example:
G G1 G2
29

30. COMPLEMENT OFAGRAPH
Definition:LetGisasimplegraph.ThencomplementofG
denotedby~GisgraphwhosevertexsetissameasvertexsetofG
&inwhichtwoverticesareadjacentif&onlyiftheyarenot
adjacentinG.ForExample:
G ~G H ~H
30

31. BIPARTITEGRAPH
Definition:AgraphG=(V,E)iscalledabipartitegraphifits
verticesVcanbepartitionedintotwosubsetsV
1and
V
2suchthateachedgeofGconnectsavertexofV
1toa
vertexV
2.ItisdenotedbyK
mn,wheremandnarethe
numbersofverticesinV
1andV
2respectively.
Agraphcannothaveselfloop.
31

32. Example:Draw thebipartitegraphsK
2,4and
K
3,4.Assuminganynumberofedges.
Solution:Firstdrawtheappropriatenumberofverticeson
twoparallelcolumnsorrowsandconnecttheverticesinone
columnorrowwiththeverticesinothercolumnorrow.The
bipartitegraphsK
2,4andK
3,4areshowninfigrespectively.

32

33. COMPLETEBIPARTITEGRAPH:
AgraphG=(V,E)iscalledacompletebipartite
graphifitsverticesVcanbepartitionedintotwo
subsetsV
1andV
2suchthateachvertexofV
1is
connectedtoeachvertexofV
2.Thenumberofedges
inacompletebipartitegraphism.naseachofthem
verticesisconnectedtoeachofthenvertices.
33

34. WALK:
34
Awalkcanbedefinedasasequenceofedgesandverticesofa
graph.Whenwehaveagraphandtraverseit,thenthattraverse
willbeknownasawalk.Inawalk,therecanberepeatededges
andvertices.Thenumberofedgeswhichiscoveredinawalk
willbeknownastheLengthofthewalk.Inagraph,therecanbe
morethanonewalk.
1.A,B,C,E,D(Numberoflength=4)
2.D,B,A,C,E,D,C(Numberoflength
=7)
3.E,C,B,A,C,E,D(Numberoflength
=6)

35. TYPESOFWALKS
35
There are two types of the walk, which are described as
follows:
Open walk
Closed walk
Closed walk =
A, B, C, D, E, C,
A
Open walk = A,
B, C, D, E, C
In case of the open walk and closed walk, the edges and vertices
can be repeated.

36. TRAILS
ATRAILCANBEDESCRIBED ASANOPENWALK
WHERE NOEDGEISALLOWED TOREPEAT.IN
THETRAILS,THEVERTEXCANBEREPEATED.
36
Trail=A,C,H,F,C,B
Closedtrail=A,C,H,
F,C,B,A

37. CIRCUIT
37
Acircuitcanbedescribedasaclosedwalkwherenoedgeis
allowedtorepeat.Inthecircuit,thevertexcanberepeated.A
closedtrailinthegraphtheoryisalsoknownasacircuit.
Twopointsareimportant,
Edgescannotberepeated
Vertexcanberepeated
Circuit:A,B,D,C,F,H,C,A

38. PATH:
38
Apathisatypeofopenwalkwhereneitheredgesnorverticesare
allowedtorepeat.Thereisapossibilitythatonlythestartingvertex
andendingvertexarethesameinapath.
Soforapath,thefollowingtwopointsareimportant,whichare
describedasfollows:
Edgescannotberepeated
Vertexcannotberepeated
Path:F,H,C,A,B,D

39. CYCLE:
39
AclosedpathinthegraphtheoryisalsoknownasaCycle.A
cycleisatypeofclosedwalkwhereneitheredgesnorvertices
areallowedtorepeat.Thereisapossibilitythatonlythestarting
vertexandendingvertexarethesameinacycle.
Soforacycle,thefollowingtwopointsareimportant,whichare
describedasfollows:
Edgescannotberepeated
Vertexcannotberepeated
Cycle:A,B,D,C,A

40. 40
CMSC 203
-
Discrete Structures

41. 41
A, B, G, F, C, D Trailbecause there is no repeated edge in the sequence
B, G, F, C, B, G, A Walkbecause the sequence contains the repeated edges and
vertices.
C, E, F, C Cyclebecause the sequence does not contain any repeated vertex or
edge except the starting vertex C.
C, E, F, C, E Walkbecause the sequence contains the repeated edges and
vertices.
A, B, F, A Not a Walkbecause there is no direct path to go from B to F. That's
why we can say that the sequence ABFA is not a Walk.
F, D, E, C, B Pathbecause the sequence does not contain any repeated edges
and vertices.

42. HAMILTONIANPATH
42
CMSC 203
-
Discrete Structures
A connected graph is said to be Hamiltonian if it contains each
vertex of G exactly once. Such a path is called aHamiltonian path.
Example
Hamiltonian Path− e-d-b-a-c.

43. 43
EulerPath:
AEulerPaththroughagraphisapathwhoseedgelistcontainseach
edgeofthegraphexactlyonce.
EulerCircuit:AnEulerCircuitisapaththroughagraph,inwhichthe
initialvertexappearsasecondtimeastheterminalvertex.
EulerGraph:AnEulerGraphisagraphthatpossessesaEulerCircuit.
AEulerCircuituseseveryedgeexactlyonce,butverticesmaybe
repeated.

44. 44
•Graphs are used to define theflow of computation.
•Graphs are used to representnetworks of
communication.
•Graphs are used to representdata organization.
•Graph transformation systems work on rule-based in-
memory manipulation of graphs. Graph databases
ensuretransaction-safe, persistent storing and
querying of graph structured data.
•Graph theory is used to findshortest path in roador a
network.
•InGoogle Maps, various locations are represented as
vertices or nodes and the roads are represented as edges
and graph theory is used to find the shortest path
between two nodes.

45. 45
Atreeisanacyclicgraphorgraphhavingno
cycles.Atreeorgeneraltreesisdefinedasa
non-emptyfinitesetofelementscalled
verticesornodeshavingthepropertythat
eachnodecanhaveminimumdegree1and
maximumdegreen

46. PROPERTIESOFTREES:
46
•There is only one path between each pair
of vertices of a tree.
•If a graph G there is one and only one
path between each pair of vertices G is a
tree.
•A tree T with n vertices has n-1 edges.
•A graph is a tree if and only if it a
minimal connected.

47. 47
RootedTrees:
Ifadirectedtreehasexactlyonenodeorvertexcalledroot
whoseincomingdegreesis0andallotherverticeshave
incomingdegreeone,thenthetreeiscalledrootedtree.

48. 48
CMSC 203
-
Discrete Structures

49. 49
For example, a code with code words {9,
55} has the prefix property; a code
consisting of {9, 5, 59, 55} does not,
because "5" is a prefix of "59" and also of
"55".

50. 50
CMSC 203
-
Discrete Structures

51. 51
A minimum spanning tree of G is a tree whose total weight is
as small as possible.
Kruskal'sAlgorithm to find a minimum spanning tree: This
algorithm finds the minimum spanning tree T of the given
connected weighted graph G.
•Input the given connected weighted graph G with n vertices
whose minimum spanning tree T, we want to find.
•Order all the edges of the graph G according to increasing
weights.
•Initialize T with all vertices but do include an edge.
•Add each of the graphs G in T which does not form a cycle
until n-1 edges are added.

52. 52

53. 53
CMSC 203
-
Discrete Structures

54. 54
The Edges of the
Graph
Edge Weight
Source Vertex Destination Vertex
E F 2
F D 2
B C 3
C F 3
C D 4
B F 5
B D 6
A B 7
A C 8
he next step that you will proceed with is arranging all edges in a sorted list by their
edge weights.

55. 55

56. 56

57. 57
choose an arbitrary
starting vertex A as
starting vertex. This
means it will be
included first in
your tree structure

58. 58
CMSC 203
-
Discrete Structures
connected edges going outward from node A and you will pick
the one with a minimum edge weight to include

59. 59
CMSC 203
-
Discrete Structures

60. 60
CMSC 203
-
Discrete Structures

61. 61

62. 62
CMSC 203
-
Discrete Structures

63. 63
ThesummationofalltheedgeweightsinMST
T(V’,E’)isequalto30,whichistheleastpossible
edgeweightforanypossiblespanningtree
structureforthisparticulargraph.

64. 64
Edges Weights Added or Not
(E, F) 1 Added
(A, B) 2 Added
(C, D) 2 Added
(B, C) 3 Added
(D, E) 3 Added
(B, D) 6 Not Added

65. 65
CMSC 203
-
Discrete Structures

66. 66

67. 67

68. 68

69. 69

70. 70

71. 71

72. 72

73. 73