Prepared by:
Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Graph theory provides a powerful tool for constructing mathematical models in a variety of situations. Given "objects" one can represent them by dots and the relationship between the objects can be indicated using straight or curved line segments. Dots might represent people, street corners, or books. Line segments could indicate that the people are same age, street corners are connected by a street, or that the books have the same author. Some relationships for people are "symmetric," and, thus, if John and Mary have the same age, Mary and John have the same age. But some relationships are not symmetric. Thus, Mary may think of John as a friend but John may not think of Mary as a friend. In cases of this kind, the line segment used to join two dots will have an arrow on it to indicated the asymmetrical behavior. Some pairs of people may be joined with "friendship edges" in each direction indicating they are friends of each other, and for other pairs of people there may be no edge or an edge in one direction only. When there are no directions for the edges we talk about graphs, and when there are directions on the edges talk about digraphs, which is short for directed graphs.
This digraph has 6 vertices and 6 directed edges. The labels (names) of the vertices appear within the dots which represent the vertices.
