MINIMUM SPANNING TREE PROBLEM

QUESTION 1

QUESTION 2

QUESTION 3

 QUESTION 4

 QUESTION 5

 QUESTION 6

CASE STUDY PROBLEMS : MODERN CORP. PROBLEM

     Management of the modern Corp. has decided to have a state-of-the-art fiber-optic network install to provide high-speed communications (data, voice, and video) between major centers.

     The nodes in figure 1 show the geographical layout of the corporation’s major centers which include corporate headquarters, a supercomputer facility, and a research park, as well as production and distribution centers. The dashed lines are potential locations of fiber-optic cables. The number next to each dashed line gives the cost (in millions of dollars) if that particular cable chosen as one to be installed.

Figure 1: A display of Modern Corp.'s major centers (nodes), the possible locations for fiber-optic cables(the dashed line), and the cost in million of dollars for those cables (the numbers).

A) Determine which cables should be installed to minimize the total cost of providing high-speed communications between every pair of centers?

n = 7

n-1 = 6

B)Explain the reason for the name of minimum spanning-tree.

     

    Every nodes now is touched by a link, so the algorithm is done and this is the optimal solution. All the links that have been inserted into the network form a minimum spanning tree with a total cost 2+4+1+3+1+5 = 16 millions.

CASE STUDY PROBLEMS : WIREHOUSE LUMBER COMPANY

The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt roads that makes each grove accessible from every other grove. The distance(in miles) between every pair of groves is as follows:

Grove	Distance between Pairs of  Groves
	1	2	3	4	5	6	7	8
1	-	1.3	2.1	0.9	0.7	1.8	2.0	1.5
2	1.3	-	0.9	1.8	1.2	2.6	2.3	1.1
3	2.1	0.9	-	2.6	1.7	2.5	1.9	1.0
4	0.9	1.8	2.6	-	0.7	1.6	1.5	0.9
5	0.7	1.2	1.7	0.7	-	0.9	1.1	0.8
6	1.8	2.6	2.5	1.6	0.9	-	0.6	1.0
7	2.0	2.3	1.9	1.5	1.1	0.6	-	0.5
8	1.5	1.1	1.0	0.9	0.8	1.0	0.5	-

Management now wants to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.

a. Describe how this problem fits the network description of a minimum spanning tree problem.   

answer:

1. Choose of the first link: Select the cheapest potential link.
2.  Choose of the next link: Select the cheapest potential link between a node that already is touched by a link and a node that does not yet have such a link.
3.  Repeat step 2 over and over until every node is touched by a link (perhaps more than one). At that point, an optimal solution (a minimum spanning tree) has been obtained.

b. Use the suitable algorithm to solve this problem.

answer :

n = 8

n -1 = 7

total distance = 0.5 + 0.6 + 0.8 + 0.7+ 0.7 + 0.9 + 1.0

                                = 5.2 miles

References:

http://www.springerlink.com/content/r81g0gvkw32wu841/

http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml

http://www.ics.uci.edu/~eppstein/161/960206.html

BASIC DEFINITIONS

1)     Set: A well-defined collection of distinct objects is called a set.

2)     Notation of Sets: Capital letters are usually used to denote or represent a set.

3)     Representation of Sets: There are two methods of representing a set. 
     (i) Roster Method 
     (ii) Set builder form.

4)     Finite and Infinite Sets: A set is finite if it contains a specific number of elements. Otherwise, a set is an infinite set.

5)     Null Set or Empty Set or Void Set: A set with no elements is an empty set .Denoted by { } or  Ø

6)     Equivalent Sets: Two finite sets A and B are said to be equivalent sets if cardinality of both sets are equal
     i.e. n (A) = n (B).

7)     Equal Sets: Two sets A and B are said to be equal if and only if they contain the same elements 
    i.e. if every element of A is in B and every element of B is in A. We denote the equality by A = B.

8)    Cardinality of a Set A: The number of elements in a finite set A, is the cardinality of A and is denoted by n(A).

9)     Universal Set: In any application of the theory of sets, the members of all sets under consideration usually belong to some fixed large set called the universal set.

10)  Subsets: If A and B are sets such that each element of A is an element of B, then we say that A is a subset of B and write A Í B.

11)  Power Set: The family of all subsets of any set S is called the power set of S. We denote the power set of S by P (S).

Set of number.

 i)  set of natural numbers , N={ 0,1,2,3,4, … }

ii) set  of positive integers, P={ 1, 2, 3, 4, … }

iii) set of all integers, Z= { …., -3, -2,-1,0,1,2,3,… }

iv) set of all real numbers, R= { …, -3, -2.5, -1/2, 0, 1, 3/2, … }

APPLICATION OF SET

       Set theory is seen as the foundation from which virtually all of mathematics can be derived. For example, structures in abstract algebra, such as groups, fields and rings, are sets closed under one or more operations.

       One of the main applications of naive set theory is constructing relations. A relation from a domainA to a codomainB is a subset of the Cartesian product A × B. Given this concept, we are quick to see that the set F of all ordered pairs (x, x²), where x is real, is quite familiar. It has a domain set R and a codomain set that is also R, because the set of all squares is subset of the set of all reals. If placed in functional notation, this relation becomes f(x) = x². The reason these two are equivalent is for any given value, y that the function is defined for, its corresponding ordered pair, (y, y²) is a member of the set F.

       Application of Sets is the important chapter in the study of sets. The set theory is the basic frame work of all branches of mathematics. Union and Intersection are the basic set operations. Using this operations we have to prove the laws of sets. They are Distributive law and Associative law and Demorgan’s law.

LOGIC

Definition: The study of the principles of valids, using rules to operate on a statement or several statements to reach a correct solution.

Truth Value: any sentence or statement which can be either true or false , but not both. That sentence can be assigned the Truth Value, True (T or 1) or False (F or 0). Then it is a meaningful propositon. Proposition which contains more than one sentence is called compound proposition.

DISJUNCTION

Definition : A disjunction is a compound statement formed by joining two statements with    the connector OR. The disjunction "p or q" is symbolized by p ∨ q  . A disjunction is false if and only if both statements are false; otherwise it is true. The truth values of p ∨ q are listed in the truth table below.A disjunction, both statements must be false for the disjunction to be false.

Example 1:

Given: p: Ann is on the softball team. q: Paul is on the football team. Problem: What does p ∨ q represent?

Solution: In Example 1, statement p represents, "Ann is on the softball team"  and statement q represents, "Paul is on the football team." The symbol ∨  is a logical connector which means "or." Thus, the compound  statement p ∨ q represents the sentence, "Ann is on the softball team or Paul is on the football team." The statement p ∨ q is a disjunction.

p q p ∨ q T T T T F T F T T F F F Example 2: Given: a: A square is a quadrilateral. b: Harrison Ford is an American actor. Problem:   Construct a truth table for the disjunction "a or b." Solution: a b a ∨ b  T T T T F T F T T F F F Example 3: Given: r: x is divisible by 2. s: x is divisible by 3. Problem: What are the truth values of  r ∨ s  Solution: If x = 6, then r is true, and s is true. The disjunction r ∨ s is true. If x = 8, then r is true, and s is false. The disjunction r ∨ s  is true. If x = 15, then r is false, and s is true. The disjunction r ∨ s  is true. If x = 11, then r is false, and s is false. The disjunction r ∨ s  is false.