Question: What does it mean by the preservation of edge end
point function in the definition of isomorphism of
graphs?
Answer: Since you know that we are looking for two functions
(Suppose one function is “f” and other function is “g”)
which preserve the edge end point function and this
preservation means that if we have vi as an end point
of the edge ej then f(vi) must be an end point of the
edge g(ej) and also the converse that is if f(vi) be an
end point of the edge g(ej) then we must have vi as an
end point of the edge ej. Note that vi and ej are the
vertex and edge of one graph respectively where as f
(vi) and g (ej) are the vertex and edge in the other
graph respectively.
Question: Is there any method of identifying that the given
graphs are isomorphic or not?(With out finding out
two functions).
Answer: Unfortunately there is no such method which will
identify whether the given graphs are isomorphic or
not. In order to find out whether the two given graphs
are isomorphic first we have to find out all the
bijective mappings from the set vertices of one graph
to the set of vertices of the other graph then find out
all the bijective functions from the set of edges of
one graph to the set of edges of the other graph. Then
see which mappings preserve the edge end point
function as defined in the definition of Isomorphism
of graphs. But it is easy to identify that the two
graphs are not isomorphic. First of all note that if
there is any Isomorphic Invariant not satisfied by
both the graphs, then we will say that the graphs are
not Isomorphic. Note that if all the isomorphic
Invariants are satisfied by two graphs then we can’t
conclude that the graphs are isomorphic. In order to
prove that the graphs are isomorphic we have to find
out two functions which satisfied the condition as
defined in the definition of Isomorphism of graphs.
Question: What are Complementary Graphs?
Answer: Complementary Graph of a simple graph(G) is denoted
by the (G bar ) and has as many vertices as G but two
vertices are adjacent in complementary Graph by an
edge if and only if these two vertices are not adjacent
in G .
Question: What is the application of isomorphism in real word?
Answer: There are many applications of the graph theory in
computer Science as well as in the Practical life; some
of them are given below. (1) Now you also go through
the puzzles like that we have to go through these
points without lifting the pencil and without repeating
our path. These puzzles can be solved by the Euler and
Hamiltonian circuits. (2) Graph theory as well as Trees
has applications in “DATA STRUCTURE" in which you
will use trees, especially binary trees in manipulating
the data in your programs. Also there is a common
application of the trees is "FAMILY TREE”. In which
we represent a family using the trees. (3) Another
example of the directed Graph is "The World Wide
Web ". The files are the vertices. A link from one file
to another is a directed edge (or arc). These are the
few examples.
Question: Are Isomorphic graphs are reflexive, symmetric and
transitive?
Answer: We always talk about " RELXIVITY"" SYMMETRIC"
and TRANSIVITY of a relation. We never say that a
graph is reflexive, symmetric or transitive. But also
remember that we draw the graph of a relation which
is reflexive and symmetric and the property of
reflexivity and symmetric is evident from the graphs,
we can’t draw the graph of a relation such that
transitive property of the relation is evident. Now
consider the set of all graphs say it G, this being a
set ,so we can define a relation from the set G to
itself. So we define the relation of Isomorphism on
the set G x G.( By the definition of isomorphism) Our
claim is that this relation is an " Equivalence Relation"
which means that the relation of Isomorphism’s of two
graphs is "REFLEXIVE" "SYMMETRIC" and
"TRANSITIVE". Now if you want to draw the graph of
this relation, then the vertices of this graph are the
graphs from the set G.
Question: Why we can't use the same color in connected portions
of planar graph?
Answer: We define the coloring of graph in such a manner that
we can’t assign the same color to the adjacent vertices
because if we give the same colors to the adjacent
vertices then they are indistinguishable. Also note that
we can give the same color to the adjacent vertices but
such a coloring is called improper coloring and the way
which we define the coloring is known as the proper
coloring. We are interested in proper coloring that’s
why all the books consider the proper coloring
Question: What is meant by isomorphic invariant?
Answer: A property "P" of a graph is known as Isomorphic
invariant. if the same property is found in all the
graphs which are isomorphic to it. And all these
properties are called isomorphic invariant (Also it clear
from the words Isomorphic Invariant that the
properties which remain invariant if the two graphs
are isomorphic to each other).
Question: What is an infinite Face?
Answer: When you draw a Planar Graph on a plane it divides the
plane into different regions, these regions are known
as the faces and the face which is not bounded by the
edges of the graph is known as the Infinite face. In
other words the region which is unbounded is known as
Infinite Face.
Question: What is "Bipartite Graph”?
Answer: A graph is said to be Bipartite if it’s set of vertices
can be divided into two disjoint sets such that no two
vertices of the same set are adjacent by some edge of
the graph. It means that the edges of one set will be
adjacent with the vertices of the other set.
Question: What is chromatic number?
Answer: While coloring a graph you can color a vertex which is
not adjacent with the vertices you already colored by
choosing a new color for it or by the same color which
you have used for the vertices which are not adjacent
with this vertex. It means that while coloring a graph
you may have different number of colors used for this
purpose. But the least number of colors which are
being used during the coloring of Graphs is known as
the Chromatic number.
Question: What is the role of Discrete mathematics in our
prectical life. what advantages will we get by
learning it.
Answer: In many areas people have to faces many mathematical
problems which can,t be solved in computer so discrete
mathematics provide the facility to overcome these
problems. Discrete math also covers the wide range of
topics, starting with the foundations of Logic, Sets
and Functions. It moves onto integer mathematics and
matrices, number theory, mathematical reasoning,
probability graphs, tree data structures and Boolean
algebra.So that is why we need discrete math.
Question: What is the De Morgan's law .
Answer: De Morgan law states " Negation of the conjunction of
two statements is logiacally equivalent to the
disjunction of their negation and Negation of the
disjunction of two statements is logically equivalent to
the conjucnction of their negation". i.e. ~(p^q) = ~p v
~q and ~(p v q)= ~p ^ ~q For example: " The bus was
late and jim is waiting "(this is an example of
conjuction of two statements) Now apply neaggation on
this statement you will get through De Morgan's law "
The bus was not late or jim is not waiting" (this is the
disjunction of negation of two statements). Now see
both statement are logically equivalent.Thats what De
Morgan want to say
Question: What is Tauology?
Answer: A tautology is a statement form that is always true
regardless of the truth values of the statement
variables. i.e. If you want to prove that (p v q) is
tautology ,you have to show that all values of
statement (p v q) are true regardless of the values of
p and q.If all the values of the satement (p v q) is not
true then this statement is not tautology.
Question: What is binary relations and reflexive,symmetric
and transitive.
Answer: Dear student! First of all ,I will tell you about the
basic meaning of relation i.e It is a logical or natural
association between two or more things; relevance of
one to another; the relation between smoking and
heart disease. The connection of people by blood or
marriage. A person connected to another by blood or
marriage; a relative. Or the way in which one person or
thing is connected with another: the relation of parent
to child. Now we turn to its mathematically definition,
let A and B be any two sets. Then their cartesian
product (or the product set) means a new set "A x B "
which contains all the ordered pairs of the form (a,b)
where a is in set A and b is in set B. Then if we take
any subset say 'R' of "A x B" ,then 'R' is called the
binary relation. Note All the subsets of the Cartesian
product of two sets A and B are called the binary
relations or simply a relation,and denoted by R. And
note it that one raltion is also be the same as "A x B".
Example: Let A={1,2,3} B={a,b} be any two sets. Then
their Cartesian product means "A x B"={ (1,a),(1,b),
(2,a),(2,b),(3,a),(3,b) } Then take any set which
contains in "A x B" and denote it by 'R'. Let we take
R={(2,b),(3,a),(3,b)} form "A x B". Clearly R is a subset
of "A x B" so 'R' is called the binary relation. A
reflexive relation defined on a set say ‘A’ means “all
the ordered pairs in which 1st element is mapped or
related to itself.” For example take a relation say R1=
{(1,1), (1,2), (1,3), (2,2) ,(2,1), (3,1) (3,3)} from “A x B”
defined on the set A={1,2,3}. Clearly R1 is reflexive
because 1,2 and 3 are related to itself. A relation say
R on a set A is symmetric if whenever aRb then
bRa,that is ,if whenever (a,b) belongs to R then (b,a)
belongs to R for all a,b belongs to A. For example given
a relation which is R1={(1,1), (1,2), (1,3), (2,2) ,(2,1),
(3,1) (3,3)} as defined on a set A={1,2,3} And a relation
say R1 is symmetric if for every (a, b) belongs to R ,(b,
a) also belongs to R. Here as (a, b)=(1,1) belongs to R
then (b, a)=(1,1)also belongs to R. as (a,b)=(1,2) belongs
to R then (b,a)=(2,1)also belongs to R. as (a,b)=(1,3)
belongs to R then (b,a)=(3,1)also belongs to R.etc So
clearly the above relation R is symmetric. And read the
definition of transitive relation from the handouts and
the book. You can easily understand it.
Question: What is the matrix relation .
Answer: Suppose that A and B are finite sets.Then we take a
relation say R from A to B. From a rectangular array
whose rows are labeled by the elements of A and
whose columns are labeled by the elements of B. Put a
1 or 0 in each position of the array according as a
belongs to A is or is not related to b belongs to B. This
array is called the matrix of the relation. There are
matrix relations of reflexive and symmetric relations.
In reflexive relation, all the diagonal elements of
relation should be equal to 1. For example if R = {(1,1),
(1,3), (2,2), (3,2), (3,3)} defined on A = {1,2,3}. Then
clearly R is reflexive. Simply in making matrix relation
In the above example,as the defined set is A={1,2,3} so
there are total three elements. Now we take 1, 2 and 3
horizontally and vertically.i.e we make a matrix from
the relation R ,in the matrix you have now 3 columns
and 3 rows. Now start to make the matrix ,as you have
first order pair (1, 1) it means that 1 maps on itself and
you write 1 in 1st row and in first column. 2nd order
pair is (1, 3) it means that arrow goes from 1 to 3.Then
you have to write 1 in 1st row and in 3rd column. (2, 2)
means that arrow goes from 2 and ends itself. Here
you have to write 1 in 2nd row and in 2nd column. (3,2)
means arrow goes from 3 and ends at 2. Here you have
to write 1 in 3rd row and in 2nd column. (3, 3) means
that 3 maps on itself and you write 1 in 3rd row and in
3rd column. And where there is space empty or unfilled
,you have to write 0 there.
Question: what is binary relation.
Answer: Let A and B be any two sets. Then their cartesian
product(or the product set) means a new set "A x B "
which contains all the ordered pairs of the form (a,b)
where a is in set A and b is in set B. Let we take any
subset say 'R' of "A x B" ,then 'R' is called the binary
relation. Note it that 'R' also be the same as "A x B".
For example: Let A={1,2,3} B={a,b} be any two sets.
Then their cartesian product means "A x B"={ (1,a),
(1,b),(2,a),(2,b),(3,a),(3,b) } Then take any set which
contains in "A x B" and denote it by 'R'. Let R={(2,b),
(3,a),(3,b)} Clearly R is a subset of "A x B" so 'R' is
called the binary relation.
Question: Role of ''Discrete Mathematics'' in our prectical life.
what advantages will we get by learning it.
Answer: Discrete mathematics concerns processes that consist
of a sequence of individual steps. This distinguishes it
from calculus, which studies continuously changing
processes. While the ideas of calculus were
fundamental to the science and technology of the
industrial revolution, the ideas of discrete
mathematics underline the science and technology
specific to the computer age. Logic and proof: An
important goal of discrete mathematics is to develop
students’ ability to think abstractly. This requires that
students learn to use logically valid forms of argument,
to avoid common logical errors, to understand what it
means to reason from definition, and to know how to
use both direct and indirect argument to derive new
results from those already known to be true. Induction
and Recursion: An exciting development of recent
years has been increased appreciation for the power
and beauty of “recursive thinking”: using the
assumption that a given problem has been solved for
smaller cases, to solve it for a given case. Such
thinking often leads to recurrence relations, which can
be “solved” by various techniques, and to verifications
of solutions by mathematical induction. Combinatorics:
Combinatorics is the mathematics of counting and
arranging objects. Skill in using combinatorial
techniques is needed in almost every discipline where
mathematics is applied, from economics to biology, to
computer science, to chemistry, to business
management. Algorithms and their analysis: The word
algorithm was largely unknown three decades ago. Yet
now it is one of the first words encountered in the
study of computer science. To solve a problem on a
computer, it is necessary to find an algorithm or stepby-
step sequence of instructions for the computer to
follow. Designing an algorithm requires an
understanding of the mathematics underlying the
problem to be solved. Determining whether or not an
algorithm is correct requires a sophisticated use of
mathematical induction. Calculating the amount of time
or memory space the algorithm will need requires
knowledge of combinatorics, recurrence relations
functions, and O-notation. Discrete Structures:
Discrete mathematical structures are made of finite
or count ably infinite collections of objects that
satisfy certain properties. Those are sets, bolean of
algebras, functions, finite start automata, relations,
graphs and trees. The concept of isomorphism is used
to describe the state of affairs when two distinct
structures are the same intheir essentials and diffr
only in the labeling of the underlying objects.
Applications and modeling: Mathematics topic are best
understood when they are seen ina variety of contexts
and used to solve problems in a broad range of applied
situations. One of the profound lessons of
mathematics is that the same mathematical model can
be used to solve problems in situations that appear
superficially to be totally dissimilar. So in the end i
want to say that discrete mathematics has many uses
not only in computer science but also in the other
fields too.
Question: what is the basic difference b/w sequences and series
Answer: A sequence is just a list of elements .In sequnce we
write the terms of sequence as a list (seperated by
comma's). e.g 2,3,4,5,6,7,8,9,... ( in this we have terms
2,3,4,5,6,7,8,9 and so on).we write these in form of list
seperated by comma's. And the sum of the terms of a
sequence forms a series. e.g we have sequence
1,2,3,4,5,6,7 Now the series is sum of terms of
sequence as 1+2+3+4+5+6+7.
Question: what is the purpose of permutations?
Answer: Permutation is an arrangement of objects in a order
where repitition is not allowed. We need arrangments
of objects in real life and also in mathematical
problems.We need to know in how many ways we can
arrange certain objects. There are four types of
arrangments we have in which one is permutation.
Question: what is inclusion-exclusion principle
Answer: Inclusion-Exclusion principle contain two rules which
are If A and B are disjoint finite sets, then n(AEB) =
n(A) + n(B) And if A and B are finite sets, then n(AEB)
= n(A) + n(B) - n(ACB) For example If there are 15
girls students and 25 boys students in a class then how
many students are in total. Now see if we take A ={ 15
girl students} and B={ 25 boys students} Here A and B
are two disjoints sets then we can apply first rule
n(AEB) = n(A) + n(B) =15 + 25 =40 So in total there are
40 students in class. Take another Example for second
rule. How many integers from 1 through 1000 are
multiples of 3 or multiples of 5. Let A and B denotes
the set of integers from 1 through 1000 that are
multiples of 3 and 5 respectivly. n(A)= 333 n(B)=200
But these two sets are not disjoint because in A and B
we have those elements which are multiple of both 3
and 5. so n(ACB) =66 n(AEB) = n(A) + n(B) - n(ACB)
=333 + 200 - 66 = 467
Question: How to use conditional probobility
Answer: Dear student In Conditional probability we put some
condition on an event to be occur. e.g. A pair of dice is
tossed. Find the probability that one of the dice is 2 if
the sum is 6. If we have to find the probability that
one of the dice is 2, then it is the case of simple
probability. Here we put a condition that sum is six.
Now A = { 2 appears in atleast one die} E = {sum is 6 }
Here E = { (1,5), (2, 4), (3, 3), (4, 2), (5, 1) } Here two
order pairs ( 2, 4 ) and ( 4, 2) satisfies the A. (i.e.
belongs to A) Now A (intersection) B= { (2,4), (4,2)}
Now by formula P(A/E) = P(A (intersection) E)/ P(E) =
2/5
Question: In which condition we use combination and in which
condition permutation.
Answer: This depends on the statement of question. If in the
statement of question you finds out that repetition of
objects are not allowed and order matters then we use
Permutation. e.g. Find the number of ways that a party
of seven persons can arrange themselves in a row of
seven chairs. See in this question repetition is no
allowed because whenever a person is chosen for a
particular seat r then he cannot be chosen again and
also order matters in the arrangements of chairs so we
use permutation here. If in the question repetition of
samples are not allowed and order does not matters
then we use combination. A student is to answer eight
out of ten questions on an exam. Find the number m of
ways that the student can choose the eight questions
See in this question repetition is not allowed that is
when you choose one question then you cannot choose
it again and also order does not matters(i.e either he
solved Q1 first or Q2 first) so you use combination in
this question.
Question: What is the differnce between edge and vertex
Answer: Vertices are nodes or points and edges are lines/arcs
which are used to connect the vertices. e.g If you are
making the graph to find the shortest path or for nay
purpose of cites and roads between them which
contain Lahore Islamabad Faisalabad Karachi
them are edges.
Question: What is the differnce between yes and allowed in
graphs.
Answer: Allowed mean that specific property can be occurs in
that case but yes mean that specific property always
occurs in that case. e.g. In Walk you may start and end
at same point and may not be (allowed). But in Closed
Walk you have to start and end at same point (yes).
Question: what is the meanging of induction? and also
Mathematical Induction?
Answer: Basic meaning of induction is: a)The act or an instance
of inducting. b) A ceremony or formal act by which a
person is inducted, as into office or military service.
In Mathematics. A two-part method of proving a
theorem involving a positive integral variable. First the
theorem is verified for the smallest admissible value
of the integer. Then it is proven that if the theorem is
true for any value of the integer, it is true for the
next greater value. The final proof contains the two
parts. As you have studied. It also means that
presentation of material, such as facts or evidence, in
support of an argument or a proposition. Whether in
Physics Induction means the creation of a voltage or
current in a material by means of electric or magnetic
fields, as in the secondary winding of a transformer
when exposed to the changing magnetic field caused by
an alternating current in the primary winding. In
Biochemistry,it means that the process of initiating or
increasing the production of an enzyme or other
protein at the level of genetic transcription. In
embryology,it means that the change in form or shape
caused by the action of one tissue of an embryo on
adjacent tissues or parts, as by the diffusion of
hormones or chemicals.
By ADEEL ABBAS, Bhakkar. AdeelAbbasbk@gmail.com
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.