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

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

Две вершины, образующие ребро, называются конечными вершинами ребра и говорят, что ребро инцидентно вершинам. Говорят, что вершина 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 : .
• (англ.) ( . Теория графов и её применение. — Москва: издательство Иностранной литературы, 1962.
• Gary Chartrand. . — 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. (англ.) на сайте Wolfram MathWorld .