|
|
|
1.
Given the undirected graph G=(V, E), where V={1,2,3,4,5,6,7},
E={{1,2},{2,3},{3,4},{3,5},{4,5},{5,6},{6,7}} a)
Is the graph simple? b)
Is the graph complete? c)
Is the graph connected? d)
Can you find 2 paths from 3 to 6? e)
Can you find a cycle? f)
Can you find an edge whose removal makes the graph acyclic? g)
Can you find an edge whose removal makes the graph not connected? h)
Give the adjacency matrix of G. i)
Is G a tree? j)
Does an Eulerian path exist? k)
Does a Hamiltonian path exist? 2.
Draw K6, (complete graph with 6 nodes.) 3.
For each of the following characteristics, draw a graph or explain why such
graph does not exist: a)
Four nodes of degree 1, 2, 3, and 4, respectively b)
Four nodes of degree 2, 3, 3, and 4, respectively 4.
If G is a simple graph, the complement of G, denoted G', is the simple graph
with the same set of nodes as G, where nodes x-y are adjacent in G' if and only
if they are not adjacent in G. a)
Draw K4', complement of K4 b)
Given an adjacency matrix A for a simple graph G, describe the
adjacency matrix for G'.
5.
Given the following graph (tree) with node a as the root and constructed from
left to right: T = (V, E), where
V= {a, b, c, d, e, f, g, h, i}, and a)
Is this a binary tree? b)
Is it a full binary tree? c)
Is it a complete binary tree? d)
What is the parent of e? e)
What is the right child of e? f)
What is the depth of g? g)
What is the height of the tree?
6.
Given the following digraph: D = (
V, E ), where V = { 1, 2, 3, 4, 5} and a)
By inspection is the graph strongly connected? b)
Compute M^2, that is M.M, where M is the adjacency of D. c)
Compute Warshall's first matrix after the adjacency matrix, 1W.
7.
Simplify the following expression:
8.
Find the sum-of-products of f(x,y,z). x
y z
f(x,y,z) 0
0 0
1 0
1 1
1 1
0 0
1 1
1 0
1 f(x,y,z)
= 0 for the other cases.
9.
Write the expression (x.y)'.z
in terms of each of the following: a)
+ and ' (disjunction, negation.) b)
NAND operator.
10.
Draw the Karnaugh map for f(x,y,z) in problem 8. Answer:
f(x,y,z) =
11.
Draw the Karnaugh map for g(x,y,z,w), where g() is "1" for the
following xyzw: 0010, 0011, 0101, 0110, 1001, 1011, 1100, 1110,
and g(x,y,z,w) = 0 elsewhere.
12.
Draw the logic circuit for the expression in problem 10.
13.
Show that NOR is complete set of operators. |