Glosario de teoría de grafos

El presente artículo contiene un glosario de la teoría de grafos, disciplina que consiste en el estudio de los grafos, los sistemas de nodos o vértices conectados en pares por líneas o aristas.

Índice

Símbolos


Corchetes [ ]: $G [S]$ es el subgrafo inducido de un grafo $G$ para el subconjunto de vértices $S$ .

Símbolo prima ': El símbolo prima (') se utiliza a menudo para modificar la notación de invariantes de grafos, de modo que se aplique al grafo lineal en lugar de al grafo dado. Por ejemplo, $α (G)$ es el número de independencia de un grafo; $α'(G)$ es el número coincidente del grafo, que equivale al número de independencia de su grafo lineal. De forma similar, $χ (G)$ es el número cromático de un grafo; $χ'(G)$ es el índice cromático del grafo, que equivale al número cromático de su grafo lineal.

Remove ads

A


abierto: 1. Véase entorno.; 2. Véase paseo.

absorbente: Un conjunto absorbente $A$ de un grafo dirigido $G$ es un conjunto de vértices tales que para cualquier vértice $v\in G\setminus A$ , existe una arista desde $v$ hacia un vértice de $A$ .

accesibilidad: La capacidad de ir de un vértice a otro dentro de un grafo.

accesible: Cuando un par de vértices poseen una accesibilidad afirmativa. Se dice que un vértice $y$ es accesible desde un vértice $x$ si existe una ruta desde $x$ a $y$ .

acíclico: 1. Un grafo es acíclico si no tiene ciclos. Un grafo acíclico no dirigido es lo mismo que un bosque. Un grafo dirigido acíclico, que es un dígrafo sin ciclos dirigidos, suele denominarse grafo acíclico dirigido, especialmente en informática.^[1]; 2. Un coloreado acíclico de un grafo no dirigido es una coloración propia en la que cada dos clases de color inducen un bosque.^[2]

acromático: El número acromático de un grafo es el número máximo de colores en una coloración completa.^[3]

adyacencia: 1. La relación entre dos vértices que son ambos extremos de la misma arista.^[1]; 2. La relación entre dos aristas distintas que comparten un vértice final.^[4]

adyacencia múltiple: Una adyacencia múltiple o arista múltiple es un conjunto de más de una arista que tienen todas los mismos extremos (en la misma dirección, en el caso de grafos dirigidos). Un grafo con múltiples aristas se suele denominar multigrafo.

agujero: Un agujero es un ciclo inducido de longitud cuatro o más. Un agujero impar es un agujero de longitud impar. Un antiagujero es un subgrafo inducido de orden cuatro cuyo complemento es un ciclo; equivalentemente, es un agujero en el grafo complemento. Esta terminología se utiliza principalmente en el contexto de grafos perfectos, que se caracterizan por los teorema del grafo perfecto fuerte como grafos sin agujeros impares ni antiagujeros impares. Los grafos sin agujeros son iguales a los grafos cordales.

aislado: Un vértice aislado de un grafo es un vértice cuyo grado es cero, es decir, un vértice sin aristas incidentes.^[1]

α (letra alfa): Para un grafo $G$ , $α (G)$ (usando la letra griega alfa) es su número de independencia (véase independiente), y $α'(G)$ es su número correspondiente (véase coincidencia).

alterno: En un grafo con coincidencia, una ruta alterna es una ruta cuyas aristas alternan entre aristas coincidentes y no coincidentes. Un ciclo alternado es, de forma similar, un ciclo cuyas aristas alternan entre aristas coincidentes y no coincidentes. Una trayectoria de aumento es una ruta alterna que comienza y termina en vértices no saturados. Una coincidencia mayor se puede encontrar como la diferencia simétrica de la ruta coincidente y la ruta de aumento; una coincidencia es máxima si y solo si no tiene ruta de aumento.

altura: 1. La "altura" de un nodo en un árbol con raíz es el número de aristas en un camino más largo, que se aleja de la raíz (es decir, sus nodos tienen una profundidad estrictamente creciente), que comienza en ese nodo y termina en una hoja.; 2. La "altura" de un árbol con raíz es la altura de su raíz. Es decir, la "altura" de un árbol es el número de aristas en el camino más largo posible, que se aleja de la raíz, que comienza en la raíz y termina en una hoja.; 3. La "altura" de un grafo acíclico dirigido es la longitud máxima de un camino dirigido en este grafo.

ancho: 1. Un sinónimo de degeneración.; 2. Para otros invariantes de grafos conocidos como ancho, véanse ancho de banda, ancho de rama, ancho de clique, ancho de ruta y ancho de árbol.; 3. El ancho de una descomposición de árbol o de ruta es uno menos que el tamaño máximo de una de sus bolsas y puede utilizarse para definir el ancho del árbol y el ancho de la ruta.; 4. El ancho de un grafo acíclico dirigido es la cardinalidad máxima de una anticadena.

ancho de árbol: El ancho de árbol de un grafo $G$ es el ancho mínimo de una descomposición de árbol de $G$ . También se puede definir en términos del número de clique de una completación cordal de $G$ , el orden de un refugio de $G$ o el orden de una zarza de $G$ .

ancho de banda: El ancho de banda de un grafo $G$ es el mínimo, para todos los ordenamientos de vértices de $G$ , de la longitud de la arista más larga (el número de pasos en el ordenamiento entre sus dos extremos). También es uno menos que el tamaño del grupo máximo en una completitud de intervalo adecuada de $G$ , elegida para minimizar el tamaño del grupo.

ancho de clique: El ancho de clique de un grafo $G$ es el número mínimo de etiquetas distintas necesarias para construir $G$ mediante operaciones que crean un vértice etiquetado, forman la unión disjunta de dos grafos etiquetados, añaden una arista que conecta todos los pares de vértices con etiquetas dadas o reetiquetan todos los vértices con una etiqueta dada. Los grafos con un ancho de clique de como máximo $2$ son exactamente los cografos.

ancho de rama: Véase descomposición de ramas.

ancho de ruta: El ancho de ruta de un grafo $G$ es el ancho mínimo de la descomposición de la ruta de $G$ . También puede definirse en términos del número de clique de una compleción de intervalo de $G$ . Siempre se encuentra entre el ancho de banda y el ancho de árbol de $G$ . También se conoce como grosor de intervalo, número de separación de vértices o número de búsqueda de nodos.

ancho de tallado: El ancho de tallado es una noción de ancho de grafo análoga al ancho de rama, pero que utiliza agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de aristas.

antiarista: Una antiarista o no arista está formada por un par de vértices no adyacentes; son las aristas del grafo complementario.

anticadena: En un grafo acíclico dirigido, un subconjunto $S$ de vértices incomparables entre sí; es decir, para cualquier $x\leq y$ en $S$ , no existe una ruta dirigida de $x$ a $y$ ni de $y$ a $x$ . Inspirado en la noción de anticadena en conjuntos parcialmente ordenados.

antitriángulo: Un conjunto independiente de tres vértices, complemento de un triángulo.

ápice: 1. Un grafo de ápice es un grafo en el que se puede eliminar un vértice, dejando un subgrafo planar. El vértice eliminado se denomina ápice. Un grafo $k$ -ápical es un grafo que se puede convertir en plano eliminando $k$ vértices.; 2. Sinónimo de vértice universal, un vértice adyacente a todos los demás vértices.

árbol clique: Sinónimo de grafo bloque.

árbol: 1. Un árbol es un grafo no dirigido conexo y acíclico, o un grafo dirigido en el que existe un único camino desde un vértice (la raíz del árbol) a todos los vértices restantes.; 2. Un $k$ -árbol es un grafo formado mediante la unión de $(k + 1)$ -cliques con $k$ -cliques compartidos. Un árbol, en sentido común, es un $1$ -árbol según esta definición.

arborescencia: Sinónimo de árbol enraizado y dirigido; véase árbol.

arco dirigido: Véase flecha.

arco: Véase arco.

arista dirigida: Véase flecha.

arista libre: Una arista que no está en un apareamiento.

arista: Una arista es (junto con los vértices) una de las dos unidades básicas a partir de las cuales se construyen los grafos. Cada arista tiene dos vértices (o, en hipergrafos, más) a los que está unida, llamados sus extremos. Las aristas pueden ser dirigidas o no dirigidas; las no dirigidas también se denominan líneas y las dirigidas, arcos o flechas. En un grafo no dirigido, una arista puede representarse como el conjunto de sus vértices, y en un grafo simple dirigido puede representarse como un par ordenado de sus vértices. Una arista que conecta los vértices $x$ y $y$ a veces se escribe $xy$ .

aumentado: Un tipo especial de trayectoria alterna; véase alterno.

automorfismo: Un automorfismo de grafo es una simetría de un grafo, un isomorfismo de un grafo sobre sí mismo.

Remove ads

B


baraja: El multiconjunto de grafos formado a partir de un único grafo $G$ eliminando un único vértice de todas las maneras posibles, especialmente en el contexto de la conjetura de reconstrucción. Una baraja de aristas se forma de la misma manera eliminando una única arista de todas las maneras posibles. Los grafos de una baraja también se denominan "cartas". Véase también crítico (grafos que tienen una propiedad que no se cumple en ninguna carta) e hipo- (grafos que no tienen una propiedad que se cumple en todas las cartas).

biclique: Sinónimo de grafo bipartito completo o subgrafo bipartito completo; véase completo.

biconexo: Generalmente sinónimo de $2$ -vértices conectados, pero a veces incluye K₂ aunque no sea 2-conexo. Véase conexo; para un componente biconexo, véase componente.

bien coloreado: Un grafo bien coloreado es un grafo cuya coloración codiciosa usa el mismo número de colores.

bien cubierto: Un grafo bien cubierto es un grafo cuyos conjuntos independientes máximos tienen el mismo tamaño.

bipartito: Un grafo bipartito es un grafo cuyos vértices pueden dividirse en dos conjuntos disjuntos, de modo que los vértices de un conjunto no están conexos entre sí, pero sí pueden estarlo con los del otro. Dicho de otro modo, un grafo bipartito es un grafo sin ciclos impares; equivalentemente, es un grafo que puede colorearse correctamente con dos colores. Los grafos bipartitos suelen escribirse como $G = (U, V, E)$ , donde $U$ y $V$ son los subconjuntos de vértices de cada color. Sin embargo, a menos que el grafo sea conexo, puede no tener una coloración bicolor única.

birregular: Un grafo birregular es un grafo bipartito en el que sólo hay dos grados de vértices diferentes, uno para cada conjunto de la bipartición de vértices.

bloque: 1. Un bloque de un grafo $G$ es un subgrafo maximal que puede ser un vértice aislado, una arista puente o un subgrafo biconexo. Si un bloque es biconexo, cada par de vértices que lo componen pertenece a un ciclo común. Cada arista de un grafo pertenece a exactamente un bloque.; 2. El grafo de bloques de un grafo $G$ es otro grafo cuyos vértices son los bloques de $G$ , con una arista que conecta dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es el grafo de intersección de los bloques de $G$ . El grafo de bloques de cualquier grafo es un bosque.; 3. El grafo de corte por bloques (o de punto de corte por bloques) de un grafo $G$ es un grafo bipartito donde un conjunto de partes consiste en los vértices de corte de $G$ y el otro tiene un vértice $b_{i}$ por cada bloque $B_{i}$ de $G$ . Cuando $G$ es conexo, su grafo de punto de corte por bloques es un árbol.; 4. Un grafo bloque (también llamado árbol clique si es conexo, y a veces erróneamente llamado árbol de Husimi) es un grafo cuyos bloques son grafos completos. Un bosque es un grafo de bloques; por lo tanto, en particular, el grafo de bloques de cualquier grafo es un grafo de bloques, y cada grafo de bloques puede construirse como el grafo de bloques de un grafo.

