A function f A B
: → is invertible if and only if it is both one-to-one and
onto.
33. Define a Graph.
A graph a consists of a finite set V of object called “Vertices”, a
finite set E of objects called “Edges” and a function γ that assigns to
each edge a subset {v, w}, where v and w are vertices. Here we have
G V E
= ( , , )
γ .
34. Define degree of a vertex.
Degree of a vertex is defined as the number of edges having that
vertex as an end point.
35. What is an isolated vertex?
A vertex with zero as degree is called an Isolated vertex.
36. What is a circuit?
A circuit is a path that begins and ends at the same vertex.
37. What is a connected graph?
A graph is called “connected” if there is a path from any vertex to
any other vertex in the graph.
38. When is a graph said to be a tree?
A graph is said to be a tree if it is connected and has no simple cycles.
39. When is a path called a cycle?
A path is a cycle if it starts and ends in the same node.
40. What is a directed graph?
A graph is said to be directed if it has arrows in stead of lines.
41. Define outdegree of a node.
The number of arrows pointing from a particular node is the
outdegree of that node.
42. Define Indegree of a node.
The number of arrows pointing to a particle node is the indegree.
43. Define Alphabet with an example.
Alphabet is defined as a finite set of symbols
Example: Roman Alphabet {a, b, .......... z}
44. Define a string.
A string over an alphabet is a finite sequence of symbols from that
alphabet, which is usually written next to one another and not separated
by commas.
45. Give examples for strings.
(a) If Σ a = { , }
0 1 then 001001 is a string over Σ a
(b) If Σ b
a b
z
= { , ,
}
KK then axyrpqstcd is a string over Σ b .
46. Define length of a string.
The length of a string is its length as a sequence. The length of a
string w is written as | w |.
Example: | 10011 | = 5.
Introduction
55
: → is invertible if and only if it is both one-to-one and
onto.
33. Define a Graph.
A graph a consists of a finite set V of object called “Vertices”, a
finite set E of objects called “Edges” and a function γ that assigns to
each edge a subset {v, w}, where v and w are vertices. Here we have
G V E
= ( , , )
γ .
34. Define degree of a vertex.
Degree of a vertex is defined as the number of edges having that
vertex as an end point.
35. What is an isolated vertex?
A vertex with zero as degree is called an Isolated vertex.
36. What is a circuit?
A circuit is a path that begins and ends at the same vertex.
37. What is a connected graph?
A graph is called “connected” if there is a path from any vertex to
any other vertex in the graph.
38. When is a graph said to be a tree?
A graph is said to be a tree if it is connected and has no simple cycles.
39. When is a path called a cycle?
A path is a cycle if it starts and ends in the same node.
40. What is a directed graph?
A graph is said to be directed if it has arrows in stead of lines.
41. Define outdegree of a node.
The number of arrows pointing from a particular node is the
outdegree of that node.
42. Define Indegree of a node.
The number of arrows pointing to a particle node is the indegree.
43. Define Alphabet with an example.
Alphabet is defined as a finite set of symbols
Example: Roman Alphabet {a, b, .......... z}
44. Define a string.
A string over an alphabet is a finite sequence of symbols from that
alphabet, which is usually written next to one another and not separated
by commas.
45. Give examples for strings.
(a) If Σ a = { , }
0 1 then 001001 is a string over Σ a
(b) If Σ b
a b
z
= { , ,
}
KK then axyrpqstcd is a string over Σ b .
46. Define length of a string.
The length of a string is its length as a sequence. The length of a
string w is written as | w |.
Example: | 10011 | = 5.
Introduction
55