Glosario de teoría de grafos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de agosto de 2022; las comprobaciones requieren 2 ediciones .

Aquí se recopilan definiciones de términos de la teoría de grafos . Las referencias a términos en este diccionario (en esta página) están en cursiva .

# A B C D E F F G I K L M N O P R S T U V W Y Z _ _ _ _ _ _

A

Automorfismo - Un isomorfismo de un gráfico consigo mismo.
Un gráfico acíclico es un gráfico sin ciclos .

b

Una base de gráfico es un subconjunto mínimo del conjunto de vértices de gráfico desde el cual se puede alcanzar cualquier vértice de gráfico.
Un grafo infinito es un grafo que tiene infinitos vértices y/o aristas.
Bigraph - ver gráfico bipartito .
Un bloque es un gráfico sin bisagras .
El diseño de bloques con parámetros (v, k, λ) es un recubrimiento con multiplicidad λ de un gráfico completo en v vértices por gráficos completos en k vértices.

En

Valencia de vértice : ver grado de vértice .
Vértice , concepto básico de nodo : un punto donde los bordes y /o los arcos pueden converger/salir. El conjunto de vértices de un grafo G se denota por V(G).
Una cubierta de vértices es un conjunto de vértices en un gráfico tal que cada borde incide en al menos un vértice de este conjunto.
El peso de un borde es el valor asignado a un borde dado de un gráfico ponderado . Por lo general, el peso es un número real , en cuyo caso se puede interpretar como la " longitud " del borde.
Un gráfico ponderado es un gráfico , a cada borde del cual se le asigna un valor determinado ( peso de borde ). Ver gráfico etiquetado .
Un vértice colgante es un vértice cuyo grado es igual a 1 (es decir, ). $d(v)=1$

Un grafo completamente desconectado es un grafo regular de grado 0, es decir, un grafo sin aristas .
La altura de un árbol es el camino más largo desde la raíz hasta la hoja .

G

Un gráfico hamiltoniano es un gráfico que tiene un ciclo hamiltoniano .
Un camino hamiltoniano es un camino simple en un gráfico que contiene todos los vértices del gráfico exactamente una vez.
Un ciclo hamiltoniano es un ciclo simple en un gráfico que contiene todos los vértices del gráfico exactamente una vez.
Una realización geométrica es una figura cuyos vértices corresponden a los vértices del gráfico, bordes: los bordes del gráfico y los bordes de la figura conectan los vértices correspondientes a los vértices del gráfico.
Un gráfico geométrico es una figura plana de vértices, puntos del plano y bordes, líneas que conectan algunos pares de vértices. Puede representar cualquier gráfico de muchas maneras.
Una hipergrafía es una colección de un conjunto de vértices y un conjunto de hiperaristas (un subconjunto de la n-ésima potencia euclidiana del conjunto de vértices, es decir, las hiperaristas conectan un número arbitrario de vértices).
Los gráficos homeomorfos son gráficos obtenidos de un solo gráfico usando una secuencia de subdivisiones de borde.
Una cara es un área delimitada por aristas en un gráfico plano y no contiene vértices ni aristas del gráfico. La parte exterior del avión también forma una cara.
El gráfico es un concepto básico. Incluye un conjunto de vértices y un conjunto de aristas que es un subconjunto del cuadrado cartesiano del conjunto de vértices (es decir, cada arista conecta exactamente dos vértices).
Un gráfico de género g es un gráfico que se puede representar sin intersecciones en una superficie de género g y no se puede representar sin intersecciones en ninguna superficie de género g -1. En particular, los grafos planos tienen género 0.

D