bola: Una bola (también conocida como bola de entorno o bola de distancia) es el conjunto de todos los vértices que se encuentran a una distancia máxima r de un vértice. Más formalmente, para un vértice v y un radio r, la bola B(v,r) está compuesta por todos los vértices cuya distancia mínima a v es menor o igual a r.

bolsa: Uno de los conjuntos de vértices resultantes de la descomposición de un árbol.

bosque: Un bosque es un grafo no dirigido sin ciclos (una unión disjunta de árboles sin raíz), o un grafo dirigido formado como una unión disjunta de árboles con raíz.

bucle: Un bucle bucle, lazo o bucle propio es una arista cuyos extremos son el mismo vértice. Forma un ciclo de longitud $1$ . No están permitidos en grafos simples.

bucle propio: Sinónimo de lazo.

Remove ads

C


C: $C n$ es un grafo ciclo de $n$ vértices; véase ciclo

cactus: Un grafo cactus, cactus o árbol de Husimi es un grafo conexo en el que cada arista pertenece como máximo a un ciclo. Sus bloques son ciclos o aristas simples. Si, además, cada vértice pertenece como máximo a dos bloques, se denomina cactus de Navidad.

cadena: 1. Sinónimo de paseo.; 2. Al aplicar métodos de topología algebraica a grafos, un elemento de un complejo de cadenas, es decir, un conjunto de vértices o un conjunto de aristas.

camino: Un camino o recorrido es una sucesión finita o infinita de aristas que une una secuencia de vértices. Los recorridos también se denominan a veces «cadenas».^[5] Un recorrido es «abierto» si su primer y último vértice son distintos, y «cerrado» si se repiten.

camino dirigido: Una ruta en el que todas las "arista" tienen el mismo dirección. Si un camino dirigido va de vértice $x$ al vértice $y$ , $x$ es un predecesor de $y$ , $y$ es un sucesor de $x$ , y se dice que $y$ es accesible desde $x$ .

canonización: Una forma canónica de un grafo es un invariante tal que dos grafos tienen invariantes iguales si y solo si son isomorfos. Las formas canónicas también pueden denominarse invariantes canónicos o invariantes completos, y a veces se definen solo para los grafos dentro de una familia particular. La canonización de grafos es el proceso de calcular una forma canónica.

cara: En un grafo plano o grafo embebido, un componente conexo del subconjunto del plano o superficie de la incrustación que es disjunto del grafo. Para una incrustación en el plano, todas las caras menos una estarán acotadas; la única cara excepcional que se extiende hasta el infinito se denomina cara externa (o infinita).

carcaj: Un carcaj es un multigrafo dirigido, como se utiliza en teoría de categorías. Las aristas de un carcaj se denominan flechas.

carta: Un grafo formado a partir de un grafo dado eliminando un vértice, especialmente en el contexto de la conjetura de reconstrucción. Véase también cubierta, el multiconjunto de todas las cartas de un grafo.

centro: El centro de un grafo es el conjunto de vértices de excentricidad mínima.

centroide: Un centroide de un árbol es un vértice $v$ tal que si tiene su raíz en $v$ , ningún otro vértice tiene un tamaño de subárbol mayor que la mitad del tamaño del árbol.

cereza: Una cereza es un camino de tres vértices.^[6]

cerrado: 1. Un entorno cerrado es aquel que incluye su vértice central; véase entorno.; 2. Un paseo cerrado es aquel que comienza y termina en el mismo vértice; véase paseo.; 3. Un grafo es transitivamente cerrado si es igual a su propio cierre transitivo; véase transitivo.; 4. Una propiedad de grafo es cerrada bajo alguna operación sobre grafos si, siempre que el argumento o los argumentos de la operación la tienen, también la tiene el resultado. Por ejemplo, las propiedades hereditarias son cerradas bajo subgrafos inducidos; las propiedades monótonas son cerradas bajo subgrafos; y las propiedades menores cerradas son cerradas bajo menores.

χ: $χ (G)$ (usando la letra griega chi) es el número cromático de $G$ y $χ'(G)$ es su índice cromático; véase cromático y coloreado.

ciclo: 1. Un ciclo puede ser un tipo de grafo o un tipo de paseo. Como un paseo puede ser un paseo cerrado (también llamado tour o más usualmente un paseo cerrado sin vértices repetidos y consecuentemente sin aristas repetidas (también llamado un ciclo simple). En este último caso usualmente se considera como un grafo, es decir, las elecciones del primer vértice y dirección usualmente se consideran sin importancia. Esto es, las permutaciones cíclicas y las inversiones del paseo producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen caminos hamiltonianos, caminos inducidos, ciclos periféricos, y el ciclo más corto, que define la cintura de un grafo. Un $k$ -ciclo es un ciclo de longitud $k$ ; por ejemplo un $2$ -ciclo es un dígono y un $3$ -ciclo es un triángulo. Un grafo ciclo es un grafo que es en sí mismo un ciclo simple; un grafo ciclo con $n$ vértices es comúnmente denotado como $C n$ .; 2. El espacio ciclo es un espacio vectorial generado por los ciclos simples en un grafo, a menudo sobre el campo de 2 elementos pero también sobre otros campos.

cierre: 1. Para el cierre transitivo de un grafo dirigido, véase transitivo.; 2. El cierre o clausura de un grafo dirigido es un conjunto de vértices sin aristas salientes hacia vértices externos a la clausura. Por ejemplo, un sumidero es una clausura de un solo vértice. El problema de la clausura consiste en encontrar una clausura con peso mínimo o máximo.

cintura: La cintura o circunferencia de un grafo es la longitud de su ciclo simple más largo. El grafo es hamiltoniano si y solo si su circunferencia es igual a su orden.

circuito: Un circuito puede referirse a una trayectoria cerrada o a un elemento del espacio cíclico (un subgrafo euleriano generador). El rango de un circuito de un grafo es la dimensión de su espacio de ciclos.

círculo: Un grafo circular es el grafo de intersección de las cuerdas de un círculo.

circunferencia: El cintura de un grafo es la longitud de su ciclo más corto.

clase: 1. Una clase de grafos o familia de grafos es una colección (generalmente infinita) de grafos, a menudo definida como aquellos que poseen una propiedad específica. Se usa el término "clase" en lugar de "conjunto" porque, a menos que se establezcan restricciones especiales (como restringir los vértices que se dibujan a partir de un conjunto particular y definir las aristas como conjuntos de dos vértices), las clases de grafos no suelen ser conjuntos cuando se formalizan mediante la teoría de conjuntos.; 2. Una clase de color de un grafo coloreado es el conjunto de vértices o aristas que tienen un color particular.; 3. En el contexto del teorema de Vizing, al colorear las aristas de grafos simples, se dice que un grafo es de clase uno si su índice cromático es igual a su grado máximo, y de clase dos si su índice cromático es igual a uno más el grado. Según el teorema de Vizing, todos los grafos simples son de clase uno o de clase dos.

clique: Un clique es un conjunto de vértices mutuamente adyacentes (o el subgrafo completo inducido por dicho conjunto). En ocasiones, un clique se define como un conjunto maximal de vértices mutuamente adyacentes (o un subgrafo completo maximal), que no forma parte de ningún conjunto (o subgrafo) mayor. Un $k$ -clique es un clique de orden $k$ . El clique $ω (G)$ de un grafo $G$ es el orden de su clique más grande. El grafo clique de un grafo G es el grafo de intersección de los cliques maximales en G. Véase también biclique, un subgrafo bipartito completo.

co-: Este prefijo tiene varios significados que generalmente involucran a un grafo complemento. Por ejemplo, un cografo es un grafo generado mediante operaciones que incluyen complementación. Un cocoloreado es una coloración en la que cada vértice induce un conjunto independiente (como en la coloración propia) o una camarilla (como en la coloración del complemento).

coárbol: 1. El complemento de un árbol de expansión.; 2. Una estructura de árbol con raíces utilizada para describir un cografo, en el que cada vértice del cografo es una hoja del árbol, cada nodo interno del árbol está etiquetado con 0 o 1, y dos vértices del cografo son adyacentes si y solo si su ancestro común más bajo en el árbol está etiquetado como 1.

cobertura: Una cobertura de vértices es un conjunto de vértices incidentes a cada arista de un grafo. Una cobertura de aristas es un conjunto de aristas incidentes a cada vértice de un grafo. Un conjunto de subgrafos de un grafo cubre dicho grafo si su unión —tomada tanto por vértices como por aristas— es igual al grafo.

coincidencia: Una coincidencia es un conjunto de aristas en el que no hay dos que compartan un vértice. Un vértice está emparejado o saturado si es uno de los extremos de una arista en la coincidencia. Una coincidencia perfecta o emparejamiento completo es un emparejamiento que coincide con todos los vértices; también se puede llamar unifactorial y solo puede existir cuando el orden es par. Un emparejamiento casi perfecto, en un grafo de orden impar, es aquel que satura todos los vértices menos uno. Un coincidencia máxima es un emparejamiento que utiliza tantas aristas como sea posible. El número de emparejamiento $α'(G)$ de un grafo $G$ es el número de aristas en un emparejamiento máximo. Una coincidencia es un emparejamiento al que no se le pueden añadir aristas adicionales.

coloreado: 1. Una coloración de grafos es el etiquetado de los vértices de un grafo mediante elementos de un conjunto dado de colores, o equivalentemente, una partición de los vértices en subconjuntos, llamados "clases de color", cada una de las cuales está asociado a uno de los colores.; 2. Algunos autores usan "coloración", sin calificativo, para referirse a una coloración correcta, que asigna diferentes colores a los extremos de cada arista. En la coloración de grafos, el objetivo es encontrar una coloración correcta que utilice la menor cantidad de colores posible. Por ejemplo, los grafos bipartitos son aquellos que se pueden colorear con solo dos colores, y el teorema de los cuatro colores establece que cada grafo plano puede colorearse con un máximo de cuatro colores. Se dice que un grafo tiene $k$ colores si se ha coloreado correctamente con $k$ colores, y que es $k$ coloreable o $k$ cromático si esto es posible.; 3. Se han estudiado muchas variaciones de coloración, incluyendo el coloreado de aristas (colorear las aristas de forma que dos aristas con el mismo extremo no compartan un color), lista para colorear (colorear correctamente con cada vértice restringido a un subconjunto de los colores disponibles), coloreado acíclico (cada subgrafo de dos colores es acíclico), cocolorear (cada clase de color induce un conjunto independiente o una camarilla), coloreado completo (cada dos clases de color comparten una arista) y coloreado total (tanto las aristas como los vértices están coloreados).; 4. El número de coloración de un grafo es uno más la degeneración. Se denomina así porque la aplicación de un algoritmo de coloración voraz a una ordenación degenerativa del grafo utiliza como máximo esta cantidad de colores.

comparabilidad: Un grafo no dirigido es un grafo comparable si sus vértices son elementos de un conjunto parcialmente ordenado y dos vértices son adyacentes cuando son comparables en el orden parcial. De forma equivalente, un grafo de comparabilidad es un grafo con orientación transitiva. Muchas otras clases de grafos pueden definirse como grafos de comparabilidad de tipos especiales de orden parcial.

complemento: El grafo complemento ${\bar {G}}$ de un grafo simple $G$ es otro grafo en el mismo conjunto de vértices que $G$ , con una arista por cada dos vértices que no sean adyacentes en $G$ .

completo: 1. Un grafo completo es aquel en el que cada dos vértices son adyacentes: todas las aristas posibles están presentes. Un grafo completo con $n$ vértices suele denotarse como $K n$ . Un grafo bipartito completo es aquel en el que cada dos vértices en lados opuestos de la partición de vértices son adyacentes. Un grafo bipartito completo con $a$ vértices en un lado de la partición y $b$ vértices en el otro lado suele denotarse como $K a, b$ . La misma terminología y notación se ha extendido a los grafos multipartitos completos, grafos en los que los vértices se dividen en más de dos subconjuntos y cada par de vértices en diferentes subconjuntos son adyacentes. Si el número de vértices en los subconjuntos es $a, b, c, ...$ , este grafo se denota como $K a, b, c, ...$ .; 2. Una completitud de un grafo dado es un supergrafo que posee alguna propiedad deseada. Por ejemplo, una completación cordal es un supergrafo que es un grafo cordal.; 3. Una coincidencia completa es sinónimo de una coincidencia perfecta; véase coincidencia.; 4. Un coloreado completo es una coloración propia en la que cada par de colores se utiliza para los extremos de al menos una arista. Toda coloración con un número mínimo de colores es completa, pero pueden existir coloraciones completas con un mayor número de colores. El número acromático de un grafo es el número máximo de colores en una coloración completa.; 5. Un invariante completo de un grafo es sinónimo de una forma canónica, un invariante que tiene diferentes valores para grafos no isomorfos.

completo: Sinónimo de inducido.

componente: Un componente conectado de un grafo es un subgrafo conexo maximal. El término también se utiliza para subgrafos maximales o subconjuntos de vértices de un grafo con un orden superior de conectividad, incluyendo componente biconectado, componente triconectado y componente fuertemente conexo.

componente conectado: Sinónimo de componente.

condensación: La condensación de un grafo dirigido $G$ es un grafo acíclico dirigido con un vértice para cada componente fuertemente conectado de $G$ y una arista que conecta pares de componentes que contienen los dos puntos finales de al menos una arista en $G$ .

conectado: Un grafo conectado es aquel en el que cada par de vértices forma los extremos de un camino. Las formas superiores de conectividad incluyen la conectividad fuerte en grafos dirigidos (por cada dos vértices existen caminos de uno a otro en ambas direcciones), grafos conectados con $k$ vértices (eliminar menos de $k$ vértices no permite desconectar el grafo) y grafos conectados con $k$ aristas (eliminar menos de $k$ aristas no permite desconectar el grafo).

conectar: Causa de ser conectado.

conjunto de aristas: El conjunto de aristas de un grafo dado $G$ , a veces denotado como $E (G)$ .

conjunto de corte: Un corte es una partición de los vértices de un grafo en dos subconjuntos, o el conjunto (también conocido como conjunto de corte) de aristas que abarca dicha partición, si dicho conjunto no está vacío. Se dice que una arista abarca la partición si tiene extremos en ambos subconjuntos. Por lo tanto, la eliminación de un conjunto de corte de un grafo conexo lo desconecta.

conjunto de vértices: El conjunto de vértices de un grafo dado $G$ , a veces denotado por $V (G)$ .

conjunto separador: Un conjunto de vértices cuya eliminación genera un grafo desconectado. Un corte de un vértice se denomina punto de articulación o vértice de corte.

cono: Un grafo que contiene un vértice universal.

constante de Cheeger: Véase expansión.

contorno: 1. En un grafo embebido, un recorrido de contorno es el subgrafo que contiene todas las aristas y vértices incidentes de una cara.

contracción: La contracción de aristas es una operación elemental que elimina una arista de un grafo mientras fusiona los dos vértices que previamente unía. La contracción de vértices (a veces llamada identificación de vértices) es similar, pero los dos vértices no están necesariamente conectados por una arista. La contracción de trayectoria ocurre en el conjunto de aristas de una trayectoria que se contraen para formar una sola arista entre los extremos de la trayectoria. La operación inversa de la contracción de aristas es la división de vértices.

convertido: El grafo convertido es un sinónimo del grafo transpuesto; véase transpuesto.

cordal: 1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, por lo que ambos extremos pertenecen al ciclo.; 2. Un grafo cordal es un grafo en el que cada ciclo de cuatro o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son triángulos.; 3. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo de longitud seis o más tiene una cuerda impar.; 4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque). Es un grafo bipartito en el que cada ciclo de seis o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son 4-ciclos.; 5. Una cuerda de una circunferencia es un segmento de recta que conecta dos puntos de una circunferencia. El grafo de intersección de un conjunto de cuerdas se llama grafo circular.

