Graph and Trees.pptGraph and Trees.ppt i detailed topic about graph and trees

Graph and Trees.ppt i detailed topic about graph and trees

1. 1
Muhammad Mohsin Saeed
Graphs and Trees

2. Simple Graph
Definition
A simple graph G = (V, E) consists of V, a
nonempty set of vertices, and E, a set of
unordered pairs of distinct elements of V
called edges.
2

3. A simple graph
3
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
How many vertices? How many edges?

4. A simple graph
4
V = { Chicago, Denver, Detroit, Los Angeles,
New York, San Francisco, Washington }
SET OF VERTICES
E = { {San Francisco, Los Angeles}, {San Francisco, Denver},
{Los Angeles, Denver}, {Denver, Chicago},
{Chicago, Detroit}, {Detroit, New York},
{New York, Washington}, {Chicago, Washington},
{Chicago, New York} }
SET OF EDGES

5. A simple graph
5
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
The network is made up of computers and telephone lines
between computers. There is at most 1 telephone line
between 2 computers in the network. Each line operates
in both directions.
These are undirected edges,
each of which connects two distinct vertices, and
no two edges connect the same pair of vertices.

6. A Non-Simple Graph
Definition
In a multigraph G = (V, E) two or more
edges may connect the same pair of
vertices.
6

7. A Multigraph
7
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
THERE CAN BE MULTIPLE TELEPHONE LINES
BETWEEN TWO COMPUTERS IN THE NETWORK.

8. Multiple Edges
8
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
Two edges are called multiple or parallel edges
if they connect the same two distinct vertices.

9. Another Non-Simple Graph
Definition
In a pseudograph G = (V, E) two or more edges
may connect the same pair of vertices, and in
addition, an edge may connect a vertex to itself.

9

10. A Pseudograph
10
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
THERE CAN BE TELEPHONE LINES IN THE NETWORK
FROM A COMPUTER TO ITSELF (for diagnostic use).

11. Loops
11
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
An edge is called a loop
if it connects a vertex to itself.

12. Undirected Graphs
12
pseudographs
simple graphs
multigraphs

13. A Directed Graph
Definition
In a directed graph G = (V, E) the edges
are ordered pairs of (not necessarily
distinct) vertices.
13

14. A Directed Graph
14
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
SOME TELEPHONE LINES IN THE NETWORK
MAY OPERATE IN ONLY ONE DIRECTION .
Those that operate in two directions are represented
by pairs of edges in opposite directions.

15. A Directed Multigraph
Definition
In a directed multigraph G = (V, E) the edges are
ordered pairs of (not necessarily distinct) vertices,
and in addition there may be multiple edges.
15

16. A Directed Multigraph
16
San Francisco
Denver
Los Angeles
New York
Chicago
Washington
Detroit
THERE MAY BE SEVERAL ONE-WAY LINES
IN THE SAME DIRECTION FROM ONE COMPUTER
TO ANOTHER IN THE NETWORK.

17. Types of Graphs
TYPE EDGES MULTIPLE EDGES LOOPS
ALLOWED? ALLOWED?
Simple graph Undirected NO NO
Multigraph Undirected YES NO
Pseudograph Undirected YES YES
Directed graph Directed NO YES
Directed multigraphDirected YES YES
17

18. Sub-graph
C
5 is a sub-graph of K
5
18
C
5
K
5

19. Union-graph
W
5 is the union of S
5 and C
5
19
C
5
W
5
S
5
a
b
c
e
d
a
c
e
a
b
c
e
d
a
b
c
e
d
f
f

20. Adjacency matrix
20
This graph has 6 vertices
a, b, c, d, e, f. We can
arrange them in that order. d
W
5
a
b
c
e a
c
e
f

21. Finding the adjacency matrix
21
a b c d e f
d
a 0 1 0 0 1 1
b
c
d
e
f
FROM
TO
There are edges from a to b, from a to e, and from a to f
W
5
a
b
c
e a
c
e
f

22. Finding the adjacency matrix
22
a b c d e f
d
a 0 1 0 0 1 1
b 1 0 1 0 0 1
c
d
e
f
FROM
TO
There are edges from b to a, from b to c, and from b to f
W
5
a
b
c
e a
c
e
f

23. Finding the adjacency matrix
23
a b c d e f
d
a 0 1 0 0 1 1
b 1 0 1 0 0 1
c 0 1 0 1 0 1
d
e
f
FROM
TO
There are edges from c to b, from c to d, and from c to f
W
5
a
b
c
e a
c
e
f

24. Finding the adjacency matrix
24
a b c d e f
a 0 1 0 0 1 1
b 1 0 1 0 0 1
c 0 1 0 1 0 1
d
e
f
FROM
TO
COMPLETE THE ADJACENCY MATRIX . . .
d
W
5
a
b
c
e a
c
e
f

