Discrete Structures Test 3

Select the set that corresponds to the relation given in the matrix  below. Rows of the matrix are numbered 1 through 4 from top to bottom and columns are numbered 1 through 4 from left to right.

{ (1, 2), (2, 2), (2, 4), (3, 3) }

A relation R is given in the matrix below. Rows of the matrix are numbered 1 through 4 from top to bottom and columns are numbered 1 through 4 from left to right. Select the expression that is false.

4R3

The domain of a relation R is the set of real numbers. x is related to y under relation R if x² = y. Select the description that accurately describes relation R.

Anti-symmetric

A is a finite non-empty set. The domain for relation R is the power set of A. (Recall that the power set of A is the set of all subsets of A.) For X ⊆ A and Y ⊆ A, X is related to Y if X and Y have the same cardinality (i.e.,|X|=|Y|). Select the description that accurately describes relation R.

Symmetric and Reflexive

Graph G is defined by the arrow diagram below.

Select the statement about G that is false.

G has a circuit length of 5

Graph G is defined by the arrow diagram below.

What is the out-degree of vertex 2?

3

S and T are binary relations on the set {a, b, c, d} and are defined by the arrow diagrams below:

Select the pair that is in S * T.

(2,4)

2) S and T are binary relations on the set {a, b, c, d} and are defined as follows:

S = { (a, b), (a, c), (b, d), (d, c) }

T = { (b, b), (c, a), (c, d), (a, d) }

Select the set corresponding to T * S.

{ (a, a), (a, b), (a, d), (d, a), (d, d) }

The figure below shows a directed graph G:

Which edge is not in G³?

(3,4)

The figure below shows a directed graph G:

Which edge is not in G⁺?

(1,4)

What is the third row of A * B

[0 1 1]

A directed graph G has 5 vertices, numbered 1 through 5.  The 5x5 matrix A is the adjacency matrix for G.  The matrices A² and A³ are given below.

Which three vertices are part of a circuit of length 3?

3,4,5

Select the words that correctly completes the following sentence:

In the graph below vertices A and C _____ .

are adjacent

What is the total degree of the graph below?

8

Select the correct adjacency representation for the graph given below.

picture

Suppose that G is a graph with n vertices such that every vertex has degree n/2. If the graph is represented using the adjacency list representation, then what is the worst-case complexity to determine whether two particular vertices are adjacent?

O(n)

Select the statement that is false.

If two graphs G and H have the same degree sequence, then G and H are isomorphic.

Select the graph property that is not preserved under isomorphism. The vertices of the graph are numbered 1 through n, where n is the number of vertices.

Every even numbered vertex has degree 3.

Pick the correct description of the sequence (F,A,G,F,E,D,B,F)

with respect to the graph pictured below.

A circuit but not a cycle

The sequence (B,C,D,A,C,E,A)  is a walk in a graph. Select the correct description for the walk.

A trail but not a path

Whic set is a connected component of the graph below?

{A,H}

What is the vertex connectivity of the graph pictured below?

2

Select the graph that does not have an Euler trail.

picture

Select the graph that has an Euler circuit.

picture

Select the graph that does not have a Hamiltonian cycle.

K_3,4

Select the sequence that is a Hamiltonian cycle for the graph shown below:

⟨d,f,e,c,a,b,d⟩

Select the graph that is not planar.

picture

Select the true statement.

C₂₀ is a planar graph.

What is the clique number of the graph shown below?

4

The greedy algorithm is used to color the graph shown below. The vertices are colored in order: A through G. The colors are ordered as:

• 1 - Red

• 2 - Blue

• 3 - Green

• 4 - Yellow

• 5 - Purple

What is the coloring assigned to each vertex?

A-red, B-red, C-blue, D-green, E-green, F-yellow, G-yellow

Which choice corresponds to the leaves of the tree?

e, g, b, h, f, m, a, and l

What is the height of the tree shown below?

4