corte

corte de arista: Un conjunto de aristas cuya eliminación desconecta el grafo. Un corte de una arista se denomina puente, istmo o arista de corte.

corte de vértice

corte mínimo: Un corte cuyo conjunto de corte tiene un peso total mínimo, posiblemente restringido a los cortes que separan un par de vértices designado; se caracterizan por teorema de flujo máximo y corte mínimo.

crítico: Un grafo crítico para una propiedad dada es aquel que posee dicha propiedad, pero que no posee ningún subgrafo formado al eliminar un solo vértice. Por ejemplo, un grafo de factor crítico posee una correspondencia perfecta (un factor 1) para cada eliminación de vértice, pero (debido a su número impar de vértices) no posee correspondencia perfecta. Compárese con "hipo-", usado para grafos que no poseen esa propiedad, pero sí la posee cada eliminación de un vértice.

cromático: Relativo a la coloración; véase color. La teoría de grafos cromáticos es la teoría de la coloración de grafos. El número cromático $χ (G)$ es el número mínimo de colores necesario para obtener una coloración correcta de $G$ . $χ'(G)$ es el índice cromático de $G$ , el número mínimo de colores necesario para una coloración correcta del coloreado de aristas de $G$ .

cuadrado: 1. El cuadrado de un grafo $G$ es la potencia de un grafo $G 2$ . En sentido opuesto, $G$ es la raíz cuadrada de $G 2$ . El medio cuadrado de un grafo bipartito es el subgrafo de su cuadrado inducido por un lado de la bipartición.; 2. Un grafo cuadrado es un grafo planar que se puede dibujar de forma que todas las caras acotadas sean 4-ciclos y todos los vértices de grado 3 pertenezcan a la cara exterior.; 3. Un grafo de cuadrícula es un grafo de celosía definido a partir de puntos en el plano con coordenadas enteras conectados por aristas de longitud unitaria.

cúbico: 1. Grafo hipercubo, el grafo de ocho vértices de los vértices y las aristas de un cubo.; 2. Grafo hipercubo, una generalización de mayor dimensión del grafo cúbico.; 3. Grafo de cubo plegado, formado a partir de un hipercubo mediante la adición de vértices opuestos que se conectan.; 4. Grafo cúbico reducido a la mitad, el medio cuadrado de un grafo hipercubico.; 5. Cubo parcial, un subgrafo de un hipercubo que preserva la distancia.; 6. El cubo de un grafo $G$ es la potencia de un grafo $G 3$ .; 7. Grafo cúbico, otro nombre para un grafo $3$ -regular, en el que cada vértice tiene tres aristas incidentes.; 8. Ciclos conexos en cubos, un grafo cúbico formado al reemplazar cada vértice de un hipercubo por un ciclo.

cubo: Véase cúbico

cuerda: Véase cordal

Remove ads

D


DAG: Abreviatura en inglés de grafo acíclico dirigido, un grafo dirigido sin ciclos dirigidos.

de primer orden: La lógica de grafos de primer orden es una forma de lógica en la que las variables representan vértices de un grafo y existe un predicado binario para comprobar si dos vértices son adyacentes. Debe distinguirse de la lógica de segundo orden, en la que las variables también pueden representar conjuntos de vértices o aristas.

de segundo orden: La lógica de grafos de segundo orden es una forma de lógica en la que las variables pueden representar vértices, aristas, conjuntos de vértices y (a veces) conjuntos de aristas. Esta lógica incluye predicados para comprobar si un vértice y una arista son incidentes, así como si un vértice o una arista pertenecen a un conjunto. Debe distinguirse de la lógica de primer orden, en la que las variables solo pueden representar vértices.

débilmente conexo: Un grafo dirigido se denomina débilmente conexo si al reemplazar todas sus aristas dirigidas por aristas no dirigidas se obtiene un grafo conexo (no dirigido).

degeneración: Un grafo $k$ -degenerado es un grafo no dirigido en el que cada subgrafo inducido tiene un grado mínimo de $k$ como máximo. La degeneración de un grafo es el $k$ más pequeño para el cual es $k$ -degenerado. Un ordenamiento por degeneración es un ordenamiento de los vértices tal que cada vértice tiene un grado mínimo en su subgrafo inducido y en todos los vértices posteriores; en un ordenamiento por degeneración de un grafo $k$ -degenerado, cada vértice tiene como máximo $k$ vecinos posteriores. La degeneración también se conoce como número de núcleo, anchura y ligamiento $k$ , y uno más la degeneración también se denomina número de coloración o número de Székeres-Wilf. Los grafos $k$ -degenerados también se han denominado grafos $k$ -inductivos.

degenerado: Véase degeneración

Δ, δ: $Δ (G)$ (usando la letra griega delta) es el grado máximo de un vértice en $G$ , y $δ (G)$ es el grado mínimo; véase grado.

densidad: En un grafo de «n» nodos, la densidad es la razón entre el número de aristas del grafo y el número de aristas en un grafo completo de «n» nodos. Véase densidad.

descomposición: Véase descomposición en árboles, descomposición en rutas o descomposición en ramas.

descomposición en árboles: Una descomposición en árboles de un grafo $G$ es un árbol cuyos nodos están etiquetados con conjuntos de vértices de $G$ . Estos conjuntos se denominan bolsas. Para cada vértice $v$ , las bolsas que contienen $v$ deben inducir un subárbol del árbol, y para cada arista $uv$ debe existir una bolsa que contenga tanto a $u$ como a $v$ . El ancho de una descomposición en árboles es uno menos que el número máximo de vértices en cualquiera de sus bolsas; el ancho del árbol de $G$ es el ancho mínimo de cualquier descomposición en árboles de $G$ .

descomposición en orejas: Una descomposición en orejas es una partición de las aristas de un grafo en una secuencia de orejas, cada uno de cuyos extremos (después del primero) pertenece a una oreja anterior y cada uno de cuyos puntos interiores no pertenece a ninguna oreja anterior. Una oreja abierta es un camino simple (una oreja sin vértices repetidos), y una descomposición de orejas abiertas es una descomposición de orejas en la que cada oreja posterior a la primera es abierta. Un grafo tiene una descomposición de orejas abiertas si y solo si es biconexo. Una oreja es impar si tiene un número impar de aristas, y una descomposición en orejas impares es una descomposición en orejas donde cada oreja es impar. Un grafo tiene una descomposición en orejas impares si y solo si es factor crítico.

descomposición en ramas: Una descomposición en ramas de $G$ es una agrupación jerárquica de las aristas de $G$ , representada por un árbol binario sin raíz cuyas hojas están etiquetadas por las aristas de $G$ . El ancho de una descomposición en ramas es el máximo, sobre las $e$ aristas de este árbol binario, del número de vértices compartidos entre los subgrafos determinados por las aristas de $G$ en los dos subárboles separados por $e$ . El ancho de rama de $G$ es el ancho mínimo de cualquier descomposición en ramas de $G$ .

descomposición en rutas: Una descomposición en rutas de un grafo $G$ es una descomposición en árboles cuyo árbol subyacente es una ruta o camino. Su ancho se define de la misma manera que para las descomposiciones en árboles, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición en rutas de $G$ es el ancho de ruta de $G$ .

desconectado: Fuertemente conectado (no confundir con desconectado)

desconectado: No conectado.

desconexión: Causa de ser desconectado.

diamante: El grafo diamante es un grafo no dirigido con cuatro vértices y cinco aristas.

diámetro: El diámetro de un grafo conexo es la longitud máxima de un problema del camino más corto. Es decir, es la distancia máxima entre pares de vértices en el grafo. Si el grafo tiene pesos en sus aristas, entonces su diámetro ponderado mide la longitud del camino mediante la suma de los pesos de las aristas en el camino, mientras que el diámetro no ponderado mide la longitud del camino mediante el número de aristas. Para grafos conexos, las definiciones varían: el diámetro puede definirse como infinito, como el diámetro mayor de un componente conexo, o puede ser indefinido.

