Graph center (original) (raw)
The center (or Jordan center) of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices u where the greatest distance d(u,v) to other vertices v is minimal. 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. This is also known as the vertex 1-center problem and can be extended to the vertex k-center problem.
| Property | Value |
|---|---|
| dbo:abstract | The center (or Jordan center) of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices u where the greatest distance d(u,v) to other vertices v is minimal. 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. This is also known as the vertex 1-center problem and can be extended to the vertex k-center problem. 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. The center can be found using the Floyd–Warshall algorithm. Another algorithm has been proposed based on matrix calculus. The concept of the center of a graph is related to the closeness centrality measure in social network analysis, which is the reciprocal of the mean of the distances d(A,B). (en) Центр (или центр Жордана) графа — это множество всех вершин с минимальным эксцентриситетом. То есть множество всех вершин A, для которой максимальное расстояние d(A,B) до других вершин B минимально. Эквивалентно, это множество вершин с эксцентриситетом, равным радиусу графа. Нахождение центра графа полезно для задач размещения предприятий, целью которых является минимизация наиболее дальних расстояний до предприятия. Например, размещение госпиталя в центре объекта уменьшает максимальное расстояние, которое приходится преодолевать машинам медицинской помощи. Концепция центра графа связана с измерением центральности по близости в анализе социальных сетей, которая равна обратной величине к среднему расстояний d(A,B). (ru) Центр (або центр Жордана) графа — це множина всіх вершин з найменшим ексцентриситетом. Тобто множина всіх вершин A, для яких найбільша відстань d(A,B) до інших вершин B найменша. Еквівалентно, це множина вершин з ексцентриситетом, рівним радіусу графа. Відшукання центра графа корисне для задач розміщення підприємств, метою яких є мінімізація найбільших відстаней до підприємства. Наприклад, розміщення шпиталю в центрі об'єкта зменшує найбільшу відстань, яку доводиться долати автомобілям швидкої допомоги. Концепція центра графа пов'язана з вимірюванням центральності за близькістю в аналізі соціальних мереж, яка дорівнює величині, оберненій до середньої відстані d(A,B). (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Graphcenter.svg?width=300 |
| dbo:wikiPageID | 10447275 (xsd:integer) |
| dbo:wikiPageLength | 2858 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1070878029 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Camille_Jordan dbc:Graph_theory_objects dbr:Social_network_analysis dbr:Graph_(discrete_mathematics) dbr:Closeness_centrality dbr:Floyd–Warshall_algorithm dbr:Eccentricity_(graph_theory) dbr:Radius_(graph_theory) dbr:Facility_location_problem dbr:Vertex_k-center_problem dbr:File:Graphcenter.svg |
| dbp:wikiPageUsesTemplate | dbt:Short_description dbt:Use_American_English dbt:Use_mdy_dates |
| dct:subject | dbc:Graph_theory_objects |
| gold:hypernym | dbr:Set |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | The center (or Jordan center) of a graph is the set of all vertices of minimum eccentricity, that is, the set of all vertices u where the greatest distance d(u,v) to other vertices v is minimal. 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. This is also known as the vertex 1-center problem and can be extended to the vertex k-center problem. (en) Центр (или центр Жордана) графа — это множество всех вершин с минимальным эксцентриситетом. То есть множество всех вершин A, для которой максимальное расстояние d(A,B) до других вершин B минимально. Эквивалентно, это множество вершин с эксцентриситетом, равным радиусу графа. Нахождение центра графа полезно для задач размещения предприятий, целью которых является минимизация наиболее дальних расстояний до предприятия. Например, размещение госпиталя в центре объекта уменьшает максимальное расстояние, которое приходится преодолевать машинам медицинской помощи. (ru) Центр (або центр Жордана) графа — це множина всіх вершин з найменшим ексцентриситетом. Тобто множина всіх вершин A, для яких найбільша відстань d(A,B) до інших вершин B найменша. Еквівалентно, це множина вершин з ексцентриситетом, рівним радіусу графа. Відшукання центра графа корисне для задач розміщення підприємств, метою яких є мінімізація найбільших відстаней до підприємства. Наприклад, розміщення шпиталю в центрі об'єкта зменшує найбільшу відстань, яку доводиться долати автомобілям швидкої допомоги. (uk) |
| rdfs:label | Graph center (en) Центр графа (ru) Центр графа (uk) |
| owl:sameAs | freebase:Graph center yago-res:Graph center wikidata:Graph center http://bn.dbpedia.org/resource/লেখচিত্রের_কেন্দ্র dbpedia-hu:Graph center dbpedia-ru:Graph center dbpedia-uk:Graph center https://global.dbpedia.org/id/4kFsk |
| prov:wasDerivedFrom | wikipedia-en:Graph_center?oldid=1070878029&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Graphcenter.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_center |
| is dbo:wikiPageDisambiguates of | dbr:Center |
| is dbo:wikiPageRedirects of | dbr:Graph_centre dbr:Centre_of_a_graph dbr:Center_(Graph_theory) dbr:Center_of_a_graph |
| is dbo:wikiPageWikiLink of | dbr:Glossary_of_graph_theory dbr:Graph_centre dbr:Tree_(graph_theory) dbr:Centered_tree dbr:Center dbr:Central_Point dbr:Facility_location_problem dbr:Centre_of_a_graph dbr:Center_(Graph_theory) dbr:Center_of_a_graph |
| is foaf:primaryTopic of | wikipedia-en:Graph_center |
