Relations : Warshall's Algorithm, Digraphs and Connectivity

Please see the attached file for the fully formatted problems. Let A = {a. b, c, d} and let the relation R be defined on A by the 0 0 1 1 matrix MR = 0 1 0 0 Note, take the nodes in A in the order given. 0 0 1 0 1 0 0 0 (a) Use Warshall’ s Algorithm (Section 7.4 ...continues

Spanning Trees and Graphs

Does every graph have a spanning tree? If not, then can you tell from the number of nodes and the number of edges a graph has whether it has a spanning tree, or do you need more information?

Spanning Tree Graph : Movie Collaboration (Kevin Bacon Game)

If you were required by a professor to find a spanning tree of the movie collaboration graph (where each node corresponds to an actor with finite Kevin Bacon number, and two nodes are connected by an edge if the corresponding actors have been in a movie together), how would you do it? Why would you choose your method over other ...continues

Tile a plane with n-gons.

Is it possible to tile a plane with (a) regular 5-gons and regular 6-gons? (B) regular 5-gons, regular 6-gons, and triangles? (c) regular 5-gons, regular 6-gons, and regular triangles?

Relations : Properties and Equivalence Classes

Please see the attached file for the fully formatted problem. Exercise 5 (4p) R is the relation defined on Z ts follows: for all m,n E Z, m R n <=>4|(m-n) a. Determine whether the relaition is reflexive. b. Determine whether the relation is symmetric. c. Determine whether the relation is transitive. d. In case the relat ...continues

Discrete Math : Set Relations

Let SIGMA = {a,b} be an alphabet. a. List between braces the elemnts of SIGMA4. the set of strings of length over SIGMA. b. Let A = SIGMA1 U SIGMA2 and B = SIGMA3 U SIGMA4. Describe A, B and AUB in plain English.

Discrete Math

The following is is meant to have some assumptions made (like "n"). I have been up all night trying to figure this out. It can't be Euler because the vertices can't be >1. It might be Hamilton if I assume that E of G(V,E) is infinte..but how would I get my answer? I would just have sets (e1, e2,...) Could this be a straight ...continues

Discrete Math

Please help me with this one! 1. Let G be an undirected graph with n vertices. If G is isomorphic to its own compliment , how many edges must G have?

Discrete structures

.Derive the statement as corollaries of other theorems from the text or of statement you have proved true in the exercise. Prove that if one solution to a quadratic equation of the form x^2+bx+c=0 is rational (where b and c are rational), then the other solutions is also rational. (Use the fact that if the solutions of the e ...continues

Disprove the statement by giving a counterexample

For all real number a & b, if a