dígono: Un dígono es un ciclo simple de longitud dos en un grafo dirigido o un multigrafo. Los dígonos no pueden aparecer en grafos no dirigidos simple, ya que requieren repetir la misma arista dos veces, lo cual viola la definición de simple.

dígrafo: Sinónimo de grafo dirigido.^[1]

dirección: 1. La relación asimétrica entre dos vértices adyacentes en un grafo, representado como una flecha.; 2. La relación asimétrica entre dos vértices en una ruta dirigida.

dirigido: Un grafo dirigido es aquel en el que las aristas tienen una dirección definida, de un vértice a otro.^[1] En un grafo mixto, una arista dirigida es, a su vez, aquella que tiene una dirección definida; las aristas dirigidas también pueden denominarse arcos o flechas.

dirruta: Véase ruta dirigida.

disjunto: 1. Dos subgrafos son disjuntos en aristas si no comparten aristas, y disjuntos en vértices si no comparten vértices.; 2. La unión disjunta de dos o más grafos es un grafo cuyos conjuntos de vértices y aristas son la unión disjunta de los conjuntos correspondientes.

disperso: Un grafo disperso es aquel cuyas distancias de ruta más cortas se aproximan a las de un grafo denso u otro espacio métrico. Entre las variaciones se incluyen los dispersos geométricos, grafos cuyos vértices son puntos en un espacio geométrico; los dispersos en árbol, árboles generadores de un grafo cuyas distancias se aproximan a las distancias del grafo; y los generadores de grafos, subgrafos dispersos de un grafo denso cuyas distancias se aproximan a las distancias del grafo original. Un generador voraz es un generador de grafos construido mediante un algoritmo voraz, generalmente uno que considera todas las aristas, de la más corta a la más larga, y conserva las necesarias para preservar la aproximación de la distancia.

dispersor: Un subgrafo es dispersor cuando incluye todos los vértices del grafo dado. Los casos importantes incluyen los árboles de expansión, subgrafos generadores que son árboles, y los de coincidencia perfecta, subgrafos generadores que son emparejamientos. Un subgrafo generador también puede denominarse factor, especialmente (pero no solo) cuando es regular.

distancia: La distancia entre dos vértices cualesquiera en un grafo es la longitud del camino más corto que tiene los dos vértices como extremos.

dividido: 1. Un grafo dividido es un grafo cuyos vértices pueden dividirse en un grupo y un conjunto independiente. Una clase relacionada de grafos, los grafos de doble división, se utilizan en la demostración del teorema fuerte del grafo perfecto.; 2. Una ruptura de un grafo arbitrario es una partición de sus vértices en dos subconjuntos no vacíos, de modo que las aristas que abarcan este corte forman un subgrafo bipartito completo. Las divisiones de un grafo pueden representarse mediante una estructura de árbol llamada "descomposición por división". Una división se denomina división fuerte cuando no es atravesada por ninguna otra división. Una división se denomina no trivial cuando ambos lados tienen más de un vértice. Un grafo se denomina primo cuando no tiene divisiones no triviales.; 3. La división de aristas (a veces llamada división de vértices) es una operación elemental de grafos que divide un vértice en dos, donde estos dos nuevos vértices son adyacentes a los vértices a los que era adyacente el vértice original. La operación inversa de la división de vértices es la contracción de vértices.

domático: Una partición domática de un grafo es una partición de los vértices en conjuntos dominantes. El número domático del grafo es el número máximo de conjuntos dominantes en dicha partición.

dominante: Un conjunto dominante es un conjunto de vértices que incluye o es adyacente a todos los vértices del grafo. No debe confundirse con una cobertura de vértices, un conjunto de vértices que incide en todas las aristas del grafo. Entre los tipos especiales importantes de conjuntos dominantes se incluyen los conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y los conjuntos dominantes conexos (conjuntos dominantes que inducen subgrafos conexos). Un conjunto dominante de un solo vértice también puede denominarse vértice universal. El número de dominación de un grafo es el número de vértices del conjunto dominante más pequeño.

dual: Un grafo dual de un grafo plano $G$ es un grafo que tiene un vértice por cada cara de $G$ .

Remove ads

E


E: $E (G)$ es el conjunto de aristas de $G$ ; véase conjunto de aristas.

elegibilidad: Un grafo es $k$ elegible si tiene una lista de coloración siempre que cada vértice tenga una lista de $k$ colores disponibles. La elegibilidad del grafo es el $k$ más pequeño para el que es $k$ elegible.

elegible

enlace: Sinónimo de degeneración.

enumeración: La enumeración de grafos es el problema de contar los grafos en una clase dada de grafos, en función de su orden. De forma más general, los problemas de enumeración pueden referirse a problemas de contar una determinada clase de objetos combinatorios (como camarillas, conjuntos independientes, coloraciones o árboles de expansión), o de listar algorítmicamente todos estos objetos.

equilibrado: Un grafo bipartito o multipartito está equilibrado si cada dos subconjuntos de su partición de vértices tienen tamaños uno dentro del otro.

equivalencia homomórfica: Dos grafos son homomórficamente equivalentes si existen dos homomorfismos, uno de cada grafo al otro.

espacio: En teoría de grafos algebraica, varios espacios vectoriales sobre un cuerpo binario pueden estar asociados a un grafo. Cada uno tiene conjuntos de aristas o vértices como sus vectores, y diferencia simétrica de conjuntos como su operación de suma vectorial. El espacio arista es el espacio de todos los conjuntos de aristas, y el espacio vértice es el espacio de todos los conjuntos de vértices. El espacio de corte es un subespacio del espacio de aristas cuyos elementos son los conjuntos de corte del grafo. El espacio ciclo tiene como elementos los subgrafos eulerianos generadores.

espacio de corte: El espacio de corte de un grafo es un GF(2)-espacio vectorial que tiene los conjuntos de corte del grafo como sus elementos y la diferencia simétrica de conjuntos como su operación de suma vectorial.

esparcido: Un grafo esparcido es aquel que tiene pocas aristas en relación con su número de vértices. En algunas definiciones, la misma propiedad también debería ser cierta para todos los subgrafos del grafo dado.

espectral

espectro: El espectro de un grafo es el conjunto de valores propios de su matriz de adyacencia. La teoría espectral de grafos es la rama de la teoría de grafos que utiliza espectros para analizar grafos. Véase también expansión espectral.

estable: Un conjunto estable es sinónimo de un conjunto independiente.

estrella: Una estrella es un árbol con un vértice interno; equivalentemente, es un grafo bipartito completo $K 1, n$ para algunos $n \geq 2$ . El caso especial de una estrella con tres hojas se denomina garra.

etiqueta: 1. Información asociada a un vértice o arista de un grafo. Un grafo etiquetado es un grafo cuyos vértices o aristas tienen etiquetas. Los términos "etiquetado por vértice" o "etiquetado por arista" pueden usarse para especificar qué objetos de un grafo tienen etiquetas. Un etiquetado se refiere a varios problemas diferentes de asignación de etiquetas a grafos sujetos a ciertas restricciones. Véase también coloración de grafos, donde las etiquetas se interpretan como colores.; 2. En el contexto de la enumeración de grafos, se dice que los vértices de un grafo están etiquetados si son distinguibles entre sí. Por ejemplo, esto se puede lograr estableciendo una correspondencia biunívoca entre los vértices y los enteros desde 1 hasta el orden del grafo. Cuando los vértices están etiquetados, los grafos isomorfos entre sí (pero con diferentes ordenaciones de vértices) se contabilizan como objetos separados. Por el contrario, cuando los vértices no están etiquetados, los grafos isomorfos entre sí no se contabilizan por separado.

euleriano: Una ruta euleriana es un recorrido que utiliza cada arista de un grafo exactamente una vez. Un circuito euleriano (también llamado ciclo euleriano o recorrido de Euler) es un recorrido cerrado que utiliza cada arista exactamente una vez. Un grafo euleriano es un grafo con un circuito euleriano. Para un grafo no dirigido, esto significa que el grafo es conexo y cada vértice tiene grado par. Para un grafo dirigido, esto significa que el grafo es fuertemente conexo y cada vértice tiene grado de entrada igual al grado de salida. En algunos casos, el requisito de conectividad se flexibiliza, y un grafo que cumple solo los requisitos de grado se denomina euleriano.

excentricidad: La excentricidad de un vértice es la distancia máxima entre él y cualquier otro vértice.

expansión: 1. La expansión de aristas, número isoperimétrico o constante de Cheeger de un grafo $G$ es la razón mínima, sobre los subconjuntos $S$ de como máximo la mitad de los vértices de $G$ , del número de aristas que salen de $S$ al número de vértices en $S$ .; 2. La expansión de vértices, número isoperimétrico de vértices o magnificación de un grafo $G$ es la razón mínima, sobre subconjuntos $S$ de como máximo la mitad de los vértices de $G$ , del número de vértices externos pero adyacentes a $S$ con el número de vértices en $S$ .; 3. La expansión vecina única de un grafo $G$ es la razón mínima, sobre subconjuntos de como máximo la mitad de los vértices de $G$ , del número de vértices fuera de $S$ pero adyacentes a un vértice único en $S$ con el número de vértices en $S$ .; 4. La expansión espectral de un grafo $d$ -regular $G$ es el salto espectral entre el mayor autovalor $d$ de su matriz de adyacencia y el segundo mayor autovalor.; 5. Una familia de grafos tiene expansión acotada si todos sus menores $r$ -superficiales tienen una razón de aristas a vértices acotada por una función de $r$ , y expansión polinómica si la función de $r$ es un polinomio.

expansor: Un grafo expansor es un grafo cuya expansión de aristas, vértices o espectral está acotada desde cero.

exterior: (Véase cara).

exterior-planar: (Un grafo plano exterior es un grafo que puede incrustarse en el plano (sin intersecciones) de modo que todos los vértices estén en la cara exterior del grafo.

Remove ads

F


factor: Un factor de un grafo es un subgrafo generador: un subgrafo que incluye todos los vértices del grafo. El término se utiliza principalmente en el contexto de subgrafos regulares: un factor $k$ es un factor $k$ -regular. En particular, un factor $1$ equivale a una coincidencia perfecta. Un grafo de factor crítico es un grafo en el que, al eliminar cualquier vértice, se obtiene un grafo con un factor $1$ .

factorización: Una factorización de grafo es una partición de las aristas del grafo en factores; una $k$ -factorización es una partición en $k$ -factores. Por ejemplo, una $1$ -factorización es una coloración de aristas con la propiedad adicional de que cada vértice incide sobre una arista de cada color.

familia: Sinónimo de clase.

fin: Un fin de un grafo infinito es una clase de equivalencia de semirrectas, donde dos semirrectas son equivalentes si existe una tercera semirrecta que incluye infinitos vértices de ambas.

finito: Un grafo es finito si tiene un número finito de vértices y un número finito de aristas. Muchas fuentes asumen que todos los grafos son finitos sin indicarlo explícitamente. Un grafo es localmente finito si cada vértice tiene un número finito de aristas incidentes. Un grafo infinito es un grafo que no es finito: tiene infinitos vértices, infinitas aristas, o ambos.

flecha: Un par ordenado de vértices, como una arista en un grafo dirigido. Una flecha $(x, y)$ tiene una cola $x$ , una cabeza $y$ y una dirección $desde x hacia y$ . Se dice que $y$ es el sucesor directo de $x$ y $x$ es el predecesor directo de $y$ . La flecha $(y, x)$ es la flecha inversa de la flecha $(x, y)$ .

flecha invertida: Una flecha con una dirección opuesta comparada con otra flecha. La flecha $(y, x)$ es la flecha invertida de la flecha $(x, y)$ .

forma canónica: Véase canonización.

Frucht: 1. Robert Frucht; 2. Grafo de Frucht, uno de los dos grafos cúbicos más pequeños sin simetrías no triviales.; 3. Teorema de Frucht que afirma que todo grupo finito es el grupo de simetrías de un grafo finito.

fuente: Una fuente, en un grafo dirigido, es un vértice sin aristas entrantes (el grado de entrada es 0).

fuerte: 1. Para la conectividad fuerte y los componentes fuertemente conexos de grafos dirigidos, véanse conectado y componente. Una orientación fuerte es una orientación fuertemente conexa; véase orientación.; 2. Para el teorema del grafo perfecto fuerte, véase perfecto.; 3. Un grafo fuertemente regular es un grafo regular en el que cada dos vértices adyacentes tienen el mismo número de vecinos compartidos y cada dos vértices no adyacentes tienen el mismo número de vecinos compartidos.; 4. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo par de longitud seis o más tiene una cuerda impar.; 5. Un grafo fuertemente perfecto es un grafo en el que cada subgrafo inducido tiene un conjunto independiente que cumple con todos los cliques maximales. Los grafos de Meyniel también se denominan "grafos muy fuertemente perfectos" porque en ellos, cada vértice pertenece a dicho conjunto independiente.

fuerza: La fuerza de un grafo es la razón mínima entre el número de aristas eliminadas del grafo y los componentes creados, considerando todas las eliminaciones posibles; es análogo a la tenacidad, basada en las eliminaciones de vértices.

Remove ads

G


G: Una variable que se usa a menudo para denotar un grafo.

garra: Una garra es un árbol con un vértice interno y tres hojas, o equivalentemente, el grafo bipartito completo $K 1,3$ . Un grafo sin garras es aquel que no tiene un subgrafo inducido que sea una garra.

gemelo: Dos vértices $u,v$ son gemelos verdaderos si tienen el mismo entorno cerrado: $N G [u] = N G [v]$ (esto implica que $u$ y $v$ son vecinos), y son falsos gemelos si tienen el mismo vecindario abierto: $N G (u) = N G (v))$ (esto implica que $u$ y $v$ no son vecinos).

