Often the lines on a graph are used to represent relationships between objects (represented by dots). Depending on the application, edges may or may not have a direction, as indicated by an arrow (see directed graph); edges joining a node to itself may or may not be allowed, and nodes and/or edges may be assigned weights (see 'weighted graph' below). A path is a series of nodes such that each node is adjacent to both the preceding and succeeding node. A path is considered simple if none of the nodes in the path is repeated. The length of a path is the number of edges that the path uses, counting multiple edges multiple times. If it's possible to establish a path from any node to any other node of a graph, the graph is said to be a connected graph. A circuit or cycle is a path that begins and ends with the same node and has a length at least two. A tree is a connected acyclic graph, i.e., a graph without any circuits. A complete graph is one in which every node is adjacent to every other node. An Euler path in a graph is a path that uses each edge precisely once. If such a path exists, the graph is said to be traversable. An Euler circuit is a path that traverses each edge precisely once. A Hamilton path in a graph is a path that visits each node once and only once; a Hamiltonian circuit is a circuit that visits each node once and only once. Well known problems whose solution involves graphs and graph theory include the four-color problem and the traveling salesman problem.
tangled graphA graph in 3-dimensional space; equivalently, a graph drawn in the plane so that when edges cross, one edge goes over the other.
weighted graphA graph having a weight, or number, associated with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc. Also known as an edge-weighted graph.
Related entry lattice
Related category GRAPHS AND GRAPH THEORY
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact