Vertex (graph theory)

	Email		Print
	Bookmark		Link

Vertex (graph theory)

For other uses, see vertex
Vertex

Vertex may refer to:...
.

In graph theory

Graph theory

Discussion

Ask a question about 'Vertex (graph theory)'

Start a new discussion about 'Vertex (graph theory)'

Answer questions from other users

Full Discussion Forum

Encyclopedia

For other uses, see vertex
Vertex

Vertex may refer to:...
.

In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, a vertex (plural vertices) or node is the fundamental unit out 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). 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

Semantic network

A semantic network is a network which represents semantic relations between the concepts. This is often used as a form of knowledge representation....
is a graph in which the vertices represent concepts or classes of objects.

The two vertices forming an edge are said to be its endpoints, 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.

The degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
of a vertex 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. A leaf vertex is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges) from the indegree (number of incoming edges); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero.

A cut vertex

Cut vertex

In mathematics and computer science, a cut vertex or articulation point is a Vertex of a Graph such that removal of the vertex causes an increase in the number of connected component s....
is a vertex the removal of which would disconnect the remaining graph; a vertex separator

Vertex separator

In graph theory, a subset is a vertex separator for nonadjacent vertices and if the removal of from the graph separates and into distinct connected component s....
is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k-vertex-connected graph

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected for k < |V| if is connectivity for all with ....
is a graph in which removing fewer than k vertices always leaves the remaining graph connected. An independent set

Independent set

In graph theory, an independent set or stable set is a set of Vertex in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in , there is no graph theory connecting the two....
is a set of vertices no two of which are adjacent, and a vertex cover

Vertex cover

In the mathematics discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph touches at least one element of the set....
is a set of vertices that includes the 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

Vertex-transitive graph

In mathematics, a vertex-transitive graph is a Graph G such that, given any two vertices v1 and v2 of G, there is some Graph automorphism...
if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration

Graph enumeration

Graph enumeration is a subject of graph theory that deals with the problems of the following type: find how many non-isomorphic graphs have a given property....
and graph isomorphism

Graph isomorphism

In graph theory, an isomorphism of graph s G and H is a bijection between the vertex sets of G and Hsuch that any two vertices u and v of G are adjacent in G if and only if ? and ? are adjacent in H....
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

Vertex (geometry)

In geometry, a vertex is a special kind of point which describes the corners or intersections of geometric shapes. Vertices are commonly used in computer graphics to define the corners of surfaces in 3d models, where each such point is given as a vector....
: 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

Vertex figure

In geometry a vertex figure is, broadly speaking, the figure exposed when a corner of a polyhedron or polytope is sliced off....
of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.

In a directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a Set V, whose element are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows....
, the forward star of a node is defined as its outgoing edges. In a Graph with the set of vertices and the set of edges , the forward star of can be described as .

Vertex (graph theory)

External links