Graph theory: Difference between revisions
imported>Yuval Langer (weighted graph image example) |
imported>Caesar Schinas m (Bot: Update image code) |
||
| Line 14: | Line 14: | ||
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 '''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. | ||
{{Image|Weighted-graph.jpg|right|350px|Weighted graph}} | |||
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 typical use of a weighted graph would be planning routes between locations on a map where the 'cost' associated with the arc would be the distance between the two locations. | 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 typical use of a weighted graph would be 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 'root node') at the top of the diagram, and then 'growing' downwards with arcs and nodes getting further and further from the root. In this way, nodes can be grouped in terms of their distance from the root. Every node (aside from the root) is referred to as the 'child' of the node to which it is connected and which is one step closer to the root. This node is also called the 'parent' node of the child. Every node has at most one parent but can have any number of children. Nodes without any children are commonly called 'leaf nodes'. 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. | 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 'root node') at the top of the diagram, and then 'growing' downwards with arcs and nodes getting further and further from the root. In this way, nodes can be grouped in terms of their distance from the root. Every node (aside from the root) is referred to as the 'child' of the node to which it is connected and which is one step closer to the root. This node is also called the 'parent' node of the child. Every node has at most one parent but can have any number of children. Nodes without any children are commonly called 'leaf nodes'. 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. | ||
Revision as of 07:09, 8 June 2009
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. For example, the following graph has two nodes (labeled 'a' and 'b'), and a single arc joining them.
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.
Types of Graphs
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 typical use of a weighted graph would be 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 'root node') at the top of the diagram, and then 'growing' downwards with arcs and nodes getting further and further from the root. In this way, nodes can be grouped in terms of their distance from the root. Every node (aside from the root) is referred to as the 'child' of the node to which it is connected and which is one step closer to the root. This node is also called the 'parent' node of the child. Every node has at most one parent but can have any number of children. Nodes without any children are commonly called 'leaf nodes'. 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.