género: El género de un grafo es el género mínimo de una superficie sobre la que se puede incrustar; véase embebido.

geodésica: Como sustantivo, geodésica es sinónimo del problema del camino más corto. Cuando se usa como adjetivo, significa relacionado con los caminos más cortos o las distancias de los caminos más cortos.

gigante: En la teoría de grafos aleatorios, un componente gigante es un componente conexo que contiene una fracción constante de los vértices del grafo. En los modelos estándar de grafos aleatorios, normalmente hay como máximo un componente gigante.

grado: 1. El grado de un vértice en un grafo es su número de aristas incidentes.^[1] El grado de un grafo $G$ (o su grado máximo) es el máximo de los grados de sus vértices, a menudo denotado como $Δ (G)$ . El grado mínimo de $G$ es el mínimo de los grados de sus vértices, a menudo denotado como $δ (G)$ . El grado a veces se denomina "valencia", mientras que el grado de $v$ en $G$ puede denotarse como $d G (v)$ , $d (G)$ o $deg(v)$ . El grado total es la suma de los grados de todos los vértices; por el lema del apretón de manos es un número par. El grado es el conjunto de grados de todos los vértices, ordenados de mayor a menor. En un grafo dirigido, se puede distinguir el grado de entrada (número de aristas entrantes) y el grado de salida (número de aristas salientes).^[1]; 2. El grado de homomorfismo de un grafo es sinónimo de su «número de Hadwiger», el orden del menor clique más grande.

grado de entrada: Número de aristas entrantes en un grafo dirigido; véase grado.

grado de salida: (Véase grado).

grafo: El objeto fundamental de estudio en teoría de grafos es un sistema de vértices conectados en pares por aristas. A menudo se subdivide en grafos dirigidos o en grafos según si las aristas tienen orientación o no. Los grafos mixtos incluyen ambos tipos de aristas.

grafo de utilidad: El problema de los tres servicios es el nombre del grafo bipartito completo $K_{3,3}$ .

grafo cuasi-lineal: Un grafo cuasi-lineal o grafo localmente cobipartito es un grafo en el que la vecindad abierta de cada vértice puede dividirse en dos cliques. Estos grafos son siempre sin garras e incluyen como caso especial los grafos lineales. Se utilizan en la teoría de estructura de grafos sin garras.

grafo de Moore: Un grafo de Moore es un grafo regular para el cual la cota de Moore se cumple exactamente. La cota de Moore es una desigualdad que relaciona el grado, el diámetro y el orden de un grafo, demostrada por Edward F. Moore. Todo grafo de Moore es una jaula.

grafo de Thomsen: El problema de los tres servicios es el nombre para el grafo bipartito completo $K_{3,3}$ .

grafo forzado: Un grafo forzado es un grafo $H$ tal que evaluar la densidad de subgrafos de $H$ en los grafos de una secuencia de grafos $G(n)$ es suficiente para comprobar si dicha secuencia es cuasi aleatoria.

grafo funcional: Un grafo funcional es un grafo dirigido donde cada vértice tiene grado de salida uno. De forma equivalente, un grafo funcional es un pseudobosque dirigido maximal.

grafo no ponderado: Un grafo cuyos vértices y aristas no tienen asignados pesos; lo opuesto de un grafo ponderado.

grafo nulo: Véase grafo vacío.

grafo ponderado: Un grafo cuyos vértices o aristas tienen asignados pesos. Un grafo ponderado por vértice tiene pesos en sus vértices y un grafo ponderado por aristas tiene pesos en sus aristas.

grafo sin aristas: El grafo nulo o grafo totalmente desconectado en un conjunto dado de vértices es el grafo que no tiene aristas. A veces se le llama grafo vacío, pero este término también puede referirse a un grafo sin vértices.

grafo vacío: 1. Un grafo nulo en un conjunto no vacío de vértices.; 2. Un grafo nulo es un grafo sin vértices ni aristas.

Grötzsch: 1. Herbert Grötzsch; 2. El grafo de Grötzsch, el grafo sin triángulos más pequeño que requiere cuatro colores en cualquier coloración adecuada.; 3. El teorema de Grötzsch que afirma que los grafos planares sin triángulos siempre pueden colorearse con un máximo de tres colores.

Remove ads

H


H: Una variable que se usa a menudo para denotar un grafo, especialmente cuando otro grafo ya ha sido denotado por $G$ .

H-coloración: Una coloración $H$ de un grafo $G$ (donde $H$ también es un grafo) es un homomorfismo de $H$ a $G$ .

H-libre: Un grafo es $H$ -libre si no tiene un subgrafo inducido isomorfo a $H$ , es decir, si $H$ es un subgrafo inducido prohibido. Los grafos $H$ -libres son la familia de todos los grafos (o, a menudo, todos los grafos finitos) que son $H$ -libres.^[7] Por ejemplo, los grafos sin triángulos son los grafos que no tienen un grafo triángulo como subgrafo. La propiedad de ser $H$ -libre siempre es hereditaria. Un grafo es $H$ -libre de menores si no tiene un menor isomorfo a $H$ .

Hadwiger: 1. Hugo Hadwiger; 2. El número de Hadwiger de un grafo es el orden del menor completo más grande del grafo. También se denomina número de clique de contracción o grado de homomorfismo.; 3. La conjetura de Hadwiger es la conjetura de que el número de Hadwiger nunca es menor que el número cromático.

hamiltoniano: Un camino hamiltoniano o ciclo hamiltoniano es un camino de expansión simple o ciclo de expansión simple: cubre todos los vértices del grafo exactamente una vez. Un grafo es hamiltoniano si contiene un ciclo hamiltoniano y trazable si contiene un camino hamiltoniano.

hereditario: Una propiedad hereditaria de grafos es una propiedad cerrada bajo subgrafos inducidos: si $G$ tiene una propiedad hereditaria, entonces también la debe tener cada subgrafo inducido de $G$ . Compárese monótono (cerrado bajo todos los subgrafos) con cerrado bajo menores.

hermano: En un árbol con raíz, un hermano de un vértice $v$ es un vértice que tiene el mismo vértice padre que $v$ .

hexágono: Un ciclo simple que consta de exactamente seis aristas y seis vértices.

hijo: En un árbol con raíz, un hijo de un vértice $v$ es vecino de $v$ en un borde saliente, que se dirige lejos de la raíz.

hiperarco: Una hiperarista dirigida con un conjunto de origen y destino.

hiperarista: Una arista en un hipergrafo, con cualquier número de extremos, a diferencia del requisito de que las aristas de los grafos tengan exactamente dos extremos.

hipercubo: Un grafo hipercubo es un grafo formado a partir de los vértices y aristas de la geometría de un hipercubo.

hipergrafo: Un hipergrafo es una generalización de un grafo en la que cada arista (denominada hiperarista en este contexto) puede tener más de dos extremos.

hipo-: Este prefijo, en combinación con una propiedad de grafo, indica un grafo que no posee dicha propiedad, pero tal que cada subgrafo formado al eliminar un solo vértice sí la posee. Por ejemplo, un grafo hipohamiltoniano es uno que no tiene un ciclo hamiltoniano, pero para el cual cada eliminación de un vértice produce un subgrafo hamiltoniano. Compárese con crítico, utilizado para grafos que poseen una propiedad, pero para los cuales cada eliminación de un vértice no la posee.^[8]

hoja: 1. Un vértice hoja o vértice colgante (especialmente en un árbol) es un vértice cuyo grado es $1$ . Una arista hoja o arista colgante es la arista que conecta un vértice hoja con su vecino.; 2. Una potencia de hojas de un árbol es un grafo cuyos vértices son las hojas del árbol y cuyas aristas conectan hojas cuya distancia en el árbol es, como máximo, un umbral determinado.

homomorfismo: 1. Un homomorfismo de grafos es una aplicación del conjunto de vértices de un grafo al conjunto de vértices de otro grafo, que aplica vértices adyacentes a vértices adyacentes. Este tipo de aplicación entre grafos es el más común en los enfoques de teoría de categorías de la teoría de grafos. Una coloración adecuada de grafos puede describirse equivalentemente como un homomorfismo a un grafo completo.; 2. El grado de homomorfismo de un grafo es sinónimo de su «número de Hadwiger», el orden del menor clique más grande.

Remove ads

I


impar: 1. Un ciclo impar es un ciclo cuya longitud es impar. La cintura impar de un grafo no bipartito es la longitud de su ciclo impar más corto. Un agujero impar es un caso especial de ciclo impar: uno que es inducido y tiene cuatro o más vértices.; 2. Un vértice impar es un vértice cuyo grado es impar. Por el lema del apretón de manos, todo grafo finito no dirigido tiene un número par de vértices impares.; 3. Una oreja impar es un camino simple o un ciclo simple con un número impar de aristas, utilizado en descomposiciones de orejas impares de grafos con factor crítico; véase oreja.; 4. Una cuerda impar es una arista que conecta dos vértices separados por una distancia impar en un ciclo par. Las cuerdas impares se utilizan para definir grafos fuertemente cordales.; 5. Un grafo impar es un caso especial de grafo de Kneser, con un vértice por cada subconjunto de elementos $(n - 1)$ de un conjunto de elementos $(2 n - 1)$ y una arista que conecta dos subconjuntos cuando sus conjuntos correspondientes son disjuntos.

incidencia: Una incidencia en un grafo es un par vértice-arista tal que el vértice es un extremo de la arista.

incidente: Relación entre una arista y uno de sus extremos.^[1]

incomparabilidad: Un grafo de incomparabilidad es el complemento de un grafo de comparabilidad; véase comparabilidad.

incrustación: Un grafo embebido es una representación topológica de un grafo como subconjunto de un espacio topológico, donde cada vértice se representa como un punto, cada arista se representa como una curva cuyos extremos son los extremos de la curva, y no hay otras intersecciones entre vértices o aristas. Un grafo plano es un grafo que presenta dicha incrustación en el plano euclídeo, y un grafo toroidal es un grafo que presenta dicha incrustación en un toro. El genus de un grafo es el género mínimo posible de una variedad bidimensional en la que puede incrustarse.

