Share
Explore BrainMass

Discrete Structures

Discrete Structures : Onto and One-to-one

Prove or disprove (find a counterexample) : If A C B and f : A --> B is an onto function (the range of f is all of B), then f is one-to-one and A =B. Please see the attached file for the fully formatted problem.

Set problem

If U = {a,b,c,d,e,f} A = {a,b} B = {-1, 0, 11} Find A' Find B' Find (A U B)' Find (A ∩ B)

Consider an experiment that consists of determining the type of job?either blue-collar or white-collar?and the political affiliation?Republican, Democratic, or Independent?of the 15 members of an adul

16. Consider an experiment that consists of determining the type of job?either blue-collar or white-collar?and the political affiliation?Republican, Democratic, or Independent?of the 15 members of an adult soccer team. How many outcomes are (a) in the sample space; (b) in the event that at least one of the team members is a b

Application of Stirling's Formula

An often used application of Stirling's approximation is an asymptotic formula for the binomial coefficient. One can prove that for k = o(n exp3/4), (n "choose" k) ~ c(ne/k)^(k) for some appropriate constant c. Can you find the c? Can you say why this only works when k is much smaller than n exp3/4?

Double Eulerian Tour

Use words to describe the solution process. No programming. 4. Suppose G is a graph. We define a double Eulerian tour as a walk that crosses each edge of G twice in different directions and that starts and ends at the same vertex. Show that every connected graph has a double Eulerian tour.

Discrete Structures : Coloring

Let G be a properly colored graph and let us suppose that one of the colours used is red. The set of all red-coloured vertices have a special property. What is it? Graph colouring can be thought of as partitioning V(G) into subsets with this special property. (See attachment for full background)

Subgraphs

Let G be a complete graph on n vertices. Please calculate how many spanning and induced subgroups G has... (see attachment)

Absolute Deviation with a Given Equation

Estimate the absolute deviation for the following calculation. List the result y and the absolute deviation. Round your answer so that it contains only significant digits. Y= 251(+/-1)*((860(+/-2))/(1.673(+/-0.006))= 129.025.70(+/-xxxxxx)

Subsequence

In a line of people you are looking for a subsequence of 4 (not necessarily consecutive = neighboring) people with increasing height. How many people should be in the line so that you can be sure to find this subsequence?

Trees

A. If T is a rooted binary tree of height 5, then T has at most 25 leaves. b. If T is a tree with 50 vertices, the largest degree that any vertex can have is 49.

Tree Traversal.

Find the: 1. preorder transversal 2. inorder transversal 3. postorder transversal Of the tree attached in the Word document.

Dimensions

We have some skylights and they measure 1.2m by 0.8m Suppose both dimensions increase by 20%. What's the percent increase in the amount of light admitted? You have a newspaper the dimensions are 35cm by 38cm they reduce the pages by 10%. There are 48 Pages in the newspaper, daily circulation of 135,000. Comp

Row operations

Using row operations, determine if the following set of equations has a solution: x1 + x2 + x3 = 3 2x1 - x2 - 2x3 = -3 3x2 - 4x3 = -3

Relations

S = {0, 1, 2, 4, 6} Test the binary relations on S for reflexivity, symmetry ,antisymmetry, and transitivity. Also find the reflexive, symmetric and transitive closure of each relations. A) P = {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6) } B) P {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)} C) P ((0

Cannot Work this one

In the questions below suppose the variable x represents students and the variable y represents courses, and A(y): y is an advanced course S(x): x is a sophomore F(x): x is a freshman T(x,y): x is taking y. Write the statement using these predicates and any needed quantifiers. a. There is a course that every freshman is

Palindromes

What are the palindromes between 100 & 200? Find the range, mode, and median.

Equivalence Relations and Classes

Let L be a subset of {a,b}* Define a relation R (R sub L) on S* as follows: L for All of x, y is a member of S*, (x,y) are members of R if for all of z, xz are members of L iff yz are members of L A) Show that R is an equivalence relation B) Suppose L={a^i b^i where i >= 0} What can you say about the inde

Discrete Math: Logic and Directed Graphs

Please see the attached file for the fully formatted problems. 1. Circle T for True or F for False as they apply to the following statements: T F Every compound is either a tautology or a contradiction. T F Integers are Rational. T F The empty set has no subsets. T F Onto functions map smaller sets to bigger sets. T F

Domination number

Determine (without proof) a formula for the domination number of path Pn.