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