independiente: 1. Un conjunto independiente es un conjunto de vértices que induce un subgrafo sin aristas. También puede denominarse conjunto estable o coclique. El conjunto independiente $α (G)$ es el tamaño del conjunto independiente.; 2. En el matroide gráfico de un grafo, un subconjunto de aristas es independiente si el subgrafo correspondiente es un árbol o un bosque. En el matroide bicircular, un subconjunto de aristas es independiente si el subgrafo correspondiente es un seudobosque.

indiferencia: Un grafo de indiferencia es otro nombre para designar a un grafo de intervalo propio o a un grafo de intervalo unitario; véase propio.

inducido: Un subgrafo inducido o subgrafo completo de un grafo es un subgrafo formado a partir de un subconjunto de vértices y de todas las aristas cuyos extremos están en el subconjunto. Los casos especiales incluyen rutas inducidas y ciclos inducidos, subgrafos inducidos que son caminos o ciclos.

inductivo: Sinónimo de degenerado.

infinito: Un grafo infinito es aquel que no es finito; véase finito.

interno: Un vértice de un camino o árbol es interno si no es una hoja; es decir, si su grado es mayor que uno. Dos caminos son internamente disjuntos (también denominados "independientes") si no tienen ningún vértice en común, excepto el primero y el último.

intersección: 1. La intersección de dos grafos es su mayor subgrafo común, el grafo formado por los vértices y las aristas que pertenecen a ambos grafos.; 2. Un grafo de intersección es un grafo cuyos vértices corresponden a conjuntos u objetos geométricos, con una arista entre dos vértices exactamente cuando los dos conjuntos u objetos correspondientes tienen una intersección no vacía. Varias clases de grafos pueden definirse como grafos de intersección de ciertos tipos de objetos, por ejemplo, los grafos cordales (grafos de intersección de subárboles de un árbol), los grafos circulares (grafos de intersección de cuerdas de una circunferencia), los grafos de intervalos (grafos de intersección de intervalos de una recta), los grafos línea (grafos de intersección de las aristas de un grafo) y los grafos clique (grafos de intersección de los grupos máximos de un grafo). Todo grafo es un grafo de intersección para alguna familia de conjuntos, y esta familia se denomina representación de intersección del grafo. El número de intersección de un grafo $G$ es el número total mínimo de elementos en cualquier representación de intersección de $G$ .

intervalo: 1. Un grafo de intervalos es un grafo de intersección de intervalos de una recta.; 2. El intervalo $[u, v]$ en un grafo es la unión de todos los caminos más cortos de $u$ a $v$ .; 3. El grosor del intervalo es sinónimo de ancho de ruta.

invariante: Sinónimo de propiedad.

inverso: Véase transponer.

isomorfismo: Un isomorfismo de grafos es una incidencia biunívoca que preserva la correspondencia de los vértices y aristas de un grafo con los vértices y aristas de otro grafo. Dos grafos relacionados de esta manera se denominan isomorfos.

isomorfo: Dos grafos son isomorfos si existe un isomorfismo entre ellos; véase isomorfismo.

isoperimétrico: Véase expansión.

istmo: Sinónimo de puente, en el sentido de una arista cuya eliminación desconecta el grafo.

Remove ads

J


jaula: Una jaula es un grafo regular con el orden más pequeño posible para su cintura.

K


K: Para la notación de grafos completos, grafos bipartitos completos y grafos multipartitos completos, véase completo.

κ: $κ (G)$ (usando la letra griega kappa) puede referirse a la conectividad de vértices de $G$ o al número de cliques de $G$ .

k-ario: Un árbol k-ario es un árbol con raíz en el que cada vértice interno tiene un máximo de $k$ hijos. Un árbol 1-ario es simplemente una ruta. Un árbol 2-ario también se denomina árbol binario, aunque este término se refiere más propiamente a árboles 2-arios en los que los hijos de cada nodo se distinguen como hijos izquierdos o derechos (con un máximo de uno de cada tipo). Se dice que un árbol $k$ -ario está completo si cada vértice interno tiene exactamente $k$ hijos.

L


L: $L (G)$ es el grafo línea de $G$ ; véase línea.

libro: 1. Un libro, grafo de libro o libro triangular es un grafo tripartito $K 1,1, n$ completo; una colección de $n$ triángulos unidos en una arista compartida.; 2. Otro tipo de grafo, también llamado libro o libro cuadrilátero, es una colección de $4$ -ciclos unidos en una arista compartida; el producto cartesiano de una estrella por una arista.; 3. Un embebido en libro es una incrustación de un grafo en un libro topológico, un espacio formado mediante la unión de un conjunto de semiplanos en una línea compartida. Normalmente, los vértices de la incrustación deben estar en la línea, lo que se denomina lomo de la incrustación, y sus aristas deben estar dentro de un único semiplano, una de las páginas del libro.

línea: Sinónimo de una arista no dirigida. El grafo línea $L (G)$ de un grafo $G$ es un grafo con un vértice por cada arista de $G$ y una arista por cada par de aristas que comparten un extremo en $G$ .

línea dirigida: Véase flecha.

lista: 1. Un lista de adyacencia es una representación computacional de grafos para su uso en algoritmos de grafos.; 2. Una lista de colores es una variación de la coloración de grafos en la que cada vértice tiene una lista de colores disponibles.

local: Una propiedad local de un grafo es aquella que está determinada únicamente por la vecindad de los vértices del grafo. Por ejemplo, un grafo es localmente finito si todas sus vecindades son finitas.

longitud: En un grafo no ponderado, la longitud de un ciclo, camino o recorrido es el número de aristas que utiliza. En un grafo ponderado, puede ser la suma de los pesos de las aristas que utiliza. La longitud se utiliza para definir el problema del camino más corto, la cintura (la longitud de ciclo más corta) y el camino más largo entre dos vértices de un grafo.

M


magnificación: Sinónimo de expansión de vértice.

mariposa: 1. El grafo mariposa tiene cinco vértices y seis aristas; está formado por dos triángulos que comparten un vértice.; 2. El grafo mariposa es utilizado como arquitectura de red en computación distribuida, y está estrechamente relacionado con los ciclos conexos con cubos.

matriz de adyacencia: La matriz de adyacencia de un grafo es una matriz cuyas filas y columnas están indexadas por los vértices del grafo, con un uno en la celda para la fila $i$ y la columna $j$ cuando los vértices $i$ y $j$ son adyacentes, y un cero en caso contrario.^[9]

matriz de incidencia: El matriz de incidencia de un grafo es una matriz cuyas filas están indexadas por los vértices del grafo y cuyas columnas están indexadas por las aristas. Se asigna un 1 a la fila $i$ y a la columna $j$ cuando el vértice $i$ y la arista $j$ son incidentes, y un 0 en caso contrario.

maximal: 1. Un subgrafo de un grafo dado $G$ es maximal para una propiedad particular si posee dicha propiedad, pero ningún otro supergrafo que también sea un subgrafo de $G$ posee la misma propiedad. Es decir, es un elementos maximal y minimal de los subgrafos con la propiedad. Por ejemplo, un clique es un subgrafo completo que no se puede expandir a un subgrafo completo mayor. El término "maximal" debe distinguirse de "máximo": un subgrafo máximo siempre es máximal, pero no necesariamente viceversa.; 2. Un grafo simple con una propiedad dada es máximo para dicha propiedad si no es posible añadirle más aristas (manteniendo el conjunto de vértices inalterado), preservando tanto la simplicidad del grafo como la propiedad. Así, por ejemplo, un grafo plano es un grafo planar, de modo que añadirle más aristas crearía un grafo no planar.

máximo: Un subgrafo de un grafo dado $G$ es máximo para una propiedad particular si es el subgrafo más grande (por orden o tamaño) entre todos los subgrafos con esa propiedad. Por ejemplo, un clique es cualquiera de los grupos más grandes en un grafo dado.

mediana: 1. Una mediana de un triple de vértices, un vértice que pertenece a los caminos más cortos entre todos los pares de vértices, especialmente en grafos medianos y en grafos modulares.; 2. Un grafo mediano es un grafo en el que cada tres vértices tienen una mediana única.

menor: Un grafo $H$ es un menor de otro grafo $G$ si $H$ puede obtenerse eliminando aristas o vértices de $G$ y contrayéndolas en $G$ . Es un menor superficial si puede formarse como un menor de tal manera que los subgrafos de $G$ que se contrajeron para formar vértices de $H$ tengan todos un diámetro pequeño. $H$ es un menor de $G$ si $G$ tiene un subgrafo que es una subdivisión de $H$ . Un grafo es $H$ -libre de menores si no tiene a $H$ como menor. Una familia de grafos es cerrada a menores si está cerrada bajo menores. El teorema de Robertson-Seymour caracteriza a las familias cerradas a menores por tener un conjunto finito de menores prohibidos.

Meyniel: 1. Henri Meyniel, teórico de grafos francés.; 2. Un grafo de Meyniel es un grafo en el que cada ciclo impar de longitud cinco o más tiene al menos dos cuerdas.

mínimo: Un subgrafo de un grafo dado es mínimo para una propiedad particular si posee dicha propiedad, pero ningún subgrafo propio la posee. Es decir, es un elemento mínimo de los subgrafos con la propiedad.

mixto: Un grafo mixto es un grafo que puede incluir aristas dirigidas y no dirigidas.

modular: 1. Un grafo modular es un grafo en el que cada triplete de vértices tiene al menos un vértice mediano que pertenece a los caminos más cortos entre todos los pares del triplete.; 2. Descomposición modular, una descomposición de un grafo en subgrafos, donde todos los vértices se conectan al resto del grafo de la misma manera.; 3. Modularidad de un agrupamiento de grafos, la diferencia entre el número de aristas entre clústeres y su valor esperado.

molino de viento: Un grafo de molino de viento es la unión de un conjunto de cliques, todas del mismo orden, con un vértice compartido que pertenece a todos los cliques y todos los demás vértices y aristas son distintos.

monótono: Una propiedad monótona de los grafos es una propiedad que es cerrada bajo subgrafos: si $G$ tiene una propiedad monótona, entonces también la debe tener cada subgrafo de $G$ . Compárese con hereditario (cerrado bajo subgrafos inducidos) o "cerrado-menor" (cerrado bajo menores).

multigrafo: Un multigrafo es un grafo que permite múltiples adyacencias (y, a menudo, bucles propios); un grafo que no requiere ser simple.

multiplicidad: La multiplicidad de una arista es el número de aristas en una adyacencia múltiple. La multiplicidad de un grafo es la multiplicidad máxima de cualquiera de sus aristas.

N


N: 1. Para la notación de vecindades abiertas y cerradas, véase entorno.; 2. $n$ en minúscula se usa a menudo (especialmente en informática) para indicar el número de vértices en un grafo dado.

nivel: 1. Esta es la "profundidad" de un nodo más 1, aunque algunos^[10] la definen como sinónimo de "profundidad". El nivel de un nodo en un árbol con raíz es el número de nodos en la ruta desde la raíz hasta el nodo. Por ejemplo, la raíz tiene nivel 1 y cualquiera de sus nodos adyacentes tiene nivel 2.; 2. Un conjunto de todos los nodos con el mismo nivel o profundidad.^[10]

no dirigido: Un grafo no dirigido es un grafo en el que los dos extremos de cada arista no se distinguen entre sí. Véase también «dirigido» y «mixto». En un grafo mixto, una arista no dirigida es, a su vez, aquella en la que los extremos no se distinguen entre sí.

nodo: Sinónimo de vértice.

