Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Граф с 6 вершинами и 7 ребрами, в котором вершина номер 6 в крайнем левом углу является вершиной листа или висячей вершиной

В математике , а точнее в теории графов , вершина (множественное число вершин ) или узел - это фундаментальная единица, из которой формируются графы: неориентированный граф состоит из набора вершин и набора ребер (неупорядоченных пар вершин), в то время как ориентированный граф состоит из множества вершин и множества дуг (упорядоченные пары вершин). На диаграмме графа вершина обычно представлена ​​кружком с меткой, а ребро представлено линией или стрелкой, идущей от одной вершины к другой.

С точки зрения теории графов, вершины рассматриваются как безликие и неделимые объекты, хотя они могут иметь дополнительную структуру в зависимости от приложения, из которого возникает граф; например, семантическая сеть - это граф, в котором вершины представляют концепции или классы объектов.

Две вершины, образующие ребро, называются концами этого ребра, а ребро инцидентно вершинам. Вершина w называется смежной с другой вершиной v, если граф содержит ребро ( v , w ). Окрестность из вершины V является подграфа графа, образованный всеми вершинами смежных с  V .

Типы вершин [ править ]

Небольшой пример сети с 8 вершинами и 10 ребрами.
Пример сети с 8 вершинами (из которых одна изолирована) и 10 ребрами.

Степень вершины, обозначим δ (v) в графе называется число ребер падающего на него. Изолированная вершина является вершиной с нулевой степенью; то есть вершина, которая не является конечной точкой какого-либо ребра (на изображении в качестве примера показана одна изолированная вершина). [1] лист вершина (также подвесная вершина ) является вершиной со степенью один. В ориентированном графе можно отличить исходящую степень (количество исходящих ребер), обозначенную 𝛿 + (v), от степени (количество входящих ребер), обозначенную 𝛿 - (v); источник вершина является вершиной с нулевой полустепенью захода, а раковина вершиной является вершиной с полустепенью нуля. Симплициальная вершинатот, чьи соседи образуют клику : каждые два соседа смежны. Универсальная вершина является вершиной , которая находится рядом с каждой другой вершины в графе.

Разреза вершина является вершиной устранение которых будет отключить оставшийся граф; вершина сепаратор представляет собой набор вершин устранения которых будет отключить оставшийся граф на мелкие кусочки. К-вершинный связной граф представляет собой график , в котором удалении меньше , чем K вершины всегда оставляет оставшийся граф подключен. Независимое множество представляет собой набор вершин никаких два из которых являются смежными, а вершина крышка представляет собой набор вершин , которые включают в себя , по меньшей мере один конце каждого ребра в графе. Пространство вершин графа - это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа.

Граф является вершинно-транзитивным, если он имеет симметрии, которые отображают любую вершину в любую другую вершину. В контексте перечисления графов и изоморфизм графов , важно различать между помеченными вершинами и немечеными вершинами . Помеченная вершина - это вершина, которая связана с дополнительной информацией, которая позволяет отличить ее от других помеченных вершин; два графа можно считать изоморфными, только если соответствие между их вершинами объединяет вершины с одинаковыми метками. Непомеченная вершина - это вершина, которая может быть заменена любой другой вершиной только на основании ее смежности в графе, а не на основе какой-либо дополнительной информации.

Вершины в графах аналогичны, но не то же самое, что вершины многогранников : остов многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое расположение), т.е. не предполагается, что он присутствует в теории графов. Вершина фигуры вершины в многогранника аналогично окрестности вершины в графе.

См. Также [ править ]

Ссылки [ править ]

  1. ^ Файл: 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 .