GRAPH THEORY

the mathematical theory of networks. A graph-in the sense used in graph theory-consists of nodes (also called points, or vertices) and of edges (lines) connecting certain pairs of nodes. The exact geometric pattern is not specified. In a directed graph (digraph) all edges are given a direction. A road or electrical network, a hydrocarbon molecule, the vertices and edges of a polyhedron, a chain of command, and the family trees of a population may be pictured as graphs or digraphs. Two graphs are associated with a political map. One is the graph of boundaries. The other is obtained by placing a node inside each region and connecting each pair of nodes separated by a boundary. In 1735 the Swiss mathematician Leonhard Euler published an analysis of the Knigsberg bridge problem, an old puzzle concerning the possibility of crossing-in a tour that includes no bridge twice-every one of seven bridges that span a forked river that flows past an island. Euler's proof that no such path exists and his generalization of the problem to all possible networks are now recognized as the origin of both graph theory and topology. A colouring of a graph means a colouring of the nodes so that connected nodes have different colours. A scheduling problem can sometimes be formulated as a graph-colouring problem. For example, if students and teachers have been assigned to classes and it is necessary to find time slots for them, the classes may be represented as nodes and two nodes are connected if they have a common teacher or student. A colouring will give a conflict-free schedule; the colours represent the time slots.