Gráfico dual . Un grafo A se llama dual a un grafo plano B si los vértices del grafo A corresponden a las caras del grafo B , y dos vértices del grafo A están conectados por una arista si y solo si las caras correspondientes del grafo B tienen al menos una borde común.
Un grafo bipartito (o bígrafo , o un grafo par ) es un grafotal que el conjunto de vértices V se divide en dos subconjuntos que no se intersecany, y cualquier arista E es incidente con un vértice desdey un vértice desde(es decir, conecta un vértice dea un vértice de). Es decir, la coloración correcta del gráfico se realiza con dos colores. Los conjuntosyse denominan "partes" de un gráfico bipartito. Un grafo bipartito se llama "completo" si dos vértices cualesquiera deyson adyacentes. Si,, entonces el grafo bipartito completo se denota por. $G(V,E)$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $\izquierda|V_{1}\derecha|=a$ $\izquierda|V_{2}\derecha|=b$ $K_{{a,b}}$
Un grafo doblemente conexo es un grafo conexo que no tiene bisagras .
Un árbol es un gráfico conexo que no contiene ciclos .
El diámetro del gráfico es la distancia máxima entre vértices para todos los pares de vértices. La distancia entre vértices es el menor número de aristas en un camino que conecta dos vértices. $\mathrm {diámetro} (G)$
Longitud de la ruta : el número de bordes en la ruta (con repeticiones). Si la ruta es , entonces la longitud de M es igual a k (indicada por ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\izquierda|M\derecha|=k$
La longitud del camino es el número de arcos del camino (o la suma de las longitudes de sus arcos, si se dan estos últimos). Entonces, para el camino v 1 , v 2 , …, v n la longitud es n-1.
El arco es una arista orientada .
Un complemento de gráfico es un gráfico sobre el mismo conjunto de vértices que el original, pero los vértices están conectados por una arista si y solo si no hay arista en el gráfico original.

E

La mora de un grafo no dirigido G es una familia de subgrafos conexos del grafo G que son tangentes entre sí.

W

El gráfico de estrella es un gráfico bipartito completo. $K_{{1,b}}$

Y

Un vértice aislado es un vértice cuyo grado es 0 (es decir, no tiene aristas incidentes ).
isomorfismo . Se dice que dos grafos son isomorfos si hay una permutación de vértices tal que son iguales. En otras palabras, dos grafos se llaman isomorfos si existe una correspondencia biunívoca entre sus vértices y aristas que preserva la adyacencia y la incidencia (los grafos difieren solo en los nombres de sus vértices).
Un gráfico invariante es una característica numérica de un gráfico o su vector ordenado que caracteriza la estructura del gráfico de forma invariable con respecto a la renumeración de los vértices.
Un gráfico de intervalo es un gráfico cuyos vértices se pueden asignar uno a uno a los segmentos en el eje real de tal manera que dos vértices inciden en el mismo borde si y solo si los segmentos correspondientes a estos vértices se cruzan.
Incidente es un concepto que se usa solo en relación con una arista o un arco y un vértice: si son vértices y a es una arista que los conecta, entonces el vértice y la arista son incidentes, y el vértice y la arista también son incidentes. Dos vértices (o dos aristas) no pueden ser incidentes. Para denotar los vértices más cercanos (aristas), se utiliza el concepto de adyacencia . $v_{1},v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $mi$ $v_{2}$ $mi$

K

Una celda es un gráfico regular de la circunferencia más pequeñapara un grado dado de vértices.
Una camarilla es un subconjunto de vértices de gráficos que están completamente conectados entre sí, es decir, un subgráfico que es un gráfico completo .
- El número de camarilla es el número (G) de vértices en la camarilla más grande. Otros nombres son densidad, densidad.
- La camarilla máxima es la camarilla con el máximo número posible de vértices entre las camarillas del gráfico.
Una rueda (indicada por W n ) es un gráfico con n vértices (n ≥ 4) formado al conectar un solo vértice a todos los vértices de un ciclo ( n -1).
Un carcaj es solo un gráfico dirigido.
Un grafo finito es un grafo que contiene un número finito de vértices y aristas.
Enumeración constructiva de gráficos : obtención de una lista completa de gráficos en una clase determinada.
Un componente conexo de un gráfico es un subconjunto de los vértices del gráfico , para dos vértices cualesquiera de los cuales hay un camino de uno al otro, y no hay camino desde el vértice de este subconjunto a un vértice que no sea de este subconjunto .
Un componente fuertemente conectado de un gráfico , una capa es el conjunto máximo de vértices de un gráfico dirigido , de modo que para dos vértices cualesquiera de este conjunto hay un camino tanto del primero al segundo como del segundo al primero.
Un contorno es un camino cerrado en un dígrafo .
La raíz del árbol es el nodo seleccionado del árbol ; en un dígrafo , un vértice con un grado de entrada cero.
Un cociclo es un corte mínimo , un conjunto mínimo de bordes, cuya eliminación hace que el gráfico se desconecte.
Las aristas múltiples son aristas múltiples que inciden en el mismo par de vértices. Encontrado en multigrafos .
Un grafo cúbico es un grafo regular de grado 3, es decir, un grafo en el que exactamente tres aristas inciden en cada vértice.
un grafo k-partido es un grafo G cuyo número cromático c(G)=k
Un grafo k-conexo es un grafo conexo en el que no hay un conjuntode vértices o menosmodo que al eliminar todos los vértices y aristas incidentes serompe la conexión del grafo. En particular, un grafo conexo es 1-conexo, y un grafo doblemente conexo es 2-conexo. $V'$ $k-1$ $V'$

L

Un grafo de Laman con n vértices es un grafo G tal que, en primer lugar, para cada k , cualquier subgrafo de G que contenga k vértices tiene como máximo 2 k − 3 aristas y, en segundo lugar, el grafo G tiene exactamente 2 n −3 aristas.

El bosque es un grafo no dirigido sin ciclos. Los árboles son los componentes de conectividad de un bosque .
Una hoja de árbol es un vértice de árbol con un solo borde o arco entrante .
El grado local de un vértice es el número de aristas que le inciden. El bucle contribuye "2" al grado del vértice.

m

Maxi-code es un gráfico invariante completo difícil de calcular que se obtiene al escribir los valores binarios de la matriz de adyacencia en una línea, seguido de la conversión del número binario resultante a la forma decimal. El código maxi corresponde a tal orden de filas y columnas, en el que el valor resultante es el máximo posible. $\mu _{max}$
La coincidencia máxima en el gráfico. Un emparejamiento se llama máximo si cualquier otro emparejamiento tiene menos aristas.
Una ruta en un gráfico es una secuencia alterna de vértices y aristas en la que inciden dos elementos adyacentes cualesquiera . Si , entonces la ruta está cerrada , de lo contrario está abierta . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
La matriz de accesibilidad de un dígrafo es una matriz que contiene información sobre la existencia de caminos entre los vértices de un dígrafo.
La matriz de incidencia de un grafo es una matriz cuyos valores de los elementos se caracterizan por la incidencia de los vértices correspondientes del grafo (verticalmente) y sus aristas (horizontalmente). Para un grafo no dirigido, un elemento toma el valor 1 si su vértice y su arista correspondientes son incidentes. Para un grafo dirigido, el elemento toma el valor 1 si el vértice incidente es el comienzo de una arista, el valor -1 si el vértice incidente es el final de una arista; en otros casos (incluidos los bucles for ), el valor del elemento se asigna a 0 .
La matriz de adyacencia de un grafo es una matriz cuyos valores de los elementos se caracterizan por la adyacencia de los vértices del grafo. En este caso, al valor del elemento de la matriz se le asigna el número de aristas que conectan los vértices correspondientes (es decir, que son incidentes a ambos vértices).
El minicódigo es un gráfico invariante completo difícil de calcular que se obtiene escribiendo los valores binarios de la matriz de adyacencia en una línea y luego convirtiendo el número binario resultante a la forma decimal. El minicódigo corresponde a tal orden de filas y columnas, en el que el valor resultante es el más pequeño posible. $\mu _{min}$
El marco mínimo (o marco de peso mínimo , árbol de expansión mínimo ) de un gráfico es un conjunto acíclico (sin ciclos) de aristas en un gráfico conectado, ponderado y no dirigido que conecta todos los vértices de este gráfico, mientras que la suma de los pesos de todos Los bordes en él son mínimos.
El conjunto de adyacencia de un vértice v es el conjunto de vértices adyacentes al vértice v . designado _ $\Gamma ^{+}(v)$
Un grafo menor es un grafo que se puede obtener del grafo original quitando y contrayendo arcos.
Un puente es una arista cuya eliminación aumenta el número de componentes conectados en el gráfico.
Un multigrafo es un grafo en el que puede haber un par de vértices que están conectados por más de un borde (no dirigido), o más de dos arcos de direcciones opuestas.

H

Un grafo dirigido es un grafo dirigido en el que dos vértices están conectados por un arco como máximo.
- Un gráfico acíclico dirigido es un gráfico dirigido sin contornos .
Un conjunto de vértices independientes (también conocido como conjunto internamente estable ) es un conjunto de vértices de un gráfico G en el que dos vértices no son adyacentes (ningún par de vértices está conectado por una arista).
- Un conjunto independiente se llama máximo cuando no hay otro conjunto independiente en el que estaría incluido. El complemento del conjunto independiente más grande se llama cobertura mínima de vértices del gráfico.
- El mayor conjunto independiente es el mayor conjunto independiente.
Los vértices independientes son vértices no adyacentes por pares del gráfico. [una]
Un gráfico inseparable es un gráfico conectado, no vacío y sin puntos de articulación. [2] .
Un grafo normado es un grafo dirigido sin ciclos .

Un gráfico nulo ( un gráfico vacío ) es un gráfico sin vértices .

Ah

La circunferencia es la longitud del ciclo más pequeño en el gráfico.
La unión de gráficos (gráficos etiquetadosy) es un gráficocuyo conjuntode vértices es y el conjunto de aristas es. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\taza G_{2}$ $X_{1}\taza X_{2}$ $U=U_{1}\taza U_{2}$
Una vecindad de orden k es un conjunto de vértices a una distancia k de un vértice v dado ; a veces interpretado ampliamente como un conjunto de vértices separados de v a una distancia no mayor que k .
El entorno es un conjunto de vértices adyacentes al dado.
Un dígrafo , un grafo dirigido G = (V,E) es un par de conjuntos, donde V es un conjunto de vértices (nodos), E es un conjunto de arcos (aristas dirigidas). Un arco es un par ordenado de vértices (v, w), donde el vértice v se llama el principio y el w es el final del arco. Podemos decir que el arco v → w conduce del vértice v al vértice w, mientras que el vértice w es adyacente al vértice v.
Un árbol de expansión ( esqueleto ) de un grafo conexo (no dirigido) es cualquier grafo parcial que sea un árbol . $G=(V,E)$ $S=(V,T)$
Un subgrafo de expansión es un subgrafo que contiene todos los vértices.

P

Una coincidencia es un conjunto de aristas no adyacentes por pares.
Un bucle es una arista cuyo principio y final están en el mismo vértice.
La intersección de gráficas (etiquetadas gráficasy) es una gráficacuyo conjuntode vértices es y el conjunto de aristas es. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cap G_{2}$ $X_{1}\cap X_{2}$ $U=U_{1}\cap U_{2}$
Enumeración de gráficos : contar el número de gráficos no isomorfos en una clase dada (con características dadas).
Un vértice periférico es un vértice cuya excentricidad es igual al diámetro del gráfico.
Un gráfico plano es un gráfico que se puede dibujar ( apilar ) en un plano sin cruzar los bordes. Es isomorfo a un grafo plano, es decir, es un grafo con intersecciones, pero que permite su tendido plano, por lo que puede diferir de un grafo plano por una imagen en un plano. Por lo tanto, puede haber una diferencia entre un gráfico plano y un gráfico plano cuando se representa en un plano.
Un grafo plano es un grafo geométrico en el que dos aristas no tienen puntos comunes, excepto el vértice incidente en ambas (no se cortan). Es un gráfico apilado en el plano.
Un subgrafo del grafo original es un grafo que contiene cierto subconjunto de vértices del grafo dado y cierto subconjunto de aristas incidentes a ellos. (cf. sugraph .) Con respecto a un subgrafo, el grafo original se llama supergrafo
Un grafo completo es un grafo en el que por cada par de vérticeshay una arista, incidentee incidente(cada vértice está conectado por una arista a cualquier otro vértice). $v_{1},v_{2}$ $v_{1}$ $v_{2}$
Una invariante completa de un grafo es una característica numérica de un grafo o de su vector ordenado, cuyos valores son necesarios y suficientes para establecer el isomorfismo del grafo
Un grafo bipartito completo es un grafo bipartito en el que cada vértice de un subconjunto está conectado por una arista a cada vértice de otro subconjunto
El grado de entrada en el dígrafo de un vértice es el número de arcos que entran en el vértice. Denotado por , , o . $v$ $d^{+}(v)$ $\mathrm {grados} ^{+}(v)$ $\mathrm {grado} (v)$ $d_{t}(v)$
El grado de salida en el dígrafo de un vértice es el número de arcos que salen del vértice. Denotado por , , o . $v$ $d^{-}(v)$ $\mathrm {grado} ^{-}(v)$ $\mathrm {fuera de grado} (v)$ $d_{o}(v)$
Un gráfico etiquetado es un gráfico a cuyos vértices o arcos se les asigna algún tipo de etiqueta, por ejemplo, números naturales o símbolos de algún alfabeto.
Un subgrafo generado es un subgrafo generado por un conjunto de aristas en el grafo original. No necesariamente contiene todos los vértices del gráfico, pero estos vértices están conectados por los mismos bordes que en el gráfico.
El orden del gráfico es el número de vértices del gráfico. [3]
Una coloración de gráfico adecuada es una coloración tal que cada clase de color es un conjunto independiente. En otras palabras, en una coloración adecuada, dos vértices adyacentes cualesquiera deben tener colores diferentes.
Un producto de gráficos : para gráficos dados , un producto es un gráfico cuyos vértices son el producto cartesiano de los conjuntos de vértices de los gráficos originales. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\veces V_{2}$
Un camino simple es un camino en el que todos los vértices son distintos.
Un gráfico simple es un gráfico que no tiene múltiples aristas o bucles .
Un camino simple es un camino cuyos vértices son distintos por pares [4] . En otras palabras, un camino simple no pasa dos veces por el mismo vértice.
- Un ciclo simple es un ciclo que no pasa dos veces por el mismo vértice.
Un seudógrafo es un gráfico que puede contener bucles y/o múltiples aristas.

Un gráfico vacío ( gráfico nulo ) es un gráfico sin bordes .
Una ruta es una secuencia de aristas (en un gráfico no dirigido) y/o arcos (en un gráfico dirigido), de modo que el final de un arco (arista) es el comienzo de otro arco (arista). O una secuencia de vértices y arcos (aristas), en la que cada elemento es incidente con el anterior y el siguiente [4] . Se puede considerar como un caso especial de una ruta .
Un camino en un dígrafo es una secuencia de vértices v 1 , v 2 , …, v n , para los cuales hay arcos v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Se dice que este camino comienza en el vértice v 1 , pasa por los vértices v 2 , v 3 , …, v n-1 y termina en el vértice v n .

R

El radio del grafo es el mínimo de las excentricidades de los vértices de un grafo conexo; el pico en el que se alcanza este mínimo se llama pico central.
Dividir un gráfico es una representación del gráfico original como un conjunto de subconjuntos de vértices según ciertas reglas.
El vértice dividido es el mismo que el de la bisagra y el punto de articulación .
El desarrollo de un grafo es una función definida en los vértices de un grafo dirigido.
Un gráfico etiquetado es un gráfico para el que se dan un conjunto de etiquetas S, una función de etiquetado de vértice f : A → S y una función de etiquetado de arco g : R → S. Gráficamente, estas funciones se representan mediante etiquetas en vértices y arcos. El conjunto de etiquetas se puede dividir en dos subconjuntos no superpuestos de etiquetas de vértice y etiquetas de arco.
Un corte es un conjunto de aristas , cuya eliminación hace que el gráfico se desconecte .
Un gráfico de marco es un gráfico que se puede dibujar en un plano de tal manera que cualquier cara acotada es un cuadrilátero y cualquier vértice con tres o menos vecinos es incidente en una cara no acotada. [5]
La coloración de gráficos es la división de los vértices en conjuntos (llamados colores). Si, además, no hay dos vértices adyacentes que pertenezcan al mismo conjunto (es decir, dos vértices adyacentes siempre son de diferentes colores), tal coloración se llama regular.
La distancia entre los vértices es la longitud de la cadena más corta (en el dígrafo de ruta) que conecta los vértices dados. Si tal cadena (camino) no existe, se supone que la distancia es igual al infinito.
Una cubierta de aristas es un conjunto de aristas de gráfico de modo que cada vértice incide en al menos una arista de este conjunto.
El gráfico lineal de un gráfico no dirigido es un gráfico que representa la vecindad de los bordes del gráfico.
Edge es un concepto básico. Una arista conecta dos vértices de un gráfico.
Un grafo regular es un grafo cuyos grados de todos los vértices son iguales. El grado de regularidad es ungráfico invariante y se denota por . Indefinido para grafos irregulares. Los gráficos regulares presentan un desafío particular para muchos algoritmos. $r(G)$ $r(G)$
- Un gráfico regular de grado 0 ( gráfico completamente desconectado , gráfico vacío , gráfico nulo ) es un gráfico sin bordes .

C

Un gráfico autodual es un gráfico que es isomorfo a su gráfico dual .
Un árbol hiperdelgado (en forma de estrella) es un árbol que tiene un solo vértice de grado mayor que 2.
Conectividad . Dos vértices en un gráfico están conectados si hay un camino (simple) que los conecta .
Un grafo conexo es un grafo en el que todos los vértices están conectados.
Una sección de un grafo es un conjunto de aristas cuya eliminación divide el grafo en dos subgrafos aislados, uno de los cuales, en particular, puede ser un grafo trivial.
Una red es, en principio, lo mismo que un grafo , aunque a las redes se les suele llamar grafos cuyos vértices están etiquetados de una forma determinada.
- Una red dirigida es un gráfico dirigido que no contiene contornos.
Fuerte conectividad . Dos vértices en un grafo dirigido están fuertemente conectados si existe un camino del primero al segundo y del segundo al primero.
- Un dígrafo fuertemente conectado es un dígrafo en el que todos los vértices están fuertemente conectados.
Adyacencia - un concepto utilizado en relación con sólo dos aristas o sólo dos vértices : Dos aristas incidentes a un vértice se llaman adyacentes ; dos vértices incidentes en la misma arista también se llaman adyacentes . (cf. Incidente .)
Un grafo mixto es un grafo que contiene aristas dirigidas y no dirigidas .
Un emparejamiento perfecto es un emparejamiento que contiene todos los vértices del gráfico.
La conexión de dos grafos y , que no tienen vértices comunes, se llama grafo . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\taza V_{2},E_{1}\taza E_{2}\taza V_{1}\veces V_{2}\taza V_{2} \veces V_{1})$

