Grado (teoría de grafos)

En teoría de grafos , el grado (o valencia ) de un vértice de un grafo es el número de aristas incidentes al vértice; en un multigrafo , un bucle contribuye con 2 al grado de un vértice, por los dos extremos de la arista. ^{[ 1 ]} El grado de un vértice${\displaystyle v}$se denota${\displaystyle \deg(v)}$o${\displaystyle \deg v}$El grado máximo de un grafo${\displaystyle G}$se denota por${\displaystyle \Delta (G)}$y es el máximo de${\displaystyle G}$grados de los vértices de 's'. El grado mínimo de un grafo se denota por${\displaystyle \delta (G)}$y es el mínimo de${\displaystyle G}$grados de los vértices 's'. En el multigrafo que se muestra a la derecha, el grado máximo es 5 y el grado mínimo es 0.

En un grafo regular , cada vértice tiene el mismo grado, por lo que podemos hablar del grado del grafo. Un grafo completo (denotado${\displaystyle K_{n}}$, dónde${\displaystyle n}$es el número de vértices en el grafo) es un tipo especial de grafo regular donde todos los vértices tienen el grado máximo posible,${\displaystyle n-1}$.

En un grafo con signos , el número de aristas positivas conectadas a un vértice se denomina grado positivo y el número de aristas negativas conectadas se denomina grado negativo . ^{[ 2 ]}

La fórmula de suma de grados establece que, dado un gráfico${\displaystyle G=(V,E)}$,

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$.

La fórmula implica que en cualquier grafo no dirigido, el número de vértices con grado impar es par. Esta afirmación (así como la fórmula de la suma de grados) se conoce como el lema del apretón de manos . Este último nombre proviene de un problema matemático popular, que consiste en demostrar que en cualquier grupo de personas, el número de personas que han estrechado la mano de un número impar de otras personas del grupo es par. ^{[ 3 ]}

La secuencia de grados de un grafo no dirigido es la secuencia no creciente de los grados de sus vértices; ^{[ 4 ]} para el grafo anterior es (5, 3, 3, 2, 2, 1, 0). La secuencia de grados es un invariante de grafos , por lo que los grafos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica de forma única un grafo; en algunos casos, grafos no isomorfos tienen la misma secuencia de grados. Un grafo que se identifica salvo isomorfismo por su secuencia de grados se denomina unigrafo y la secuencia de grados correspondiente se denomina unigráfica.

The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some simple graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The inverse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs (forming a matching), and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can be solved by either the Erdős–Gallai theorem or the Havel–Hakimi algorithm. The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.

More generally, the degree sequence of a hypergraph is the non-increasing sequence of its vertex degrees. A sequence is ${\displaystyle k}$-graphic if it is the degree sequence of some simple ${\displaystyle k}$-uniform hypergraph. In particular, a ${\displaystyle 2}$-graphic sequence is graphic. Deciding if a given sequence is ${\displaystyle k}$-graphic is doable in polynomial time for ${\displaystyle k=2}$ via the Erdős–Gallai theorem but is NP-complete for all ${\displaystyle k\geq 3}$.^[5]

• A vertex with degree 0 is called an isolated vertex.
• A vertex with degree 1 is called a leaf vertex or end vertex or a pendant vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of trees in graph theory and especially trees as data structures.
• A vertex with degree n − 1 in a graph on n vertices is called a dominating vertex.

• If each vertex of the graph has the same degree k, the graph is called a k-regular graph and the graph itself is said to have degree k. Similarly, a bipartite graph in which every two vertices on the same side of the bipartition as each other have the same degree is called a biregular graph.
• An undirected, connected graph has an Eulerian path if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
• A directed graph is a directed pseudoforest if and only if every vertex has outdegree at most 1. A functional graph is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
• By Brooks' theorem, any graph G other than a clique or an odd cycle has chromatic number at most Δ(G), and by Vizing's theorem any graph has chromatic index at most Δ(G) + 1.
• A k-degenerate graph is a graph in which each subgraph has a vertex of degree at most k.

• Indegree, outdegree for digraphs
• Degree distribution
• Degree sequence for bipartite graphs

• Erdős, P.; Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal"(PDF). Matematikai Lapok (in Hungarian). 11: 264–274..
• Havel, Václav (1955). "A remark on the existence of finite graphs". Časopis Pro Pěstování Matematiky (in Czech). 80 (4): 477–480. doi:10.21136/CPM.1955.108220.
• Hakimi, S. L. (1962). "On realizability of a set of integers as degrees of the vertices of a linear graph. I". Journal of the Society for Industrial and Applied Mathematics. 10 (3): 496–506. doi:10.1137/0110037. MR 0148049..
• Sierksma, Gerard; Hoogeveen, Han (1991). "Seven criteria for integer sequences being graphic". Journal of Graph Theory. 15 (2): 223–231. doi:10.1002/jgt.3190150209. MR 1106533..