Вершина (теория графов)

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

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

С точки зрения теории графов, вершины рассматриваются как лишённые характерных черт неделимые объекты, хотя они могут представлять некоторые структуры, зависящие от задачи, из которой возник граф. Например, семантическая сеть — это граф, в котором вершины представляют понятие класса объектов.

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

Типы вершин[править | править исходный текст]

Степенью вершины графа называется число рёбер, инцидентных ей. Вершина называется изолированной, если её степень равна нулю. То есть, это вершина, не являющаяся конечной ни для какого ребра. Вершина называется листом (или висячей), если вершина имеет степень единица. В ориентированном графе различают полустепень исхода (число исходящих дуг) и полустепень захода (число входящих рёбер). Источником называется вершина с нулевой полустепенью захода, а вершина с нулевой степенью исхода называется стоком.

Шарниром называется вершина, удаление которой приводит к увеличению компонент связности графа. Вершинным сепаратором называется набор вершин, удаление которых приводит к увеличению компонент связности графа. Вершинно k-связный граф — это граф, в котором удаление менее k вершин всегда оставляет граф связным. Независимым множеством называется множество вершин, никакие два из которых не являются смежными, а вершинным покрытием называется множество вершин, которое включает хотя бы одну конечную вершину любого ребра графа. Векторным пространством вершин[en] графа называется векторное пространство, имеющее в качестве базиса вектора, соответствующие вершинам графа (над полем чисел {0, 1}).[1][2]

Граф называется вершинно-транзитивным, если он имеет симметрии, которые переводят любую вершину в любую другую вершину. В контексте перечисления графов[en] и изоморфизма графов важно различать помеченные вершины и непомеченные вершины . Помеченная вершина — это связанная с вершиной дополнительная информация, которая позволяет отличить её от других помеченных вершин. Два графа можно считать изоморфныvb только если изоморфизм переводит вершины в вершины, имеющие те же метки. Непомеченные вершины могут при этом переводиться в другие вершины, основываясь только на смежности и не используя дополнительную информацию.

Вершины графа аналогичны вершинам многоранника[en], но это не то же самое — скелет[en] многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (геометрическое местоположение), которая игнорируется в теории графов. Фигура вершины[en] многогранника аналогична окрестности вершины графа.

Смотрите также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. М. Свами, К. Туласимаран Графы, сети и алгоритмы. — Москва: Мир, 1984. — С. 62-76. глава 4
  2. Рейнгард Дистель Теория графов. — Новосибирск: Издательство Института Математики, 2002. — С. 35.

Ссылки[править | править исходный текст]

  • Giorgio Gallo, Stefano Pallotino Shortest path algorithms // Annals of Operations Research. — 1988. — В. 1. — Т. 13. — С. 1–79. — DOI:10.1007/BF02288320
  • К. Берж[en] Теория графов и её применение. — Москва: издательство Иностранной литературы, 1962.
  • Gary Chartrand Introductory graph theory. — New York: Dover, 1985. — ISBN 0-486-24775-9
  • Norman Biggs, E. H. Lloyd, Robin J. Wilson Graph theory, 1736-1936. — Oxford [Oxfordshire]: Clarendon Press, 1986. — ISBN 0-19-853916-9
  • Frank Harary Graph theory. — Reading, Mass.: Addison-Wesley Publishing, 1969. — ISBN 0-201-41033-8
  • Frank Harary, Edgar M. Palmer, Graphical enumeration. — New York: Academic Press, 1973. — ISBN 0-12-324245-2

Внешние ссылкиs[править | править исходный текст]