Se puede ver a partir de la definición que la conexión de grafos tiene las propiedades de conmutatividad y asociatividad.

El espectro de un grafo es el conjunto de todos los valores propios de la matriz de adyacencia, teniendo en cuenta múltiples aristas.
El grado del vértice es el número de aristas del grafo G que inciden en el vértice x . designado_ El grado mínimo de un vértice de un grafo G se denota por. y el máximo es. $d(x)$ $\ delta (G)$ $\Delta (G)$
Contracción del borde del gráfico : reemplazo de los extremos del borde con un vértice, los vecinos de estos extremos se convierten en vecinos del nuevo vértice. El gráfico es contraíble si elsegundo puede obtenerse del primero mediante una secuencia de contracciones de aristas. $G_{1}$ $G_{2}$
Un subgrafo ( grafo parcial ) del grafo original es un grafo que contiene todos los vértices del grafo original y un subconjunto de sus aristas . (cf. subgrafo .)
Supergraph : cualquier gráfico que contenga el gráfico original (es decir, para el cual el gráfico original es un subgrafo )

T

Theta-graph es un grafo que consiste en la unión de tres caminos que no tienen vértices comunes en su interior, y tienen los mismos vértices finales [7]
El gráfico theta de un conjunto de puntos en el plano euclidiano se construye como un sistema de conos que rodean cada vértice con una arista por cada cono añadida al punto del conjunto cuya proyección sobre el eje central del cono es mínima.