Which of the following tic-tac-toe configurations has a child that is a winning leaf if X plays next?

picture

Use the prefix tree below to encode the word "piece".

1110100011110

An acyclic graph has 10 vertices and 8 edges. How many connected components does the graph have? Acyclic is an adjective used to describe a graph in which there is no cycle, or closed path.

2

Select the set of properties such that it is impossible to have a graph that satisfies all the properties in the set. Acyclic is an adjective used to describe a graph in which there is no cycle, or closed path.

Acyclic, 7 vertices, 7 edges

Select the order in which the vertices are visited in a pre-order traversal of the tree shown below.

e, i, b, h, f, a, c, d, g

Select the order in which the vertices are visited in a post-order traversal of the tree shown below.

b, i, f, h, d, g, c, a, e

The graph below is traversed using depth first search. The search starts at vertex A and vertices are considered in alphabetical order. What are the edges in the depth first search tree?

{A, B}, {B, D}, {B, E}, {E, C}, {E, F}

The graph below is traversed using breadth first search. The search starts at vertex A and vertices are considered in alphabetical order. What are the edges in the breadth first search tree?

{A, B}, {A, C}, {A, E}, {B, F}, {C, D}

Select the expression that is equivalent to x̄

xbar * ybar + xbar

The values for variables x, y, and z are:

x = 1, y = 0, z = 1

Select the Boolean expression that evaluates to 0.

x + y + z all with bar on top

Select the Boolean expression that is equivalent to the function defined in the table blow:

xbar ybar zbar + xbar y zbar + x y z

Select the Boolean expression that is equivalent to the function defined in the table below:

xbar y zbar + xbar y z + x ybar z

Select the description that characterizes the Boolean expression:

x(ybar + z)

CNF, but not DNF

Select the description that characterizes the Boolean expression:

x ybar z

CNF and DNF

Select the expession that is equivalent to (x + ybar) z

image

Select the expression that is equivalent to xy + zbar + ubar

picture

Select the Boolean expression that is not satisfiable.

picture

Select the Boolean expression that is not satisfiable.Select the Boolean expression that corresponds to the output of the Boolean circuit below:

picture

Select the Boolean expression that corresponds to the output of the Boolean circuit below:

x+ybar + yz

Select the circuit whose output is xy + zbar all under bar

picture

Select the set that corresponds to the relation given in the arrow diagram below:

{ (1, 3), (1, 4), (2, 3), (2, 2) }

Select the set that corresponds to the relation given in the arrow diagram below:

{ (A, 3), (B, 1), (B, 4), (D, 3), (D, 4) }

The domain of a relation R is the set of real numbers. x is related to y under relation R if |x| <= |y|. Select the description that accurately describes relation R.

Neither symmetric nor anti=symmetric

A is a finite non-empty set. The domain for relation R is the power set of A. (Recall that the power set of A is the set of all subsets of A.) For X ⊆ A and Y ⊆ A, X is related to Y if X is a proper subsets of Y (i.e., X ⊂ Y). Select the description that accurately describes relation R.

 

Anti-symmetric and Anti-reflexive

Graph G is defined by the arrow diagram below.

Select the properties that accurately describe the following

sequence with respect to graph G: (2,3,1,3,4)

 

A trail but not a path

S and T are binary relations on the set {a, b, c, d} and are defined by the arrow diagrams below:

Select the pair that is not in T * S.

(2,4)

The figure below shows a directed graph G:

What is the out-degree of vertex 3 in G⁺?

1

A directed graph G has 5 vertices, numbered 1 through 5.  The 5x5 matrix A is the adjacency matrix for G.  The matrix A² is given below.

Which vertex can be reached by a walk of length 4 that starts at vertex 1?

5

A directed graph G has 5 vertices, numbered 1 through 5.  The 5x5 matrix A is the adjacency matrix for G.  The matrices A² and A³ are given below.

Which edge is not in the transitive closure of G?

(4,5)

