Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Основная единица, из которой формируются графы.
Fundamental unit of which graphs are formed
В дискретной математике, и в частности в теории графов, вершина (множественное число – вершины) или узел является фундаментальной единицей, из которой формируются графы: ненаправленный граф состоит из множества вершин и множества рёбер (неупорядоченных пар вершин), а направленный граф – из множества вершин и множества дуг (упорядоченных пар вершин). На схеме графа вершина обычно изображается кругом с меткой, а ребро – линией или стрелкой, соединяющей две вершины. С точки зрения теории графов, вершины рассматриваются как не имеющие особенностей и неделимые объекты, хотя они могут иметь дополнительную структуру в зависимости от области применения графа; например, семантическая сеть – это граф, в котором вершины представляют понятия или классы объектов. Две вершины, образующие ребро, называются конечными точками этого ребра, а ребро называется инцидентным вершинам. Вершина w считается смежной с другой вершиной v, если граф содержит ребро (v, w). Окрестность вершины v – это индуцированный подграф графа, образованный всеми вершинами, смежными с v.
In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another. From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects. The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex w is said to be adjacent to another vertex v if the graph contains an edge (v,w). The neighborhood of a vertex v is an induced subgraph of the graph, formed by all vertices adjacent to v.
Типы вершин
Степень вершины, обозначаемая δ(v) в графе, — это количество рёбер, инцидентных ей. Изолированная вершина — это вершина со степенью ноль; то есть вершина, которая не является концом ни одного ребра (например, изображение иллюстрирует одну изолированную вершину). Вершина-лист (также подвешенная вершина) — это вершина со степенью один. В ориентированном графе различают внешнюю степень (количество исходящих рёбер), обозначаемую δ+(v), и внутреннюю степень (количество входящих рёбер), обозначаемую δ−(v); вершина-источник — это вершина с внутренней степенью ноль, а вершина-сток — это вершина с внешней степенью ноль. Симплициальная вершина — это вершина, соседи которой образуют клику: любые две соседние вершины смежны. Универсальная вершина — это вершина, смежная со всеми остальными вершинами в графе. Разделяющая вершина — это вершина, удаление которой разъединит оставшуюся часть графа; разделитель вершин — это набор вершин, удаление которых разъединит оставшуюся часть графа на небольшие компоненты. k-связный граф — это граф, в котором удаление менее k вершин всегда оставляет оставшуюся часть графа связной. Независимое множество — это набор вершин, никакие две из которых не смежны, а вершинное покрытие — это набор вершин, включающий хотя бы один конец каждого ребра в графе. Вершинное пространство графа — это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа. Граф является вершинно-транзитивным, если он имеет симметрии, отображающие любую вершину в любую другую вершину. В контексте перечисления графов и изоморфизма графов важно различать помеченные вершины и непомеченные вершины. Помеченная вершина — это вершина, связанная с дополнительной информацией, позволяющей отличить её от других помеченных вершин; два графа могут считаться изоморфными только в том случае, если соответствие между их вершинами сопоставляет вершины с одинаковыми метками. Непомеченная вершина — это вершина, которую можно заменить любой другой вершиной, основываясь только на её смежностях в графе и не основываясь на какой-либо дополнительной информации. Вершины в графах аналогичны, но не идентичны вершинам многогранников: скелет многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое положение), которая не предполагается в теории графов. Вершинная фигура вершины в многограннике аналогична окрестности вершины в графе.
The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex). A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿 +(v), from the indegree (number of incoming edges), denoted 𝛿−(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose neighbors form a clique: every two neighbors are adjacent. A universal vertex is a vertex that is adjacent to every other vertex in the graph. A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k vertex connected graph is a graph in which removing fewer than k vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices. A graph is vertex transitive if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration and graph isomorphism it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information. Vertices in graphs are analogous to, but not the same as, vertices of polyhedra: the skeleton of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The vertex figure of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.