Difference between revisions of "Graph (graph theory)"
(You can tell I have aops vol. 2 when you read this. ;)) |
(add def. for tree) |
||
| Line 1: | Line 1: | ||
{{WotWAnnounce|week=Jan 3-9}} | {{WotWAnnounce|week=Jan 3-9}} | ||
| − | In [[graph theory]], a '''graph''' is a set of [[vertex|vertices]] (or [[points]]) that are connected by a number of [[edge]]s (which are not necessarily straight). Note that this number can be zero, in which case no points are connected. | + | In [[graph theory]], a '''graph''' is a set of [[vertex|vertices]] (or [[points]]) that are connected by a number of [[edge]]s (which are not necessarily straight). Note that this number can be zero, in which case no points are connected. Formally, a graph <math>G</math> is a pair, <math>G = (V, E)</math>, of a set <math>V</math> of vertices together with a subset <math>E</math> of pairs of members of <math>V</math>. |
==Properties and Subobjects== | ==Properties and Subobjects== | ||
A walk is a way to start at any one vertex and travel through the entire graph. A path is a walk that cannot go through any vertex more than once, and a path is a walk that cannot go through any edge more than once. A cycle is a path which starts and ends at the same point. The number of edges coming out of any one vertex is called the degree of the vertex. | A walk is a way to start at any one vertex and travel through the entire graph. A path is a walk that cannot go through any vertex more than once, and a path is a walk that cannot go through any edge more than once. A cycle is a path which starts and ends at the same point. The number of edges coming out of any one vertex is called the degree of the vertex. | ||
| Line 11: | Line 11: | ||
===Connected graph=== | ===Connected graph=== | ||
A graph is called connected if any two vertices can be connected by a path. That is, there are no isolated vertices with no paths coming from them, nor are there closed sub-graphs which are not connected by an edge anywhere. | A graph is called connected if any two vertices can be connected by a path. That is, there are no isolated vertices with no paths coming from them, nor are there closed sub-graphs which are not connected by an edge anywhere. | ||
| − | ==Planar Graphs=== | + | ===Planar Graphs=== |
A graph is said to be planar if it can be drawn in a [[plane]] with no intersecting edges. For example, <math>K_1,K_2,K_3,</math> and <math>K_4</math> are planar. | A graph is said to be planar if it can be drawn in a [[plane]] with no intersecting edges. For example, <math>K_1,K_2,K_3,</math> and <math>K_4</math> are planar. | ||
| Line 23: | Line 23: | ||
*<math>E\le 3V-6</math> | *<math>E\le 3V-6</math> | ||
*if the the sum of the degrees of the faces of the graph is <math>F</math>, then <math>F\le \frac{2}{3}E</math>. | *if the the sum of the degrees of the faces of the graph is <math>F</math>, then <math>F\le \frac{2}{3}E</math>. | ||
| − | ==Euler Trail== | + | ===Euler Trail=== |
A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph. | A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph. | ||
| + | ===Trees=== | ||
| + | A tree is a graph which does not have any sub-graphs which are cycles. | ||
==See Also== | ==See Also== | ||
Revision as of 13:10, 4 January 2008
| This is an AoPSWiki Word of the Week for Jan 3-9 |
In graph theory, a graph is a set of vertices (or points) that are connected by a number of edges (which are not necessarily straight). Note that this number can be zero, in which case no points are connected. Formally, a graph 
is a pair, 
, of a set 
of vertices together with a subset 
of pairs of members of .
Contents
Properties and Subobjects
A walk is a way to start at any one vertex and travel through the entire graph. A path is a walk that cannot go through any vertex more than once, and a path is a walk that cannot go through any edge more than once. A cycle is a path which starts and ends at the same point. The number of edges coming out of any one vertex is called the degree of the vertex.
Types of Graphs
Complete Graph
A complete graph (or clique) is a graph in which every pair of points is connected. The clique with 
vertices is called 
.
Null Graph
The null graph (or independent set) is the opposite of the complete graph. A null graph is simply a scatter plot of points (which are the vertices) with no edges connecting them.
Connected graph
A graph is called connected if any two vertices can be connected by a path. That is, there are no isolated vertices with no paths coming from them, nor are there closed sub-graphs which are not connected by an edge anywhere.
Planar Graphs
A graph is said to be planar if it can be drawn in a plane with no intersecting edges. For example, 
and 
are planar.
In a planar graph, we can define faces of the graph, or the smallest regions bounded by edges. (An alternate definition is the regions bounded by edges which do not have any edges going through them.) Note that the area outside the planar graph is also a face, called the unbounded face. The degree of the face is the number of edges that bound the face. (Note that the same term is used for vertices, which can become confusing)
An interesting result is Euler's Polyhedral Formula, which states that in a planar graph with vertices, edges, and 
faces, then
![\[V-E+F=2\]](http://latex.artofproblemsolving.com/1/d/8/1d82f9de4b42e3c90f709167d76f199d56a2e517.png)
The proof of this is simple using induction, but the derivation of the formula is much trickier.
Other interesting results for planar graphs are that:
- if the the sum of the degrees of the faces of the graph is
, then 
.
.Euler Trail
A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph.
Trees
A tree is a graph which does not have any sub-graphs which are cycles.
