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

Discrete mathematics

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. ...

Read More »

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       ″     ...

Read More »

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 ...

Read More »

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 ...

Read More »

Let R be a transitive reflexive relation on A. Let T be a relation on A such that (a, b) ∊T if and only if both (a, b) ∊ T and (b, a) ∊ R. Show that T is equivalence relation.

Proof: For all a ∊ R, (a, a) ∊ R. Since R is reflexive. So according to problem (a, a) ∊ T. Suppose (a, b) ∊ T. Then by problem (a, b) ∊ R and (b, a) ∊ R ⇒ (b, a) ∊R and (a, b) ∊R ⇒ (b, a)∊ ...

Read More »

Let R be a symmetric and transitive relation on a set. Show that for every a in A there exist b in A such that (a, b) ∊ R then R is an equivalence relation.

Proof: For all a ∊ A, we have (a, b) ∊ R. Since R is symmetric, so (b, a) ∊ R Now, (a, b) ∊ R and (b, a) ∊ R imply that (a, a) ∊ R. Since R is transitive hence R is reflexive. Therefore R is an equivalence ...

Read More »