Solutions to other tests:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  

Mathematics for the Digital Age
and
Programming in Python

>>> Second Edition

Test 16

1.
(a) T   (b) F   (c) F
2.
3.
4.
5.
(b)
6.
7.
8.
(a), (b), (c)
9.
10.
(a), (b), (c)
11.
12.
13.
14.
(a) T   (b) T   (c) T
15.
Yes, any planar graph can be colored in four colors.
16.
17.
18.
(a) T   (b) F   (c) T
19.
20.
21.
(a)

The matrix has only zeros on the main diagonal.
The matrix is symmetrical with respect to the main diagonal.

(b)
def isAdjacencyMatrix(a): n = len(a) for r in range(n): if len(a[r]) != n or a[r][r] != 0: return False for c in range(r+1, n): if (a[r][c] not in {0, 1} or a[r][c] != a[c][r]): return False return True
22.
def makeAdjacencyMatrix(g): n = len(g) a = [] for r in range(n): a.append(n * [0]) for v1 in g: for v2 in g[v1]: a[v1-1][v2-1] += 1 return a
23.
24.
def isProperColoring(E, coloring): for e in E: if coloring[e[0]] == coloring[e[1]]: return False return True
25.
See Test16-25.pdf.
26.
def extractChain(E, coloring, v, colors): if coloring[v] not in colors: return None chain = {v} count = -1 while len(chain) != count: count = len(chain) for e in E: if e[0] in chain and coloring[e[1]] in colors: chain.add(e[1]) if e[1] in chain and coloring[e[0]] in colors: chain.add(e[0]) return chain


Copyright © 2010 by Skylight Publishing