Select the correct matrix representation for the undirected graph given below. The rows and columns of the matrix are numbered 1 through 5.

V = {1, 2, 3, 4, 5}

E = { {1, 3}, {2, 3}, {4, 5}, {5, 1}, {5, 2}, {3, 4} }

picture

Suppose that G is a graph with n vertices such that every vertex has degree 4. If the graph is represented using the matrix representation, then what is the worst-case complexity to find all the neighbors of a particular vertex?

O(n)Select the graph that is isomorphic to the graph pictured below.

Select the graph that is isomorphic to the graph pictured below.

V = {1, 2, 3, 4, 5}

E = { {2, 4}, {2, 3}, {2, 5}, {1, 5}, {1, 3}, {3, 5} }

What is the length of the walk (B,D,G,E,D,B) in the graph below?

5

The degree sequence of a graph is a list of the degrees of all of the v vertices in non-increasing order. The degree sequence for four different graphs are given below. Each graph is guaranteed to be connected. Select The degree sequence corresponding to the graph that has an Euler circuit.

2, 2, 2, 4, 4, 4, 4

Select the graph that has an Euler trail.

K_2,3

Which graph does not have a Hamiltonian path?

image

A planar graph G has 7 vertices. One of the vertices has degree 4, two vertices have degree 3, and four vertices have degree 2. How many regions does G have?

4

What is the chromatic number of the graph shown below?

3

Which choice corresponds to the level 2 vertices

e, d, m, a, and l

What is the height of a full game tree for tic-tac-toe in which the root is an empty tic-tac-toe board?

9

A complete graph with 6 vertices is traversed using breadth first search. The vertices are labeled A through F. The search starts at vertex A and vertices are considered in alphabetical order. What is the resulting BFS tree?

picture

Select the expression that is equivalient to x+y.

y + x ybar

Select the Boolean expression that is equivalent to the function defined in the table blow:

x ybar zbar + xyz

Select the description that characterizes the Boolean expression: x + ybar + z

CNF and DNF

Select the description that characterizes the Boolean expression:

Neither CNF nor DNF

Select the expression that is equivalent to xy + z’ + u’

picture

Select the Boolean expression that corresponds to the output of the Boolean circuit below:

x’y’ + y’z

S and T are relations on the real numbers R and are defined as follows:

S={(x,y)|x<y}

T={(x,y)|x>y}

What is T * S?

RxR (all pairs of real numbers

What is the total degree of the graph K_5?

20

Select the function f that is an isomorphism from G to G'.

f(a) = 3, f(b) = 5, f(c) = 2, f(d) = 4, f(e) = 1

Select the sequence that is a cycle in the graph below.

(B,D,G,E,F,B)

What is the vertex connectivity of K_3,5 ?

3

Select the correct statement

If an undirected graph G is 4-regular, then G must have an Euler circuit.

Select the true statement.

If every vertex in the graph has d or fewer neighbors, then the chromatic number must be less than or equal to d+1.

Use the prefix tree below to decode 10110011110.

rice

A complete graph with 6 vertices is traversed using depth first search. The vertices are labeled A through F. The search starts at vertex A and vertices are considered in alphabetical order. What is the resulting DFS tree?

picture

Select the expression that is equivalient to x+y.

y + x y’

The values for variables x, y, and z are:

x = 0, y = 1, z = 1

Select the Boolean expression that evaluates to 1.

(z + x)’ + yx’

Select the description that characterizes the Boolean expression:
xy’ + z

DNF, but not CNF

Select the description that characterizes the Boolean expression:

(x + y + z’) (zy)’

Neither CNF nor DNF

The figure below shows a directed graph G:

What is the out-degree of vertex 2 in G²?

3

Select the graph that is not regular.

picture

What is the chromatic number of the graph shown below?

3

Which choice corresponds to the descendants of vertex d?

g,b,c, and h

Select the expression that is equivalient to x+y.

y + x y’