BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Tuesday , August 22 2017
Home / Discrete mathematics

Discrete mathematics

Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, let P={a} and T=v-{a}. For every vertex t in T. Let ℓ (t) = w(a, t) Select the vertex in T that has the smallest index with respect to P. Let x denote the vertex. ...

Euler’s formula for planner graphs| Discrete Mathematics

Proof: We have to proved V-E+R=2 for any connected planner graph. Where v, e, r are the number of vertices, edges and regions of the graph respectively. The proof proceeds by induction on the number of edges. As the basis of induction we observe that for the two graphs with ...

An undirected graph possess an Eulerian path if and only if, is connected and has either zero or two vertices of odd degree.

Proof: Suppose that the graph possess an eulerian path. That the graph must be connected is obvious. When the eulerian path is traced, we observe that every time the path meets a vertex, it goes through two edges which are incident with the vertex and have not been traced before. ...

A tree has two vertices of degree 2. One vertex of degree 3 and 3 vertices of degree 4.How many vertices of degree 1 does it have?

Exercise:A tree has 2n vertices of degree 1. 3n vertices of degree 2 and n vertices of degree 3. Determine the number of vertices and edges in the tree. Solution: 2n vertices has total degree = 2n× 1 = 2n 3n       ″      ″    ″      ″   = 3n×2 =6n n       ″     ...

Absorption Property, Idempotent Property| Discrete mathematics

Absorption Property: For any a, b in A, a˅(a˄b) =a and a˄(a˅b)=a Proof: Since a˅(a˄b) is the join of a and (a˄b) then , a˅(a˄b) ≥a ————————-(1) Since a≥a and a≥(a˄b) which implies that   (a˅a) ≥ a˅(a˄b) ⇒ a≥ a˅(a˄b) ———————————(2) From (1) and (2) we get, a˅(a˄b)=a Now ...

Both the join and meet operations are associative

Both the join and meet operations are associative i.e., a ˅(b˅c) =(a˅b) ˅c and a˄(b˄c)=(a˄b) ˄c Proof: We first show that, the join operation is associative i.e., a ˅(b˅c) =(a˅b) ˅c Let a ˅(b˅c) = g and (a˅b) ˅c=h Since g is the least upper bound of a and (b˅c) ...

Show that R is a partially ordering relation.

For a given set A, consider the relation R={(x,y)|x∊P(A), y∊P(A) and x≤y. Show that R is a partially ordering relation. Proof: For all a∊P(A), a≤a ⟹(a,a) ∊R, R is reflexive Let (a,b) ∊R and (b,a) ∊R then a≤b and b≤a implies that a=b. ∴ R is an anti-symmetric. Let (a,b) ...

Let R be a reflexive relation on a set A. Show that R is an equivalence relation if and only if (a,b) and (a,c) in R implies that (b,c) ∊R.

Proof: First we say that R is an equivalence relation. We have (a,b)∊R and (a,c) ∊R ⟹(b,a) ∊R and (a,c) ∊R [∵ R is symmetric] ⟹(b,c) ∊R Conversely, we suppose that (b,c) ∊R Given that R is reflexive. Let (a,b) ∊R, then there exist x∊A such that (x,a) ∊R and ...