Solution: There is at most one edge between each pair of vertices, so, the question is, how many pairs are there? There are n(n-1)/2 pairs. Or, think about it this way: each vertex can be adjacent to at most n-1 other vertices. Therefore, the adjacency list of each vertex contains at most n-1 entries. Each edge is represented in the adjacency lists of each of its end vertices. Therefore, there are at most n(n-1)/2 edges.
Solution: It is possible to graduate. Simply complete the courses in the following order: CS100, CS103, CS200, CS250, CS260, CS300, CS303, CS360, CS370, CS400 and finally CS405.
To make it impossible, we could make CS405 a prerequisite for CS260.
Here is the directed graph:
It is possible to graduate if and only if there are no directed cycles. Notice that the graph above has cycles but they aren't directed.
| m | x,q,r |
| n | q,u,o |
| o | n,r,s,p,v |
| p | o,s,z |
| q | m,t,n |
| r | m,u,y,o,s |
| s | r,o,p |
| t | q,u |
| u | t,n,r |
| v | x,y,o,w |
| w | v,z |
| x | m,v |
| y | r,v |
| z | p,w |
Solution:
Here is a drawing of the graph:
Adjacency Matrix:
| m | n | o | p | q | r | s | t | u | v | w | x | y | z | |
| m | F | F | F | F | T | T | F | F | F | F | F | T | F | F |
| n | F | F | T | F | T | F | F | F | T | F | F | F | F | F |
| o | F | T | F | T | F | T | T | F | F | T | F | F | F | F |
| p | F | F | T | F | F | F | T | F | F | F | F | F | F | T |
| q | T | T | F | F | F | F | F | T | F | F | F | F | F | F |
| r | T | F | T | F | F | F | T | F | T | F | F | F | T | F |
| s | F | F | T | T | F | T | F | F | F | F | F | F | F | F |
| t | F | F | F | F | T | F | F | F | T | F | F | F | F | F |
| u | F | T | F | F | F | T | F | T | F | F | F | F | F | F |
| v | F | F | T | F | F | F | F | F | F | F | T | T | T | F |
| w | F | F | F | F | F | F | F | F | F | T | F | F | F | T |
| x | T | F | F | F | F | F | F | F | F | T | F | F | F | F |
| y | F | F | F | F | F | T | F | F | F | T | F | F | F | F |
| z | F | F | F | T | F | F | F | F | F | F | T | F | F | F |
On average, how many steps would it take to determine whether or not two vertices are adjacent in a graph with 13,342 vertices and 79,243 edges. The answer depends on how we represent the graph so give two answers.
Solution:
Adjacency Matrix: 1
Adjacency List: 1 + (79,243 / 13,342)
Adjacency list representations are just like hashtables that use chaining
(see lectures notes).
To determine if an element is in a hashtable we calculate its position in the table,
O(1) steps, and then search the list at that position;
likewise, to determine if two vertices are adjacent in a adjacency list representation,
we first find the position of one vertex in the table, 1 step,
and then search the adjacency list at that position.
For hashtables the average number of steps required to determine if an element is
in the table is 1 + load factor/2.
Recall that the load factor is just
the number of elements in the hashtable divided by the size of the table.
The "load factor" in this example is (2 * 79,243 / 13,342)
because the table has size 13,342 and the number of elements in the table is
2*79,243 (remember, each edge is represented in the adjacency lists
of each of its end vertices).
Solution:
There are many solutions to this problem so we give only one here.
The removed edges are drawn as dashed line segments.
Turn the graph from the previous question into three trees by removing edges. List the edges that you removed.
Solution:
In addition to the edges removed to turn the graph into a tree,
we also removed two more to create three trees.
These two edges are drawn as dashed line segments.
Given only the number v of vertices and the number e of edges in a graph:
Solution:
The following tree, consisting of only one edge,
is the only example:
Solution: Following is a labelled list of all valid states:
State 0 State 1 State 2 State 3 2 0 2 0 2 0 1 1 2 0 1 1 0 2 1 1 B - B - B - B - State 4 State 5 State 6 0 2 0 2 0 2 2 0 1 1 0 2 B - B - B - State 7 State 8 State 9 State 10 2 0 2 0 2 0 1 1 2 0 1 1 0 2 1 1 - B - B - B - B State 11 State 12 State 13 0 2 0 2 0 2 2 0 1 1 0 2 - B - B - BThe initial state is labelled "0" and the goal state "13". The graph corresponding to this state space looks like the following:
8 9 3 2 \ / \ / \ / 0 1 - 12 13 / \ / \ / \ 11 10 4 5 6 7Thus, there are an infinite number solutions to the problem, however, there are only four optimal solutions.
