В дискретной математике , а точнее в теории графов , вершина (множественное число вершин ) или узел — это фундаментальная единица, из которой формируются графы: неориентированный граф состоит из набора вершин и набора ребер (неупорядоченных пар вершин), а ориентированный граф состоит из набора вершин и набора дуг (упорядоченных пар вершин). На диаграмме графа вершина обычно изображается кружком с меткой, а ребро — линией или стрелкой, идущей от одной вершины к другой.
С точки зрения теории графов вершины рассматриваются как безликие и неделимые объекты , хотя они могут иметь дополнительную структуру в зависимости от приложения, из которого возникает граф; например, семантическая сеть — это граф, вершины которого представляют понятия или классы объектов.
Две вершины, образующие ребро, называются конечными точками этого ребра, а ребро называется инцидентным вершинам. Говорят, что вершина w смежна с другой вершиной v , если граф содержит ребро ( v , w ). Окрестность вершины v — это индуцированный подграф графа, образованный всеми вершинами, смежными с v .
Степень вершины, обозначаемой 𝛿(v) в графе , — это количество инцидентных ей ребер. Изолированная вершина — это вершина нулевой степени; то есть вершина, которая не является конечной точкой какого-либо ребра (пример изображения иллюстрирует одну изолированную вершину). [1] Листовая вершина (также висячая вершина ) — это вершина степени один. В ориентированном графе можно отличить исходящую степень (количество исходящих ребер), обозначаемую 𝛿 + (v), от входной степени (количество входящих ребер), обозначаемую 𝛿 - (v); исходная вершина — это вершина с нулевой степенью входа, а вершина стока — это вершина с нулевой степенью выхода. Симплициальная вершина — это вершина, соседи которой образуют клику : каждые два соседа смежны. Универсальная вершина — это вершина, смежная с любой другой вершиной графа.
Разрезанная вершина — это вершина, удаление которой отключило бы оставшийся граф; разделитель вершин — это набор вершин, удаление которых разъединило бы оставшийся граф на небольшие части. Граф с k-связностью — это граф, в котором удаление менее k вершин всегда оставляет оставшийся граф связным. Независимый набор — это набор вершин, ни одна из которых не является смежной, а вершинное покрытие — это набор вершин, который включает хотя бы одну конечную точку каждого ребра графа. Пространство вершин графа — это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа.
Граф является вершинно-транзитивным, если он имеет симметрии, отображающие любую вершину в любую другую вершину. В контексте нумерации графов и изоморфизма графов важно различать помеченные вершины и непомеченные вершины . Помеченная вершина — это вершина, связанная с дополнительной информацией, позволяющей отличить ее от других помеченных вершин; два графа можно считать изоморфными только в том случае, если соответствие между их вершинами образует пары вершин с одинаковыми метками. Непомеченная вершина — это вершина, которую можно заменить на любую другую вершину только на основе ее смежности в графе, а не на основе какой-либо дополнительной информации.
Вершины в графах аналогичны, но не тождественны вершинам многогранников : скелет многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое расположение), т.е. не предполагается, что он присутствует в теории графов. Фигура вершины вершины в многограннике аналогична окрестностям вершины в графе.
