Mathematics

What You Should Be Able To Do For Test 4

Chapter 7

Determine whether a graph is a tree (exercises 1, 3abc, 5, 7).

Find spanning trees in a graph. In simple examples, find all spanning trees, or count the number of spanning trees.

Use Kruskal's algorithm to find a minimum spanning tree of a weighted graph.

Shortest network problems like exercises 27, 29, 37, 41, 57, 58, 59.

Chapter 8

Given a scheduling problem, draw the project digraph.

Use a priority list to make a schedule.

Find what is illegal in a proposed schedule.

Use the decreasing time algorithm to make a priority list and schedule a project

Find the length of the critical path from each vertex and the length of the critical path of the project digraph. You should know that no schedule can possibly get the job done in less time than the length of the critical path of the project digraph.

Use the critical-path algorithm to schedule a project.

Personal Help Sheet

You may bring to the test one sheet of paper containing whatever you find helpful.

MA 103-005 home page
Test study guides
Last modified Tue Nov 5 2002
Send questions or comments to schecter@math.ncsu.edu