Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Февраль 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В математике , а точнее в теории графов , вершина (множественное число вершин ) или узел - это фундаментальная единица, из которой формируются графы: неориентированный граф состоит из набора вершин и набора ребер (неупорядоченных пар вершин), в то время как ориентированный граф состоит из множества вершин и множества дуг (упорядоченные пары вершин). На диаграмме графа вершина обычно представлена кружком с меткой, а ребро представлено линией или стрелкой, идущей от одной вершины к другой.
С точки зрения теории графов, вершины рассматриваются как безликие и неделимые объекты, хотя они могут иметь дополнительную структуру в зависимости от приложения, из которого возникает граф; например, семантическая сеть - это граф, в котором вершины представляют концепции или классы объектов.
Две вершины, образующие ребро, называются концами этого ребра, а ребро инцидентно вершинам. Вершина w называется смежной с другой вершиной v, если граф содержит ребро ( v , w ). Окрестность из вершины V является подграфа графа, образованный всеми вершинами смежных с V .
Типы вершин [ править ]
Степень вершины, обозначим δ (v) в графе называется число ребер падающего на него. Изолированная вершина является вершиной с нулевой степенью; то есть вершина, которая не является конечной точкой какого-либо ребра (на изображении в качестве примера показана одна изолированная вершина). [1] лист вершина (также подвесная вершина ) является вершиной со степенью один. В ориентированном графе можно отличить исходящую степень (количество исходящих ребер), обозначенную 𝛿 + (v), от степени (количество входящих ребер), обозначенную 𝛿 - (v); источник вершина является вершиной с нулевой полустепенью захода, а раковина вершиной является вершиной с полустепенью нуля. Симплициальная вершинатот, чьи соседи образуют клику : каждые два соседа смежны. Универсальная вершина является вершиной , которая находится рядом с каждой другой вершины в графе.
Разреза вершина является вершиной устранение которых будет отключить оставшийся граф; вершина сепаратор представляет собой набор вершин устранения которых будет отключить оставшийся граф на мелкие кусочки. К-вершинный связной граф представляет собой график , в котором удалении меньше , чем K вершины всегда оставляет оставшийся граф подключен. Независимое множество представляет собой набор вершин никаких два из которых являются смежными, а вершина крышка представляет собой набор вершин , которые включают в себя , по меньшей мере один конце каждого ребра в графе. Пространство вершин графа - это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа.
Граф является вершинно-транзитивным, если он имеет симметрии, которые отображают любую вершину в любую другую вершину. В контексте перечисления графов и изоморфизм графов , важно различать между помеченными вершинами и немечеными вершинами . Помеченная вершина - это вершина, которая связана с дополнительной информацией, которая позволяет отличить ее от других помеченных вершин; два графа можно считать изоморфными, только если соответствие между их вершинами объединяет вершины с одинаковыми метками. Непомеченная вершина - это вершина, которая может быть заменена любой другой вершиной только на основании ее смежности в графе, а не на основе какой-либо дополнительной информации.
Вершины в графах аналогичны, но не то же самое, что вершины многогранников : остов многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое расположение), т.е. не предполагается, что он присутствует в теории графов. Вершина фигуры вершины в многогранника аналогично окрестности вершины в графе.
См. Также [ править ]
Ссылки [ править ]
- ^ Файл: Small Network.png ; пример изображения сети с 8 вершинами и 10 ребрами
- Галло, Джорджио; Паллотино, Стефано (1988). «Алгоритмы кратчайшего пути». Анналы исследований операций . 13 (1): 1–79. DOI : 10.1007 / BF02288320 .
- Берже, Клод , Теория графических и других приложений . Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii + 277 стр. (Английское издание, Wiley 1961; Methuen & Co, New York 1962; русский, Москва 1961; испанский, Мексика 1962; румынский, Бухарест, 1969; китайский, Шанхай, 1963) ; Второе издание первого английского издания 1962 года. Довер, Нью-Йорк, 2001)
- Чартран, Гэри (1985). Вводная теория графов . Нью-Йорк: Дувр. ISBN 0-486-24775-9.
- Биггс, Норман; Ллойд, EH; Уилсон, Робин Дж. (1986). Теория графов, 1736-1936 гг . Оксфорд [Оксфордшир]: Clarendon Press. ISBN 0-19-853916-9.
- Харари, Фрэнк (1969). Теория графов . Ридинг, Массачусетс: Addison-Wesley Publishing. ISBN 0-201-41033-8.
- Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление . Нью-Йорк, Academic Press. ISBN 0-12-324245-2.
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Вершина графа» . MathWorld .