25. Finding the adjacency matrix
25
a b c d e f
d
a 0 1 0 0 1 1
b 1 0 1 0 0 1
c 0 1 0 1 0 1
d 0 0 1 0 1 1
e 1 0 0 1 0 1
f 1 1 1 1 1 0
FROM
TO
Notice that this matrix is symmetric. That is a
ij = a
ji Why?
W
5
a
b
c
e a
c
e
f

26. Planar Graphs
A "planar graph" is
 a graph that can be drawn on a flat plane (like a piece of paper)
without any of its edges crossing each other, meaning all edges only intersect at
their endpoints where vertices are located;
 essentially, it's a graph that can be drawn
without edge intersections on a plane.
 
A graph is planar if it can be drawn in the plane without its edges crossing.
K4 is planar
K5 is NOT planar
K3,3 is NOT planar
K2,3 is planar
26

27. 27
Example

28. Example
A graph may be planar even if it
represents a 3-dimensional object.
28

29. 29
Coloring Graphs
A graph coloring is an assignment of
labels, called colors, to the vertices of
a graph such that no two adjacent
vertices share the same color.

30. Maps and Colors
Take a look at this map of the US

31. Maps and Colors
We can color in the states like this

32. Maps and Colors
This is a “proper” coloring because no two bordering
states are the same color

33. Maps and Colors
This coloring uses 6 colors; is it possible to color the
map with fewer colors?

34. Two Colors?
Can we use only two colors?

35. Two Colors?
We need to choose a color for Pennsylvania, say blue

36. Two Colors?
Since New York borders PA, we can’t use blue for NY, so
we need a
second color, say red

37. An Euler path in a graph is a path that travels
along every edge of the graph exactly once. An
Euler path might pass through individual
vertices of the graph more than once.
Euler Graph (pronounced oiler)
A Euler path is a
snowplow problem where
a snow plow needs to plow
every street exactly once
(with NO backtracking).

38. An Euler circuit (Graph) is a path that
travels along every edge exactly once (no
backtracking) AND starts and ends at the
same vertex.
Start and finish

39. Tree Terminology

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors

40. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
The node at the
top of a tree is
called its root

41. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
The links from a
node to its
successors are
called branches

42. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
The successors of
a node are called
its children

43. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
The predecessor
of a node is
called its parent

44. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
Each node in a tree
has exactly one
parent except for
the root node,
which has no
parent

45. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or
nodes, with each node linked to its successors
Nodes that have
the same parent
are siblings

46. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A node that has
no children is
called a leaf
node

47. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A node that has
no children is
called a leaf
node
Leaf nodes also
are known as
external nodes,
and nonleaf
nodes are known
as
internal nodes

48. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A generalization of the parent-child
relationship is the
ancestor-descendant relationship

49. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
dog is the
parent of cat
in this tree
A generalization of the parent-child
relationship is the
ancestor-descendant relationship

50. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
cat is the
parent of
canine in this
tree
A generalization of the parent-child
relationship is the
ancestor-descendant relationship

51. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
canine is a
descendant of
cat in this tree
A generalization of the parent-child
relationship is the
ancestor-descendant relationship

52. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
dog is an
ancestor of
canine in this
tree
A generalization of the parent-child
relationship is the
ancestor-descendant relationship

53. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A subtree of a
node is a tree
whose root is a
child of that
node

54. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A subtree of a
node is a tree
whose root is a
child of that
node

55. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
A subtree of a
node is a tree
whose root is a
child of that
node

56. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The level of a
node is
determined by
its distance from
the root

57. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The level of a
node is its
distance from
the root plus 1
Level 1
Level 2
Level 3

58. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The level of a
node is defined
recursively
Level 1
Level 2
Level 3

59. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The level of a
node is defined
recursively
Level 1
Level 2
Level 3
•If node n is the root of tree T, its level
is 1
•If node n is not the root of tree T, its
level is
1 + the level of its parent

60. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The height of a
tree is the
number of
nodes in the
longest path
from the root
node to a leaf
node

61. Tree Terminology (cont.)

dog
cat wolf
canin
e
A tree consists of a collection of elements or nodes,
with each node linked to its successors
The height of a
tree is the
number of
nodes in the
longest path
from the root
node to a leaf
node
The height
of this tree
is 3

62. 62
Tree traversal is a popular form of graph
traversal in the world of computer science
and data structures, and it is a procedure of
visiting each node of the tree. The
sequence in which the nodes are visited is
preferred to classify these traversals.
Tree Traversal

63. 63

64. 64

65. 65

66. 66
END OF COURSE