12,080
edits
Changes
cleanup
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a [[website]] could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page ''A'' to page ''B'' exists if and only if ''A'' contains a link to ''B''. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of [[algorithm]]s to handle graphs is therefore of major interest in [[computer science]].
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a [[website]] could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page ''A'' to page ''B'' exists if and only if ''A'' contains a link to ''B''. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of [[algorithm]]s to handle graphs is therefore of major interest in [[computer science]].
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights can be used to represent many different concepts; for example if the graph represents a road network, the weights could represent the length of each road.<ref name="Note1">The only information a weighted graph provides as such is (a) the vertices, (b) the edges and (c) the weights. Therefore the example in which the weights represent the roads' lengths doesn't imply that the weights are merely redundant annotations: there is no actual topographical information associated with the graph, so unlike reading a map, measuring the distances between the vertices is completely meaningless -- without the weights, there would be no way of telling what the distance between the vertices is in real life.</ref> A digraph with weighted edges is called a [[network (mathematics)|network]].
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights can be used to represent many different concepts; for example if the graph represents a road network, the weights could represent the length of each road. The only information a weighted graph provides as such is (a) the vertices, (b) the edges and (c) the weights. Therefore the example in which the weights represent the roads' lengths doesn't imply that the weights are merely redundant annotations: there is no actual topographical information associated with the graph, so unlike reading a map, measuring the distances between the vertices is completely meaningless -- without the weights, there would be no way of telling what the distance between the vertices is in real life. A digraph with weighted edges is sometimes called a [[network (mathematics)|network]].
Networks have many uses in the practical side of graph theory, [[network analysis]] (for example, to model and analyze traffic networks or to discover the ''shape'' of the internet -- see [[#Applications|Applications]] below). Within network analysis, the definition of the term "network" varies, and may often refer to a simple graph.
Networks have many uses in the practical side of graph theory, [[network analysis]] (for example, to model and analyze traffic networks or to discover the ''shape'' of the internet -- see [[#Applications|Applications]] below). Within network analysis, the definition of the term "network" varies, and may often refer to a simple graph.
Graph theory is also used to study molecules in [[chemistry]] and [[physics]]. In [[condensed matter physics]], the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings.
Graph theory is also used to study molecules in [[chemistry]] and [[physics]]. In [[condensed matter physics]], the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings.
==References==
==References==
* [http://wikinfo.org/index.php/Graph_theory Graph theory], [http://wikinfo.org/index.php/Main_Page Wikinfo].
* [http://wikinfo.org/index.php/Graph_theory Graph theory], [http://wikinfo.org/index.php/Main_Page Wikinfo].
* [http://en.wikipedia.org/wiki/Graph_theory Graph_theory], [http://en.wikipedia.org/ Wikipedia].
* [http://en.wikipedia.org/wiki/Graph_theory Graph theory], [http://en.wikipedia.org/ Wikipedia].
[[Category:Combinatorics]]
[[Category:Combinatorics]]
[[Category:Graph Theory]]
[[Category:Graph Theory]]
[[Category:Mathematics]]
[[Category:Mathematics]]
[[Category:Visualization]
[[Category:Visualization]]