Operations on Graphs

Examples of Graph Operations

Topological sort: Given a list of courses required for the major, and the prerequisite list for each course, find a schedule for taking the courses that obeys the prerequisite list.

Minimum spanning tree: Design the layout of the NSF backbone network for the Internet, minimizing the amount of cable that must be laid.

Finding a cycle: Given a list of processes currently executing on the system, the resources each holds, and the resources each needs, determine whether or not progress is possible.

All-pairs-shortest-path: Find the shortest distance between all pairs of cities in the country, for publication in a traveler's guidebook.

Graph coloring: Assign the fewest numbers of registers needed to store variables and temporary results in a procedure.

Graph matching: Assign teachers to courses, so that every course is taught by a qualified teacher.