Graph theory: Difference between revisions
imported>Yitzchak Novick (New page: '''Graph theory''' is the field of mathematics which deals with the study of '''graphs'''. A graph is defined as a set of ''vertices'' or ''nodes'' and ''edges'' or ''arcs'' which join th...) |
imported>Yitzchak Novick No edit summary |
||
| Line 1: | Line 1: | ||
'''Graph theory''' is the field of mathematics which deals with the study of '''graphs'''. A graph is defined as a set of ''vertices'' or ''nodes'' and ''edges'' or ''arcs'' which join the nodes. Graphs have a wide variety of real-world applications. They are naturally well suited for expressing problems involving geographical information, but they can also be used for expressing far more abstract information such as possible strategies in a game theory question, or available courses of action for manipulating database tables. | '''Graph theory''' is the field of mathematics which deals with the study of '''graphs'''. A graph is defined as a set of ''vertices'' or ''nodes'' and ''edges'' or ''arcs'' which join the nodes. [[Image:GraphTheoryDiagram1.jpg]]Graphs have a wide variety of real-world applications. They are naturally well suited for expressing problems involving geographical information, but they can also be used for expressing far more abstract information such as possible strategies in a game theory question, or available courses of action for manipulating database tables. | ||
There are certain specific types of graphs which express additional information and/or have certain restrictions applied to them. A few examples are listed here: | There are certain specific types of graphs which express additional information and/or have certain restrictions applied to them. A few examples are listed here: | ||
Revision as of 15:08, 29 July 2008
Graph theory is the field of mathematics which deals with the study of graphs. A graph is defined as a set of vertices or nodes and edges or arcs which join the nodes. 
Graphs have a wide variety of real-world applications. They are naturally well suited for expressing problems involving geographical information, but they can also be used for expressing far more abstract information such as possible strategies in a game theory question, or available courses of action for manipulating database tables.
There are certain specific types of graphs which express additional information and/or have certain restrictions applied to them. A few examples are listed here:
A directed graph is a graph where the arcs are one-directional, that is an arc between two nodes only indicates the possibility of moving from one node to the other, but not in the opposite direction. The arcs will usually be drawn as arrows to indicate the direction. An example of a potential use for a directed graph would be a graph which tracks possible states that a computer could be in; there may be a way for a computer in one state to reach a subsequent state, but no way to return from the second state to the first.
A weighted graph is a graph where there is some 'cost' associated with each arc. Usually, a little number will appear directly adjacent to every arc to express this price. A weighted graph would typically used for planning routes between locations on a map where the 'cost' associated with the arc would be the distance between the two locations.
A tree is a special graph which is connected (every node can be reached from every other node by following one or more arcs) and for which the number of arcs is exactly one fewer than the number of nodes. A tree is usually drawn with one node (called the 'route node') at the top of the diagram, and then 'growing' downwards with arcs and nodes getting further and further from the route. A typical use of a tree would be a decision problem where the answer to a question determines the next question and set of possible answers.