núcleo: 1. Un $k$ -núcleo es el subgrafo inducido que se forma eliminando todos los vértices de grado menor que $k$ y todos los vértices cuyo grado se vuelve menor que $k$ tras eliminaciones anteriores. Véase degeneración.; 2. Un núcleo es un grafo $G$ tal que todo homomorfismo de grafos desde $G$ hasta sí mismo es un isomorfismo.; 3. El núcleo de un grafo $G$ es un grafo minimal $H$ tal que existen homomorfismos desde $G$ hasta $H$ y viceversa. $H$ es único hasta el isomorfismo. Puede representarse como un subgrafo inducido de $G$ y es un núcleo en el sentido de que todos sus autohomomorfismos son isomorfismos.; 4. En la teoría de emparejamientos de grafos, el núcleo de un grafo es un aspecto de su descomposición de Dulmage-Mendelsohn, formado como la unión de todos los emparejamientos máximos.

núcleo de un grafo dirigido: Un núcleo de un grafo dirigido es un conjunto de vértices que es tanto estable como absorbente.

nudo: Sección ineludible de un grafo directo. Véase nudo y teoría de nudos.

número de atadura: La relación más pequeña posible entre el número de vecinos de un subconjunto propio de vértices y el tamaño del subconjunto.^[11]

número de búsqueda: Número de búsqueda de nodo es sinónimo de ancho de ruta.

número de disociación: Un subconjunto de vértices en un grafo G se denomina disociación si induce un subgrafo con un máximo de grado 1.

número de Grundy: 1. El número de Grundy de un grafo es el número máximo de colores producidos por una coloración codiciosa, con un orden de vértices mal elegido.

número de separación: El número de separación de vértices es un sinónimo de ancho de ruta.

O


orden: 1. El orden de un grafo $G$ es el número de sus vértices, $| V (G)|$ . La variable $n$ se utiliza a menudo para esta cantidad. Véase también tamaño, el número de aristas.; 2. Un tipo de lógica de grafos; véanse primer orden y segundo orden.; 3. Un ordenamiento de un grafo es la disposición de sus vértices en una secuencia, especialmente en el contexto de ordenamiento topológico (un orden de un grafo acíclico dirigido en el que cada arista va de un vértice anterior a uno posterior en el orden) y ordenamiento de la degeneración (un orden en el que cada vértice tiene el grado mínimo en su subgrafo inducido y en todos los vértices posteriores).; 4. Para el orden de un refugio o una zarza, véanse refugio y zarza.

oreja: Una oreja de un grafo es un camino cuyos extremos pueden coincidir, pero en el que, por lo demás, no hay repeticiones de vértices ni aristas.

orientación

orientado: 1. Un orientación de un grafo no dirigido es la asignación de direcciones a sus aristas, lo que lo convierte en un grafo dirigido. Un grafo orientado es aquel al que se le ha asignado una orientación. Así, por ejemplo, un poliárbol es un árbol orientado. Se diferencia de un árbol dirigido (una arborescencia) en que no se requiere consistencia en las direcciones de sus aristas. Otros tipos especiales de orientación incluyen torneos (orientaciones de grafos completos); orientación fuerte (orientaciones fuertemente conexas); orientación acíclica (orientaciones acíclicas); orientación euleriana (orientaciones eulerianas); y orientación transitiva (orientaciones transitivamente cerradas).; 2. Grafo orientado, utilizado por algunos autores como sinónimo de grafo dirigido.

oruga: Un árbol oruga u oruga es un árbol en el que los nodos internos inducen un camino.

P


padre: En un árbol con raíz, el padre de un vértice $v$ es vecino de $v$ en la arista entrante, la que se dirige hacia la raíz.

par: Divisible por dos; por ejemplo, un ciclo par es un ciclo cuya longitud es par.

pendiente: Véase hoja.

perfecto: 1. Un grafo perfecto es un grafo en el que, en cada subgrafo inducido, el número cromático es igual al número de clique. El teorema del grafo perfecto y el teorema del grafo perfecto fuerte son dos teoremas sobre grafos perfectos: el primero demuestra que sus complementos también son perfectos y el segundo demuestra que son exactamente los grafos sin agujeros impares ni antiagujeros.; 2. Un gráfico perfectamente ordenable es un grafo cuyos vértices pueden ordenarse de tal manera que un algoritmo de coloración voraz con este ordenamiento colorea óptimamente cada subgrafo inducido. Los grafos perfectamente ordenables son una subclase de los grafos perfectos.; 3. Una coincidencia perfecta es un emparejamiento que satura cada vértice; véase coincidencia.; 4. Una 1-factorización perfecta es una partición de las aristas de un grafo en emparejamientos perfectos, de modo que cada dos emparejamientos forman un ciclo hamiltoniano.

periférico: 1. Un ciclo periférico o ciclo no separador es un ciclo con como máximo un puente.; 2. Un vértice periférico es un vértice cuya excentricidad es máxima. En un árbol, este debe ser una hoja.

peso: Un valor numérico, asignado como etiqueta a un vértice o arista de un grafo. El peso de un subgrafo es la suma de los pesos de los vértices o aristas dentro de ese subgrafo.

Petersen: 1. Julius Petersen (18391910), teórico de grafos danés.; 2. El grafo de Petersen, un grafo de 10 vértices y 15 aristas, se utiliza frecuentemente como contraejemplo.; 3. El teorema de Petersen, que afirma que todo grafo cúbico sin puente tiene una correspondencia perfecta.

planar: Un grafo plano es un grafo que tiene un embebido en el plano euclidiano. Un grafo plano es un grafo planar para el cual ya se ha fijado una incrustación particular. Un grafo $k$ -planar es aquel que se puede dibujar en el plano con un máximo de $k$ cruces por arista.

poliárbol: Un poliárbol es un árbol orientado; equivalentemente, un grafo acíclico dirigido cuyo grafo subyacente no dirigido es un árbol.

potencia: 1. Una potencia de grafo $G k$ de un grafo $G$ es otro grafo en el mismo conjunto de vértices; dos vértices son adyacentes en $G k$ cuando están a una distancia máxima de $k$ en $G$ . La potencia de hoja es un concepto estrechamente relacionado, derivado de una potencia de un árbol al tomar el subgrafo inducido por las hojas del árbol.; 2. El análisis de potencia de grafo es un método para analizar redes complejas mediante la identificación de cliques, biclíques y estrellas dentro de la red.; 3. La ley potencial en la distribución de grado de la red libre de escala son un fenómeno en el que el número de vértices de un grado dado es proporcional a una potencia de dicho grado.

predecesor: Un vértice que precede a un vértice dado en un ruta dirigida.

predecesor directo: Cola de una arista dirigida cuya cabeza es el vértice dado.

primo: 1. Un grafo primo se define a partir de un grupo algebraico, con un vértice para cada número primo que divide el orden del grupo.; 2. En la teoría de descomposición modular, un grafo primo es un grafo sin módulos no triviales.; 3. En la teoría de ruptura, cortes cuyo conjunto de cortes es un grafo bipartito completo, un grafo primo es un grafo sin divisiones. Todo grafo cociente de una descomposición máxima por divisiones es un grafo primo, una estrella o un grafo completo.; 4. Un grafo primo para el producto cartesiano de grafos es un grafo conexo que no es en sí mismo un producto. Todo grafo conexo puede factorizarse de forma única en un producto cartesiano de grafos primos.

profundidad: La profundidad de un nodo en un árbol con raíz es el número de aristas en el camino desde la raíz hasta el nodo. Por ejemplo, la profundidad de la raíz es 0 y la profundidad de cualquiera de sus nodos adyacentes es 1. Es el nivel de un nodo menos uno. Sin embargo, cabe destacar que algunos autores usan "profundidad" como sinónimo de "nivel" de un nodo.^[12]

prohibido: Un caracterización de grafos prohibidos define una familia de grafos como aquellos que no tienen otros grafos como subgrafos, subgrafos inducidos o menores. Si $H$ es uno de los grafos que no aparece como subgrafo, subgrafo inducido o menor, entonces se dice que $H$ está prohibido.

propiedad: Una propiedad de grafo es algo que puede ser cierto para algunos grafos y ser falso en otros, y esto depende únicamente de la estructura del grafo y no de información incidental como las etiquetas. Las propiedades de los grafos pueden describirse de forma equivalente en términos de clases de grafos (los grafos que poseen una propiedad dada). De forma más general, una propiedad de grafo también puede ser una función de grafos que, a su vez, es independiente de información incidental, como el tamaño, el orden o la secuencia de grados de un grafo. Esta definición más general de una propiedad también se denomina invariante del grafo.

propio: 1. Un subgrafo propio es un subgrafo que elimina al menos un vértice o arista con respecto a todo el grafo. Para grafos finitos, los subgrafos propios nunca son isomorfos a todo el grafo, pero para grafos infinitos sí pueden serlo.; 2. Una coloración propia es una asignación de colores a los vértices de un grafo (una coloración) que asigna diferentes colores a los extremos de cada arista; véase coloración.; 3. Un gráfico de intervalo propio o grafo de arco circular propio es un grafo de intersección de un conjunto de intervalos o arcos circulares (respectivamente) tal que ningún intervalo o arco contiene a otro intervalo o arco. Los grafos de intervalo propio también se denominan grafos de intervalo unitario (porque siempre se pueden representar mediante intervalos unitarios) o grafos de indiferencia.

pseudobosque: Un seudobosque es un grafo no dirigido en el que cada componente conexo tiene como máximo un ciclo, o un grafo dirigido en el que cada vértice tiene como máximo una arista saliente.

pseudografo: Un pseudografo es un grafo o multigrafo que permite bucles propios.

puente: 1. Un puente, istmo o arista de corte es una arista cuya eliminación desconectaría el grafo. Un grafo sin puentes es aquel que no los tiene; equivalentemente, es un grafo conexo de dos aristas.; 2. Un puente de un subgrafo H es un subgrafo conexo maximal separado del resto del grafo por H. Es decir, es un subgrafo maximal disjunto con respecto a H y en el que cada dos vértices y aristas pertenecen a un camino internamente disjunto con respecto a H. H puede ser un conjunto de vértices. Una cuerda es un puente de una arista. En pruebas de planaridad, H es un ciclo y un ciclo periférico es un ciclo con como máximo un puente; debe ser un límite de cara en cualquier incrustación plana de su grafo.; 3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo, pero es más corto que cualquiera de los caminos del ciclo que conectan los mismos dos vértices. Un grafo puenteado es un grafo en el que cada ciclo de cuatro o más vértices tiene un puente.

punto de articulación: Un vértice en un grafo conexo cuya eliminación dejaría un grafo desconectado. En términos más generales, un vértice cuya eliminación aumenta el número de componentes.

punto de corte: Véase punto de articulación.

punto final: Uno de los dos vértices unidos por una arista dada, o uno de los primeros o últimos vértices de un camino, sendero o ruta. El primer extremo de una arista dirigida dada se denomina «cola» y el segundo extremo se denomina «cabeza».

R


radio: El radio de un grafo es el mínimo excentricidad de cualquier vértice.

raíz: 1. Un vértice designado en un grafo, particularmente en árboles dirigidos y grafos con raíz.; 2. La operación inversa a una potencia de grafo: una raíz $k$ -ésima de un grafo $G$ es otro grafo en el mismo conjunto de vértices, tal que dos vértices son adyacentes en $G$ si y solo si tienen una distancia máxima de $k$ en la raíz.

rama: Un camino de vértices de grado dos, que termina en vértices cuyo grado es distinto de dos.^[13]

Ramanujan: Un grafo de Ramanujan es un grafo cuya expansión espectral es lo más grande posible. Es decir, es un grafo $d$ -regular, tal que el segundo valor propio más grande de su matriz de adyacencia es como máximo $2{\sqrt {d-1}}$ .

rayo: Un rayo, en un grafo infinito, es un camino simple infinito con exactamente un punto final. Los finales de un grafo son clases de equivalencia de rayos.

reconocible: En el contexto de la conjetura de reconstrucción, una propiedad de grafo es reconocible si su verdad puede determinarse a partir del mazo del grafo. Se sabe que muchas propiedades de grafos son reconocibles. Si la conjetura de reconstrucción es verdadera, todas las propiedades de grafos son reconocibles.

