Graph center

Graph center

The center of a graph is the set of all vertices of minimum eccentricity. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius. Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.

Finding the center of a graph is useful in facility location problems where the goal is to minimize the worst-case distance to the facility. For example, placing a hospital at a central point reduces the longest distance the ambulance has to travel.

References

* James A. McHugh, [http://www.cs.njit.edu/mchugh/psswrd/web-course-materials/graph-theory/Algorithms-text.html Algorithmic Graph Theory] (Post-Script and PDF)
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Center — or centre (see American and British English spelling differences) may refer to: cience*Center (algebra), uses of center in algebra *Center of gravity (military) *Center (group theory), in abstract algebra, the subgroup consisting of those… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • center-of-gravity envelope — An envelope drawn on a graph included in aircraft certificates, data sheets, and flight manuals, showing the way the center of gravity may vary with the gross weight of an aircraft. Any combination of weight and the center of gravity that falls… …   Aviation dictionary

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Metric k-center — In graph theory, the metric k center, is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the distance of the… …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Storm Prediction Center — The Storm Prediction Center logo. Agency overview Formed October 1995 Preceding agencies …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”