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