Un grafo de identidad es un grafo para el que sólo es posible un automorfismo : el grafo de identidad . Hablando en sentido figurado, el gráfico de identidad es un gráfico "absolutamente no simétrico".
El punto de articulación es el mismo que el de la bisagra y el vértice divisorio .
Triangulación de superficie : colocar un gráfico en una superficie , dividirlo en regiones triangulares; un caso especial de triangulación topológica .
Un grafo trivial es un grafo que tiene como máximo un vértice .
Un torneo es un gráfico dirigido en el que cada par de vértices está conectado por una sola arista.

Wu

Un nodo es lo mismo que un vértice .
Apilamiento o incrustación de gráficos : un gráfico se apila en alguna superficie si se puede dibujar en esta superficie de modo que los bordes del gráfico no se crucen. (Consulte Gráfica plana , Gráfica plana .)
Un refugio es un cierto tipo de función en los conjuntos de vértices de un gráfico no dirigido. Si existe cobertura, el fugitivo puede usarla para ganar el juego de persecución y evasión en el gráfico usando esta función en cada paso del juego para determinar conjuntos seguros de vértices a los que ir.
Un grafo ordenado es un grafo en el que las aristas que salen de cada vértice están numeradas de manera única, comenzando desde 1. Se considera que las aristas están ordenadas en orden ascendente de números. En la representación gráfica, a menudo se considera que los bordes están ordenados en el orden de algún recorrido estándar (por ejemplo, en el sentido contrario a las agujas del reloj ).

