In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper bound. Rigorously, any graph G is a bound graph if there exists a partial order ≤ on the vertices of G with the property that for any vertices u and v of G, uv is an edge of G if and only if u ≠ v and there is a vertex w such that u ≤ w and v ≤ w.
Bound graphs are sometimes referred to as upper bound graphs, but the analogously defined lower bound graphs comprise exactly the same class—any lower bound for ≤ is easily seen to be an upper bound for the dual partial order ≥.
Famous quotes containing the words bound and/or graph:
“Successful socialism depends on the perfectibility of man. Unless all, or nearly all, men are high-minded and clear-sighted, it is bound to be a rotten failure in any but a physical sense. Even through it is altruism, socialism means materialism. You can guarantee the things of the body to every one, but you cannot guarantee the things of the spirit to every one; you can guarantee only that the opportunity to seek them shall not be denied to any one who chooses to seek them.”
—Katharine Fullerton Gerould (1879–1944)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)