Weighted Graphs and Networks
A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers. They may be restricted to rational numbers or integers. Certain algorithms require further restrictions on weights; for instance, Dijkstra's algorithm works properly only for positive weights. The weight of a path or the weight of a tree in a weighted graph is the sum of the weights of the selected edges. Sometimes a non-edge is labeled by a special weight representing infinity. Sometimes the word cost is used instead of weight. When stated without any qualification, a graph is always assumed to be unweighted. In some writing on graph theory the term network is a synonym for a weighted graph. A network may be directed or undirected, it may contain special vertices (nodes), such as source or sink. The classical network problems include:
- minimum cost spanning tree,
- shortest paths,
- maximal flow (and the max-flow min-cut theorem)
Read more about this topic: Glossary Of Graph Theory
Famous quotes containing the word networks:
“The great networks are there to prove that ideas can be canned like spaghetti. If everything ends up by tasting like everything else, is that not the evidence that it has been properly cooked?”
—Frederic Raphael (b. 1931)