F

El factor n de un gráfico es un subgráfico de expansión regular de grado . $norte$
n-factorización de un gráfico: división de un gráfico en n-factores independientes .

x

El número cromático de un gráfico es el número mínimo de colores necesarios para colorear los vértices de un gráfico de modo que los vértices conectados por un borde se coloreen de diferentes colores.
El polinomio característico de un grafo es el polinomio característico de su matriz de adyacencia .

C

El centro de la gráfica es el conjunto de vértices, para los cuales se cumple la igualdad:, donde es la excentricidad del vértice , y es el radio de la gráfica. $W=\izquierda\{u_{1},u_{2},...,u_{n}\derecha\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
Una cadena en un gráfico es una ruta , todos cuyos bordes son distintos. Si todos los vértices (y por lo tanto los bordes) son diferentes, entonces dicha cadena se llama simple ( elemental ). En una cadena, los vértices y se denominan extremos de la cadena. Una cadena con extremos u y v conecta vértices u y v . La cadena que conecta los vértices u y v se denota por . Para los dígrafos, una cadena se llama cadena or. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ En algunas fuentes , una cadena simple es una cadena cuyos bordes son distintos, que es una condición más débil.
El ciclo es un circuito cerrado . Para los dígrafos, un ciclo se llama contorno .
- Un ciclo ( ciclo simple ) en un dígrafo es un camino simple de longitud al menos 1 que comienza y termina en el mismo vértice.
- El ciclo de Hamilton es el mismo que el ciclo de Hamilton .
El número ciclomático de un gráfico es el número mínimo de aristas que deben eliminarse para que el gráfico sea acíclico . Para un gráfico conexo, existe una relación:donde es el número ciclomático, es el número de componentes conexas del gráfico, es el número de aristas y es el número de vértices . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

Un grafo parcial es lo mismo que un sugrafo .
Un gráfico par es lo mismo que un gráfico bipartito .
Número de cobertura de vértice : el tamaño de la cobertura de vértice más pequeña del gráfico.
El número de independencia es el tamaño del conjunto independiente más grande de vértices en el gráfico.
El número coincidente es el tamaño de la coincidencia más grande en el gráfico.
Número de cubierta de borde : el tamaño de la cubierta de borde más pequeña del gráfico.

W

Una bisagra es un vértice de un grafo , como resultado de lo cual, junto con todas las aristas que le inciden , elnúmero de componentes conectados en el grafo aumenta como resultado de su remoción.
Un engranaje (denotado por ) es un gráfico obtenido de una rueda colocando vértices adicionales entre cada par de vértices adyacentes del perímetro . Los engranajes pertenecen a la familia de los gráficos de cuadros y juegan un papel importante en la descripción de los subgráficos prohibidos de los gráficos de cuadros [8] $G_{n}$

E

Un grafo de Euler es un grafo en el que hay un ciclo que contiene todas las aristas del grafo una vez (los vértices se pueden repetir).
Cadena de Euler (o ciclo de Euler ) - una cadena ( ciclo ) que contiene todos los bordes del gráfico (los vértices se pueden repetir).
La excentricidad de un vértice es el máximo de todas las distancias mínimas de otros vértices a un vértice dado.
Un camino elemental es un camino cuyos vértices, con la posible excepción del primero y el último, son diferentes. En otras palabras, un camino simple no pasa dos veces por el mismo vértice, sino que puede comenzar y terminar en el mismo vértice, en cuyo caso se denomina ciclo (ciclo elemental).
El siguiente procedimiento se denomina contracción elemental : tomamos una arista (junto con los vértices que le inciden , por ejemplo, u y v) y la “contraemos”, es decir, quitamos la arista e identificamos los vértices u y v. El vértice obtenido de esta manera es incidente con aquellas aristas (que no sean) con las que u o v eran originalmente incidentes.

Enlaces

↑ Distel R. Teoría de grafos Per. De inglés. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - P. 17.
↑ Harari F. Teoría de grafos. - M.: Mir, 1972. - S. 41.
↑ Distel R. Teoría de grafos Per. De inglés. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - P. 16.
↑ 1 2 Kuznetsov O. P., Adelson-Velsky G. M. / Matemáticas discretas para un ingeniero. / M .: Energía, 1980-344 p., il. Página 120-122
↑ AV Karzanov. Extensiones de métricas finitas y el problema de colocación de equipos // Actas de la ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ MB Abrosimov. En el vértice mínimo 1-extensiones de conexiones de gráficos de una forma especial. // Teoría de Grafos Aplicada.- 2011.- Edición. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43–54. — (Apuntes de clase en Matemáticas). -doi : 10.1007/ BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatoria y geometría de gráficos cuadrados finitos e infinitos // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , núm. 4 . - S. 1399-1440 . -doi : 10.1137/ 090760301 . -arXiv : 0905.4537 . _ .

Literatura

Distel R. Teoría de grafos Per. De inglés. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - 336 p.
Harari F. Teoría de grafos. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .