A complete graph is a connected graph in which exactly one edge connects each pair of vertices. A complete graph with n vertices, denoted Kn, has n(n - 1)/2 edges (i.e., the nth triangular number), (n-1)! Hamilton circuits, and a chromatic number of n. Every vertex in Kn has degree n-1; therefore Kn has an Euler circuit if and only if n is odd. In a weighted complete graph, each edge has a number called a weight attached to it. Each path then has a total weight, which is the sum of the weights of the edges in the path.
Related entry traveling salesman problem
Related category GRAPHS AND GRAPH THEORY
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact