Graphs
In mathematics, a graph is an abstract set of points (vertices) and lines (edges) that connect the vertices. A graph is an abstraction widely used to symbolically represent such varying things as electrical circuitry, computer networks, molecular diagrams, transportation and traffic problems, pipeline flows, and so on. The theory of graphs is intimately connected with topology, combinatorics, electrical engineering, computer science, and many other fields and disciplines. Graphs have been used to model social structures (think about a family tree, which is just a special kind of graph representing ancestor-descendant relationships) and other problems in the humanities where relationships between multiple entities needs to be symbolically represented. The study and design of graph algorithms is a primal concern in computer science.
Graph theory had its origins in a seminal 1736 contribution of the famous Swiss mathematician Leonhard Euler, who was then living in Germany. In Königsberg, Germany, the Pregel river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. People who lived in the area wondered whether it was possible to traverse each of the bridges exactly once and return to one's starting point. This remained an open question for many years; no one had been able to show how to do it, but none had a proof that it wasn't possible, either. Euler's analysis came up with the answer, which was in the negative.
Euler's insight was in reducing the concrete problem of the bridges over the Pregel at Königsberg into an abstract representation using a graph. He considered that the situation of the bridges could be abstracted to a graph having four points connected in a certain way with seven edges. He then had to analyze whether it was possible to traverse the edges of the graph once each, so as to return to the point from whence one began. Such a path is now called, in his honor, an Eulerian path, and the criterion he evolved for the existence of such a path in a graph allowed for a simple proof to show why it was not possible to solve the Königsberg Bridge Problem, which is now given as an introduction to most graph theory texts.
After the solution to this problem by Euler, the study of graph theory was strangely relegated to the back burner for over two hundred years, but the period after the second world war saw a great increase in interest, motivated to a great extent by the rapid pace of research in the sciences, as well as the needs of the industry.
Formally, a graph may be defined by saying that a graph (commonly represented by the letter G) consists of two sets: a finite, nonempty set V(G) of vertices, and a finite, possibly empty set E(G) of edges. Edges are commonly represented by pairs of vertices that they connect--it is a common restriction on graphs that any two vertices be connected by at most one edge. Graphs are considered to be undirected if the edges connecting the vertices have no directional arrows; such graphs are appropriate when all edges may be considered to be bidirectional. Formally, we would say that the pair of vertices that represent an edge are unordered. Graphs that do have directions on the edges are called, not surprisingly, directed graphs or digraphs. The vertex-pairs representing edges in a digraph are considered to be ordered pairs. A directed graph is appropriate to represent situations such as dependency relations, which may not be bidirectional.
A loop (or self-loop) on a vertex in a graph is an edge that connects a vertex with itself; a cycle or circuit is a sequence of edges such that by traversing the edges in order, one returns to the vertex from which one began. An Eulerian circuit (invented by Euler as noted above) is a circuit that traverses each of the edges once only. A Hamiltonian circuit (named after the Englishman Sir William Hamilton, who invented a puzzle requiring one to find such a circuit in a specific graph with twenty vertices) is a circuit that traverses each of the vertices just once. (Finding a Hamiltonian circuit for an arbitrary graph continues to be one of the hard problems in mathematics and computer science.) The degree of a vertex in an undirected graph is the number of edges (other than loops) connecting to that vertex. For a directed graph, we have two kinds of degrees, an in-degree, or the number of edges pointing in to the vertex, and an out-degree, or the number of edges pointing out of it.
A complete graph is a graph with n vertices where any two vertices have an edge between them. Two graphs are considered to be isomorphic if they have the same numbers of vertices, and the same edge-relationships among them. A graph is connected if its vertices have at least one edge each connecting them. A graph is acyclic if it has no circuits (cycles). A special type of interesting graph is a directed acyclic graph (abbreviated DAG). An undirected connected acyclic graph is called a tree--this kind of graph is specially interesting also (think family trees again).
This is the complete article, containing 878 words
(approx. 3 pages at 300 words per page).
