# Class 51: Graphs

Back to Discussion of Exam 2. On to Shortest Path.

Held: Wednesday, May 3, 2006

Summary: Today we consider an ADT used to model a variety of problems, the graph.

Related Pages:

Notes:

• Are there questions on the exam?
• Those of you who have studied this topic in combinatorics should not volunteer too much.
• Reminder: Visitor on Friday.

Overview:

• Introduction: Modeling in CS.
• One Modeling ADT: The Graph.
• Some Graph Problems.
• Solving the Reachability Problem.
• Coding the Solution.

## Introduction: Modeling in CS

• Modeling is a common task in computer science.
• First, you identify a real-world problem (or set of related problems)
• Next, you generalize that problem by modeling the problem domain
• Third, you write an algorithm to solve the generalized problem
• Finally, you use the algorithm to solve the original problem.
• Here are some sample problems:
• Given a town with lots of one-way streets, determine how to get from place to another (and whether you can get from one place to another).
• Find the cheapest sequence of flights from one place to another.
• Find the fastest way to get information across the Internet.
• Determine the shortest path that visits a collection of cities.
• Many of these problems are geographic in nature.

## One Modeling ADT: The Graph

• In all of these problems, it seems natural to model the underlying problem using an abstract type called a graph.
• Graphs contain vertices, which represent the places in the problem.
• Graphs also contain edges between pairs of vertices. These edges represent the connections between the represented places.
• In some graphs, the edges are directed in that they go in one direction, but not necessarily the other.
• In some graphs, the edges are weighted in that they have an associated value (e.g., the cost of taking one leg of a plane flight, the distance between two cities, the speed of a network connection).

## Some Graph Problems

• Some problems are independent of weight
• Reachability: Can you get there from here?
• Cycle: Is there a path that visits every vertex exactly once and returns to the first vertex?
• Generalized reachability: Can you get to every vertex from every other vertex?
• Variants of these problems that use weights
• Shortest path: What is the cheapest way to get there from here?
• Traveling Salesman: What is the shortest path that visits every vertex exactly once?

• To be developed in class.

## Solving the Reachability Problem

• To be developed in class.

## Coding the Solution

• To be developed in class.

Back to Discussion of Exam 2. On to Shortest Path.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:57 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.51.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu