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

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

Граф с 6 вершинами и 7 рёбрами, в котором вершина с номером 6 в левом верхнем углу — лист, или висячая вершина

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

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

Типы вершин

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

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

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

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

См. также

• Узел (информатика)
• Теория графов
• Глоссарий теории графов

Ссылки

• Giorgio Gallo, Stefano Pallotino. Shortest path algorithms (англ.) // Annals of Operations Research. — 1988. — Vol. 13, iss. 1. — P. 1—79. — doi:10.1007/BF02288320.
• К. Берж. Теория графов и её применение. — Москва: издательство Иностранной литературы, 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.
• Weisstein, Eric W. Graph Vertex (англ.) на сайте Wolfram MathWorld.