INTRODUCTION
The development of graph theory is very similar the development of probability theory, where much of the original work was motivated by efforts to understand games of chance. The large portions of graph theory have been motivated by the study of games and recreational mathematics. Generally speaking, we use graphs in two situations. Firstly, since a graph is a very convenient and natural way of representing the relationships between objects we represent objects by vertices and the relationship between them by lines. In many situations (problems) such a pictorial representation may be all that is needed. Example of such applications are chemical molecule and map coloring as shown in the diagrams below. Other examples are signal-flow graphs, Konigsberg bridges, tracing maze etc.
Secondly, we take the graph as mathematical model, solve the appropriate graph-theoretic problem, and then interpret the solution in terms of the original problem. This modeling procedure can be illustrate as follows:
Diagram
Most problems in graph theory can be described under the following headings:
Many of the existence problems in graph theory arose a recreational puzzles.
Diagram
Most problems in graph theory can be described under the following headings:
- Existence Problems
- Does there exist . . . ?
- Is it possible to . . . ?
- Construction Problems
- If . . . exists, how can we construct it?
- Enumeration Problems
- How many . . . are there, and can we list them all?
- Optimization Problems?
- If there are several . . . which one is the best?
- Does there exist a closed trail crossing each of the seven bridges exactly once? (existence problem).
- If such a trail exists, how can we construct one? (constructive problem).
- How many closed trails are there, and can we list them? (enumerate problem).
- Which close trails involve shortest path. (Optimization problems).
Many of the existence problems in graph theory arose a recreational puzzles.
- The Konigsberg Problem
- Does there exist a closed trail crossing each of the seven bridges exactly once?
- The Knight's-Tour Problem
- Does there exists a sequence of knight's moves visiting each square of a chessboard exactly once and returning to the starting position?
- The Four-Color Problem
- Does exist a map which require four colors to color it, so that neighboring countries are differently colored?
- The Utilities Problem
- Does there exist a way of connecting the three neighbors to the three utilities in such a way that no two connections cross?
- The Queen's Problem
- Does there exist an arrangement of five queens on a chessboard so that every non-occupied square is attached?
- Eulerian Type Problem
- A test for determining whether a given graph is Eulerian (Fleury's algorithm ).
- A problem of getting out of a maze (Tarry's algorithm).
- The spanning tree Problem (Kruskal's and Prim's algorithms).
- Planarity type problems i.e., problems deal with planarity of graphs.
- The best way of determining whether a given graph is planar: (Planarity algorithm).
- The problem of finding the chromatic number of a given graph: (chromatic Polynomials).
- Enumeration Problems
- Labeled graphs.
- Labeled Digraphs.
- Labeled Trees.
- Optimization Problems
- The problem of finding the shortest path between two vertices in a weighted digraph (The shortest path problem).
- The problem of obtaining the longest path between two vertices in a weighted digraph (The scheduling algorithm)
- The problem of finding a minimum weight spanning tree in a given connected graph. (The minimum connector problem).
- The traveling salesman problem.