Graph theory
Category:Graph theory
Graph theory is the branch of
mathematics that examines the properties of
graphs. \n
 |
\n| A graph with 6 vertices and 7 edges. |
Informally, a graph is a set of objects called
vertices (or nodes) connected by links called edges (or arcs). Typically, a graph is depicted as a set of dots (i.e., vertices) connected by lines (i.e., edges).
For more and formal definitions, see
Glossary of graph theory and
Graph (mathematics).
Depending on the applications, edges may or may not have a direction; edges joining a vertex to itself may or may not be allowed, and vertices and/or edges may be assigned weights, that is, numbers. If the edges have a direction associated with them (indicated by an arrow in the graphical representation) then it is a
directed graph, or
digraph.
A graph with only one vertex and no edges is the
trivial graph or
"the dot". A graph with only vertices and no edges is known as the
empty graph, but is sometimes also known as the
Null graph. See
Glossary of graph theory.
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. Various
networks are conveniently described by means of graphs. For example, the link structure of
Wikipedia could be represented by a directed graph: the vertices are the articles in Wikipedia and there's a directed edge from article
A to article
B if and only if
A contains a link to
B. Directed graphs are also used to represent
finite state machines. The development of
algorithms to handle graphs is therefore of major interest in
computer science.
History
\nLeonhard Euler's paper on Seven Bridges of Königsberg is considered to be the first result in graph theory. It is also regarded as one of the first topological results in geometry; that is, it does not depend on any measurements. This illustrates the deep connection between graph theory and topology.
Graph representations
In general, there are four ways to represent a graph in a computer system: The incidence list representation, the incidence matrix representation, adjacency list representation, and the adjacency matrix representation. \n* Incidence List - This representation uses an array. Each element in the array corresponds with a single edge. Each edge contains a list of size two which corresponds to the endpoints of the edge. This can also apply to directed graphs by ensuring the first vertex be defined as the source or destination while the second should be defined as the opposite.\n* Incidence matrix - This representation uses a matrix of M edges by N vertices. If the vertex is an endpoint to the edge, a value of 1 is assigned to their crossing, otherwise, a value of 0 is assigned. This is a terrible waste of space as every column or row represented by the edge can only have two values of 1 while the rest are labelled 0.\nThese two representations are most useful when information about the edges are more desirable than information about vertices.\n* adjacency list - Much like the incidence list, each node has a list of which nodes it is adjacent to. This can sometimes result in "overkill" in an undirected graph as vertex 3 may be in the list for node 2, then node 2 must be in the list for node 3. Either the programmer may choose to use the unneeded space anyway, or he/she may choose to list the adjacency once. This representation is easier to find all the nodes which are connected to a single node, since these are explicitly listed.\n* adjacency matrix - there is an N by N matrix, where N is the total number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element would be 1, otherwise it would be 0. This makes it easier to find subgraphs, and to reverse graphs if needed.\nThese two representations are most useful when information about the vertices is more desirable than information about the edges. These two representations are also most popular since information about the vertices is often more desirable than edges in most applications.
Special graphs
There are several kinds of special graphs, which have specific structures and properties:
- Complete graphs\n* Treess \n* Bipartite graphs\n* Planar graphs\n* Line graphs
Graph problems
Important algorithms
Generalizations
In a hypergraph, an edge can connect more than two vertices.
An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.
Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.
In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number.
Related areas of mathematics
See also
\n* Ordered tree data structure - DAGs, binary trees and other special forms of graph.\n* Graph (data structure)\n* List of graph theory topics\n* Graph drawing
External links
\n* Graph Theory online textbook\n* Graph theory tutorial\n* Graph theory algorithm presentation\n* Some graph theory algorithm animations \n**Step through the algorithm to understand it.\n* The compendium of algorithm visualisation sites\n* A search site for finding algorithm implementations, explanations and animations
\n\n\n\n\n\n\n\n\npt_BR:Teoria dos Grafos\nsimple:Graph theory\n\n\n\n
