Gráf centruma

Az ábrán látható gráf centrumában található csúcsok pirosra vannak színezve. Három olyan A csúcs van, melyre d(A, B) ≤ 3 az összes B csúcsra. A fekete csúcsok legalább 4 távolságra vannak valamely másik csúcstól.

A matematika, azon belül a gráfelmélet területén egy gráf középpontja, centruma vagy közepe (center vagy Jordan center) azoknak a csúcsoknak az összessége, melyek excentricitása minimális, tehát az olyan u csúcsok halmaza, melyeknek a többi v csúcstól való legnagyobb d(u,v) távolsága minimális. Ezzel ekvivalens megfogalmazás szerint azon csúcsok halmaza, melyek excentricitása megegyezik a gráf sugarával. A gráf közepében lévő csúcsok (central points) minimalizálják a gráf többi csúcsától való távolságot.

A gráfcentrum megkeresése jól jön a létesítmény-elhelyezési problémák megoldásánál; itt a cél a létesítménytől való távolság legrosszabb esetének minimalizálása. Például egy kórháznak a centrumba helyezésével csökkenthető az a leghosszabb út, amit egy mentőautónak a kórházig meg kell tennie.

A gráfcentrum ideája kapcsolódik a kapcsolatháló-elemzésben használt közelség-központisági mértékhez, ami a d(A,B) távolságok átlagának reciproka.

Fordítás

• Ez a szócikk részben vagy egészben a Graph center című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.