reconstrucción: La conjetura de reconstrucción establece que cada grafo no dirigido $G$ está determinado de forma única por su "mazo", un multiconjunto de grafos formado al eliminar un vértice de $G$ de todas las maneras posibles. En este contexto, la reconstrucción es la formación de un grafo a partir de su mazo.

rectángulo: Un ciclo simple que consta de exactamente cuatro aristas y cuatro vértices.

red de mundo pequeño: Una red de mundo pequeño es un grafo en el que la mayoría de los nodos no son vecinos entre sí, pero se puede acceder a la mayoría de los nodos desde cualquier otro nodo mediante un pequeño número de saltos o pasos. Específicamente, una red de mundo pequeño se define como un grafo donde la distancia típica "L" entre dos nodos elegidos aleatoriamente (el número de pasos requeridos) crece proporcionalmente al logaritmo del número de nodos "N" en la red.^[14]

red: Un grafo cuyos atributos (por ejemplo, nombres) están asociados a los nodos y/o aristas.

refugio: Un $k$ -refugio es una función que asigna cada conjunto $X$ con menos de $k$ vértices a una de sus solapas, lo que a menudo cumple condiciones de consistencia adicionales. El orden de un refugio es el número $k$ . Los refugios se pueden utilizar para caracterizar el ancho de árbol de grafos finitos y los extremos y números de Hadwiger de grafos infinitos.

regular: Un grafo es $d$ -regular cuando todos sus vértices tienen grado $d$ . Un grafo regular es un grafo $d$ -regular para algún $d$ .

rueda: Un grafo rueda es un grafo formado sumando un vértice universal a un ciclo simple.

ruta: Una ruta puede ser un camino o un recorrido sin vértices repetidos ni, por consiguiente, aristas (también llamado camino simple), dependiendo del origen. Casos especiales importantes incluyen el camino inducido y el problema del camino más corto.

S


saturado: Véase coincidencia.

secuencia de grafos cuasi-aleatorios: Una sucesión de grafo cuasialeatorio es una secuencia de grafos que comparte varias propiedades con una secuencia de grafos aleatorios generada según modelo de gráfico aleatorio de Erdős-Rényi.

sendero: Un paseo sin aristas repetidas.

simple: 1. Un grafo simple es un grafo sin bucles ni adyacencias múltiples. Es decir, cada arista conecta dos extremos distintos y no hay dos aristas con los mismos extremos. Una arista simple es una arista que no forma parte de una adyacencia múltiple. En muchos casos, se asume que los grafos son simples a menos que se especifique lo contrario.; 2. Una ruta simple o un ciclo simple es una ruta o ciclo que no tiene vértices repetidos y, en consecuencia, no tiene aristas repetidas.

sin puentes: Un grafo sin puentes o un grafo sin istmos es un grafo que no tiene aristas de puente (es decir, istmos); y por lo tanto, cada componente conectado es un grafo con 2 aristas conexas.

snark: Un snark es un grafo cúbico simple, conexo y sin puentes con un índice cromático igual a 4.

solapa: Para un conjunto de $X$ vértices, una $X$ -solapa es un componente conexo del subgrafo inducido formado al eliminar $X$ . El término solapa se usa comúnmente en el contexto de "refugios", funciones que asignan pequeños conjuntos de vértices a sus solapas. Véase también puente de un ciclo, que es una solapa de los vértices del ciclo o una cuerda del ciclo.

subárbol: Un subárbol es un subgrafo conexo de un árbol. A veces, para árboles con raíz, los subárboles se definen como un tipo especial de subgrafo conexo, formado por todos los vértices y aristas accesibles desde un vértice seleccionado.

subbosque: Un subgrafo de un bosque.

subgrafo: Un subgrafo de un grafo $G$ es otro grafo formado a partir de un subconjunto de los vértices y aristas de $G$ . El subconjunto de vértices debe incluir todos los extremos del subconjunto de aristas, pero también puede incluir vértices adicionales. Un subgrafo generador es aquel que incluye todos los vértices del grafo; un subgrafo inducido es aquel que incluye todas las aristas cuyos extremos pertenecen al subconjunto de vértices.

sucesor: Un vértice que viene después de un vértice dado en un ruta dirigida.

sucesor directo: Cola de una arista dirigida cuya cola es el vértice dado.

sumidero: Un sumidero, en un grafo dirigido, es un vértice sin aristas salientes (el grado de salida es igual a 0).

superconcentrador: Un superconcentrador es un grafo con dos subconjuntos designados de igual tamaño de vértices $I$ y $O$ , de modo que por cada dos subconjuntos de igual tamaño $S$ de $I$ y $T$ de $O$ existe una familia de caminos disjuntos que conecta cada vértice de $S$ con un vértice de $T$ . Algunas fuentes requieren, además, que un superconcentrador sea un grafo acíclico dirigido, con $I$ como sus fuentes y $O$ como sus sumideros.

supergrafo: Un grafo formado al sumar vértices, aristas o ambos a un grafo dado. Si $H$ es un subgrafo de $G$ , entonces $G$ es un supergrafo de $H$ .

T


tamaño: El tamaño de un grafo $G$ es el número de sus aristas, $| E (G)|$ .^[15] La variable $m$ se utiliza a menudo para esta cantidad. Véase también "orden", el número de vértices.

theta: 1. Un grafo theta es la unión de tres trayectorias internamente disjuntas (simples) que comparten dos vértices finales distintos.^[16]; 2. El grafo theta de un conjunto de puntos en el plano euclidiano se crea construyendo un sistema de conos que rodea cada punto y añadiendo una arista por cono, hasta el punto cuya proyección sobre un rayo central del cono sea menor.; 3. La función theta de Lovász, o número de Lovász, de un grafo es un invariante de grafo relacionado con el número de clique y el número cromático, que puede calcularse en tiempo polinomial mediante programación semidefinida.

topológico: 1. Un grafo topológico es una representación de los vértices y las aristas de un grafo mediante puntos y curvas en el plano (sin evitar necesariamente los cruces).; 2. La teoría de grafos topológica es el estudio de las incrustaciones de grafos.; 3. Ordenamiento topológico es el problema algorítmico de ordenar un grafo acíclico dirigido en un orden topológico, una secuencia de vértices tal que cada arista va de un vértice anterior a uno posterior en la secuencia.

torneo regular: Un torneo regular es un torneo donde el grado de entrada es igual al grado de salida para todos los vértices.

torneo: Un torneo es una orientación de un grafo completo; es decir, es un grafo dirigido tal que cada dos vértices están conectados por exactamente una arista dirigida (que va solo en una de las dos direcciones entre los dos vértices).

totalmente desconectado: Sinónimo de grafo sin aristas.

transitivo: Relacionado con la relación transitiva. La clausura transitiva de un grafo dirigido dado es un grafo en el mismo conjunto de vértices que tiene una arista de un vértice a otro siempre que el grafo original tenga un camino que conecta los mismos dos vértices. Una reducción transitiva de un grafo es un grafo minimal con la misma clausura transitiva; los grafos acíclicos dirigidos tienen una reducción transitiva única. Una orientación transitiva es una orientación de un grafo que es su propia clausura transitiva; existe solo para un grafo de comparabilidad.

transposición: El grafo transpuesto de un grafo dirigido dado es un grafo con los mismos vértices, pero con cada arista invertida en dirección. También puede denominarse recíproco o inverso del grafo.

trazable: Un grafo trazable es un grafo que contiene un camino hamiltoniano.

triángulo: Un ciclo de longitud tres en un grafo. Un grafo sin triángulos es un grafo no dirigido que no tiene subgrafos triangulares.

trivial: Un grafo trivial es un grafo con 0 o 1 vértice.^[17] Un grafo con 0 vértices también se llama grafo nulo.

Turán: 1. Pál Turán; 2. Un grafo de Turán es un grafo multipartito completo balanceado.; 3. El teorema de Turán afirma que los grafos de Turán tienen el máximo número de aristas entre todos los grafos libres de clique de un orden dado.; 4. El problema de la fábrica de ladrillos de Turán solicita el mínimo número de cruces en el dibujo de un grafo bipartito completo.

U


uniforme: Un hipergrafo es $k$ -uniforme cuando todas sus aristas tienen extremos $k$ , y uniforme cuando es $k$ -uniforme para algunos $k$ . Por ejemplo, los grafos ordinarios son iguales a los hipergrafos $2$ -uniformes.

unión: La unión de dos grafos se forma a partir de su unión disjunta añadiendo una arista de cada vértice de un grafo a cada vértice del otro. Equivalentemente, es el complemento de la unión disjunta de los complementos.

universal: 1. Un grafo universal es un grafo que contiene como subgrafos todos los grafos de una familia de grafos dada, o todos los grafos de un tamaño u orden dado dentro de una familia de grafos dada.; 2. Un vértice universal (también llamado vértice dominante) es un vértice adyacente a todos los demás vértices del grafo. Por ejemplo, un grafo rueda y un grafo umbral conexos siempre tienen un vértice universal.; 3. En la lógica de grafos, un vértice que es cuantificado universalmente en una fórmula puede denominarse vértice universal para esa fórmula.

V


V: Véase conjunto de vértices.

valencia: Sinónimo de grado.

vecindad: El entorno abierto (o vecindad) de un vértice $v$ es el subgrafo inducido por todos los vértices adyacentes a $v$ . La vecindad cerrada se define de la misma manera, pero también incluye al propio $v$ . La vecindad abierta de $v$ en $G$ puede denotarse como $N G (v)$ o $N (v)$ , y la vecindad cerrada puede denotarse como $N G [v]$ o $N [v]$ . Cuando no se especifica la apertura o la clausura de una vecindad, se asume que es abierta.

vecindad

vecino: Un vértice adyacente a un vértice dado.

vértice libre: 1. Un vértice que no está en una arista coincidente en un apareamiento.; 2. Un vértice que no ha sido coincidente.

vértice separador: Véase punto de articulación.

vértice unario: En un árbol con raíz, un vértice unario es aquel que tiene exactamente un vértice hijo.

vértice: Un vértice es (junto con las aristas) una de las dos unidades básicas a partir de las cuales se construyen los grafos. Los vértices de los grafos suelen considerarse objetos atómicos, sin estructura interna.

vínculo: Un conjunto de corte mínimo: un conjunto de aristas cuya eliminación desconecta el grafo, para el que ningún subconjunto propio tiene la misma propiedad.

Vizing: 1. Vadim G. Vizing; 2. El teorema de Vizing afirma que el índice cromático es como máximo uno mayor que el grado máximo.; 3. La conjetura de Vizing sobre el número de dominancia de productos cartesianos de grafos.

volumen: La suma de los grados de un conjunto de vértices.

voraz: Producido por un algoritmo voraz. Por ejemplo, un coloración codiciosa de un grafo es una coloración que se obtiene al considerar los vértices en una secuencia y asignar a cada vértice el primer color disponible.

vuelta: Una ruta cerrada, un paseo que comienza y termina en el mismo vértice y no tiene aristas repetidas. Los recorridos de Euler son recorridos que utilizan todas las aristas del grafo; véase euleriano.

W


$W$: La letra $W$ se utiliza en la notación para grafo rueda y para el grafo molino de viento (por windmill en inglés). La notación no está estandarizada.

Wagner: 1. Klaus Wagner; 2. El grafo de Wagner, una escalera de Möbius de ocho vértices.; 3. El teorema de Wagner que caracteriza grafos planares por sus menores prohibidos.; 4. Teorema de Wagner que caracteriza los grafos sin menores $K 5$ .

Z


zarza: Una zarza es una colección de subgrafos conexos que se tocan mutuamente, donde dos subgrafos se tocan si comparten un vértice o si cada uno incluye un extremo de una arista. El orden de una zarza es el tamaño mínimo de un conjunto de vértices que tiene una intersección no vacía con todos los subgrafos. El ancho de árbol de un grafo es el orden máximo de cualquiera de sus zarzas.

Véase también

Teoría de grafos

Referencias

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads