Tipos de grafos: la clasificación completa con ejemplos
Los grafos se clasifican por sus aristas (dirigidas o no, con peso o sin él, simples o repetidas), por su conexión (conexo o fuertemente conexo), por sus ciclos (cíclico, acíclico, dirigido acíclico), por cómo se reparten los vértices (bipartito, completo), por su dibujo (plano) y por sus recorridos (euleriano, hamiltoniano).
Última actualización: 2026-11-17
Contenido de esta página
- ¿Cuáles son los tipos de grafos?
- Grafos dirigidos y no dirigidos: qué es un dígrafo
- Grafo ponderado y no ponderado
- Grafo simple y multigrafo: aristas paralelas y lazos
- Grafo conexo, fuertemente conexo y débilmente conexo
- Grafo cíclico, acíclico y DAG: qué es un grafo dirigido acíclico
- Grafo bipartito y grafo completo
- Grafo plano: cuándo se dibuja sin cruces
- Grafo euleriano y grafo hamiltoniano
- Cómo saber qué tipo de grafo tienes: un clasificador en Python
- Primero el tipo, después el algoritmo
En 1960, una revista china de matemáticas publicó, en chino, un artículo de Kwan Mei-Ko [12]. Dos años después salió traducido al inglés como Graphic Programming Using Odd or Even Points [1][12]. Trataba de optimizar la ruta de un cartero [1]. El planteamiento cabe en una línea: pasar por cada calle al menos una vez y volver al punto de partida, con el recorrido más corto posible [1].
El nombre con el que hoy se conoce llegó después. Lo cuenta el diccionario de algoritmos del NIST, el instituto de normas técnicas de Estados Unidos. Alan J. Goldman le sugirió a Jack Edmonds llamarlo «problema del cartero chino» [1]. Edmonds trabajaba entonces en el grupo de investigación de operaciones de Goldman, en la Oficina Nacional de Normas, hoy el NIST [1]. Le gustó lo pegajoso del nombre y lo adoptó [1].
La misma entrada trae un dato que importa más que la anécdota. Si la red mezcla calles de doble sentido con calles de un solo sentido, hallar la ruta óptima es un problema NP-completo [1]. La etiqueta nombra una familia de problemas para los que, según explica un libro de texto del Instituto Tecnológico de Massachusetts (MIT) a propósito de uno de ellos, nadie sabe si existe un método eficiente [9]. La idea de fondo es simple: la misma pregunta cambia de dificultad según el tipo de calle.
Una calle de doble sentido y una de un solo sentido son dos tipos distintos de arista. Por eso, antes de escoger un algoritmo, hay que saber qué tipo de grafo se tiene entre manos.

¿Cuáles son los tipos de grafos?
Los tipos de grafos se definen por una propiedad a la vez. Unos miran las aristas: si tienen sentido, si llevan un número o si se repiten. Otros miran el conjunto: si todo está conectado, si hay ciclos, cómo se reparten los vértices, si se puede dibujar sin cruces y qué recorridos admite. Un mismo grafo cae en varios tipos a la vez: puede ser dirigido, ponderado y acíclico. A ese último caso, el grafo dirigido acíclico, se le conoce como DAG por su sigla en inglés.
Un grafo es un conjunto de puntos, llamados vértices, unidos por líneas, llamadas aristas. Qué es exactamente y cómo se guarda en un programa está en la guía de grafos. La tabla resume la clasificación completa. Cada definición sale de una fuente primaria; los ejemplos marcados como ilustrativos son míos.
| Tipo | Definición | Qué modela | Lo que lo distingue |
|---|---|---|---|
| Dirigido (dígrafo) | Sus aristas son pares ordenados de vértices: cada una se sigue de un vértice a otro [2][7] | Un barrio de calles de un solo sentido; la ruta del cartero por ese barrio [2] | Ir de A a B no garantiza poder volver de B a A |
| No dirigido | Sus aristas son pares sin orden: cada una solo une dos vértices [2] | El mapa de calles de un barrio [2] | Ninguna arista tiene sentido |
| Ponderado | Cada arista lleva asociado un peso, es decir, un número [2] | Rutas aéreas con su distancia o su tarifa (ilustrativo) | El número sobre la arista |
| No ponderado | Las aristas no llevan número: solo dicen si hay conexión | Quién le compra a quién, sin montos (ilustrativo) | Solo cuenta si la arista existe |
| Simple | Sin lazos y sin dos aristas entre el mismo par de vértices [8][9] | Una red que solo anota si dos oficinas se comunican (ilustrativo) | A lo sumo una arista por par |
| Multigrafo | Un mismo par de vértices puede unirse con varias aristas [2] | Dos aerolíneas que vuelan la misma ruta (ilustrativo) | Aristas paralelas |
| Conexo | Grafo no dirigido con un camino entre cada par de vértices [3] | Una red de carreteras sin pueblos incomunicados (ilustrativo) | Nadie queda aislado |
| Fuertemente conexo | Grafo dirigido con un camino de cada vértice a todos los demás [3][7] | Un centro de calles de un solo sentido donde se puede volver a cualquier esquina (ilustrativo) | Se llega y se regresa siguiendo las flechas |
| Débilmente conexo | Dígrafo con un camino entre dos vértices cualesquiera si se permite recorrer las aristas hacia atrás o hacia adelante [9] | Una cadena de suministro: todo está unido, aunque el producto no vuelva al origen (ilustrativo) | Conexo solo si se ignoran las flechas |
| Cíclico | Tiene al menos un ciclo: un camino que empieza y termina en el mismo vértice e incluye al menos una arista [3][6] | Deudas cruzadas: A le debe a B, B a C y C a A (ilustrativo) | Se puede volver al punto de partida |
| Acíclico | Ningún camino empieza y termina en el mismo vértice [3][6] | Un organigrama: el NIST anota que un grafo no dirigido acíclico se parece a un árbol [3] | No hay vuelta posible |
| Dirigido acíclico (DAG) | Grafo dirigido sin ciclos dirigidos [3][7][9] | Los prerrequisitos entre materias [9]; dependencias temporales entre tareas [7] | Las flechas nunca regresan |
| Bipartito | Sus vértices se parten en dos conjuntos y ninguna arista une dos vértices del mismo conjunto [4][6][9] | Empresas y personas que se postulan a ellas (ilustrativo) | Dos lados, y aristas solo de un lado al otro |
| Completo | Grafo no dirigido con una arista entre cada par de vértices; tiene n(n − 1)/2 aristas [4][9] | Una ronda de negociación en la que cada país se reúne con todos los demás (ilustrativo) | No le falta ninguna arista posible |
| Plano | Se puede dibujar en el plano sin que se crucen aristas [4][6] | Las pistas de un circuito impreso [9] | Existe al menos un dibujo sin cruces |
| Euleriano | Tiene un recorrido cerrado que pasa por cada arista exactamente una vez [5][9] | La ruta de un cartero que no repite calle [1][5] | Conexo y con todos los grados pares [9] |
| Hamiltoniano | Tiene un ciclo que pasa por cada vértice exactamente una vez [5] | La gira de un vendedor que visita cada ciudad una vez [5] | Decidirlo es un problema NP-completo, sin método eficiente conocido [9] |

Grafos dirigidos y no dirigidos: qué es un dígrafo
Un grafo dirigido, o dígrafo, es aquel cuyas aristas tienen sentido: van de un vértice de origen a uno de destino [2][7]. En uno no dirigido, la arista solo dice que dos vértices están unidos [2]. El NIST lo explica con un barrio. El mapa de sus calles es un grafo no dirigido, pero el mapa con la ruta del cartero por ese barrio es un grafo dirigido [2].
Una calle de doble sentido puede pensarse como dos calles de un solo sentido, una de ida y otra de vuelta [2]. Por eso un grafo no dirigido siempre se puede guardar como uno dirigido con dos aristas por cada conexión [2].
En economía, la diferencia es la que hay entre «comercian» y «le vende a». La primera frase es simétrica; la segunda, no. Por ejemplo, un vuelo directo de una ciudad a otra no garantiza que exista el de vuelta (ilustrativo).
Grafo ponderado y no ponderado
Un grafo ponderado lleva un número en cada arista, su peso [2]. El peso puede ser una distancia, un tiempo, un costo o un volumen de comercio. El NIST advierte que algunos algoritmos exigen pesos con condiciones, por ejemplo que no sean negativos o que sean enteros [2].
Un grafo no ponderado solo registra si la conexión existe. Una red de vuelos que dice qué ciudades tienen ruta directa es no ponderada. La misma red con los kilómetros de cada trayecto ya es ponderada. Con ella se pueden buscar caminos mínimos, por ejemplo con el algoritmo de Dijkstra, que se explica aparte.
Grafo simple y multigrafo: aristas paralelas y lazos
Aquí las fuentes no dicen lo mismo, y conviene verlo antes de leer cualquier libro. Dos términos ayudan. Un lazo es una arista que empieza y termina en el mismo vértice [2][6]. Dos aristas son paralelas si unen el mismo par de vértices [6].
- El texto de matemáticas para computación del MIT, el Instituto Tecnológico de Massachusetts, no admite lazos en un grafo simple. Llama multigrafos a los que permiten varias aristas entre los mismos dos vértices [9].
- El curso de algoritmos 6.006 del MIT supone que todos sus grafos son simples: sin aristas repetidas y sin aristas de un vértice a sí mismo. En un grafo dirigido sí admite la pareja de ida y la de vuelta entre dos vértices [8].
- El NIST dice que algunos tipos de grafos admiten lazos y otros no [2]. Su multigrafo admite aristas repetidas. Además anota que una de las definiciones de «pseudografo» es un multigrafo con lazos [2].
- Sedgewick y Wayne, autores del libro Algorithms, de la Universidad de Princeton, definen lazos y aristas paralelas en su glosario. Entre sus problemas proponen un método para contar las aristas paralelas de un grafo [6].
Un ejemplo de lazo: si cada vértice es una terminal y cada arista una ruta, una ruta de bus circular que sale de una terminal y vuelve a la misma (ilustrativo). Un ejemplo de aristas paralelas: dos aerolíneas que vuelan el mismo trayecto. Si cada vuelo importa, el modelo es un multigrafo; si solo importa que haya conexión, basta un grafo simple.
Grafo conexo, fuertemente conexo y débilmente conexo
Un grafo conexo es uno en el que se puede ir de cualquier vértice a cualquier otro. El NIST reserva esa palabra para grafos no dirigidos, con un camino entre cada par de vértices [3]. Para los dirigidos usa «fuertemente conexo»: hay un camino de cada vértice a todos los demás, siguiendo las flechas [3]. Sedgewick y Wayne lo definen igual [7].
El curso 6.006 del MIT aplica «fuertemente conexo» a cualquier grafo. Anota que todo grafo no dirigido conexo es también fuertemente conexo, porque cada arista sin sentido sale de sus dos extremos [8]. El texto de matemáticas del mismo instituto agrega un tercer nivel. Un dígrafo es débilmente conexo si hay un camino entre dos vértices cualesquiera cuando se permite seguir las aristas hacia atrás o hacia adelante [9].
Una cadena de suministro ilustra la diferencia. La finca le vende al acopiador, el acopiador a la trilladora y la trilladora al exportador. Todo está unido si se ignoran las flechas, así que la cadena es débilmente conexa. No es fuertemente conexa: desde el exportador no hay camino de vuelta a la finca.
Grafo cíclico, acíclico y DAG: qué es un grafo dirigido acíclico
Un ciclo es un camino que empieza y termina en el mismo vértice e incluye al menos una arista [3]. Un grafo cíclico tiene al menos uno. Uno acíclico no tiene ninguno [3][6]. Si además es dirigido y no tiene ciclos dirigidos, se llama grafo dirigido acíclico, o DAG por su sigla en inglés [3][7].
El texto del MIT lo introduce con los prerrequisitos de sus materias. Cada flecha va de una materia a otra que la exige [9]. El libro lo dice con humor: graduarse tomaría una eternidad si ese grafo tuviera un recorrido cerrado, de modo que tiene que ser acíclico [9]. Sedgewick y Wayne cuentan entre las aplicaciones del orden topológico los prerrequisitos de cursos y las dependencias temporales [7].
La propiedad útil es esta: un dígrafo admite un orden topológico solo si es un DAG [7]. Un orden topológico es una lista de los vértices en la que todas las flechas apuntan de uno anterior a uno posterior [7]. En una obra, primero el cimiento, luego los muros, luego el techo. Si dos tareas se esperan mutuamente, no hay orden posible.
En ingeniería de datos, herramientas como Apache Airflow organizan sus flujos de trabajo en «Dags». Su documentación aclara que el término viene del concepto matemático, pero que en Airflow su sentido ya va más allá de esa estructura [10]. Ese uso pertenece a la ingeniería de datos.
Grafo bipartito y grafo completo
Un grafo bipartito es aquel cuyos vértices se pueden partir en dos conjuntos, de modo que cada arista tiene un extremo en cada uno [9]. El NIST lo define para grafos no dirigidos: ninguna arista une dos vértices del mismo conjunto [4]. Sedgewick y Wayne lo convierten en una prueba práctica: pintar los vértices con dos colores sin que una arista una dos del mismo color. Su programa, cuando no encuentra esa división, devuelve un ciclo de longitud impar [6].
El ejemplo económico natural es un mercado de dos lados. A un lado están las empresas con vacantes y al otro, las personas que se postulan; cada arista es una postulación (ilustrativo). Nadie se postula a otra persona, así que no hay aristas dentro de un mismo lado. El problema de emparejar a cada persona con a lo sumo un puesto se estudia como emparejamiento bipartito [9].
Un grafo completo tiene una arista entre cada par de vértices [4]. Con n vértices suma n(n − 1)/2 aristas [4][9]. El de cinco vértices, que el MIT llama K5, tiene 10. El NIST lo clasifica como grafo denso [4]: no le falta ninguna conexión posible.
Grafo plano: cuándo se dibuja sin cruces
Un grafo plano es el que se puede dibujar en el plano sin que se crucen aristas [4][6]. Lo que cuenta es que exista un dibujo así, no que el primero que se haga lo cumpla. El texto del MIT lo motiva con los circuitos: cuando los cables van sobre una superficie, como una placa o un microchip, cada cruce exige estructuras en tres dimensiones [9].
El criterio clásico usa dos grafos prohibidos. Uno es K5. El otro es K3,3: tres vértices a un lado y tres al otro, todos unidos con todos. Es el acertijo de las tres casetas de perro y las tres casas [9]. Las fuentes lo enuncian distinto:
- El NIST: un grafo es plano si no contiene un subgrafo homeomorfo a K5 o a K3,3 [4]. Homeomorfo quiere decir que queda con la misma estructura si se agregan puntos intermedios, de dos aristas cada uno, sobre sus líneas [4].
- El texto del MIT, que lo atribuye a Kuratowski: un grafo no es plano si y solo si contiene a K5 o a K3,3 como menor [9]. Un menor es lo que queda al borrar vértices, borrar aristas y fusionar vértices vecinos [9].
En la práctica no hace falta buscar esas figuras a mano. Sedgewick y Wayne citan el algoritmo de Hopcroft y Tarjan, que decide si un grafo es plano en tiempo lineal, es decir, proporcional a su tamaño [6].
Grafo euleriano y grafo hamiltoniano
Los dos nombres se confunden, y el NIST los separa en una línea: «Un ciclo hamiltoniano incluye cada vértice una vez; un ciclo de Euler incluye cada arista una vez» [5]. El de Euler es un recorrido cerrado que pasa por todas las aristas sin repetir ninguna [5][9]. El hamiltoniano es un ciclo que visita todos los vértices exactamente una vez [5].
Para el de Euler hay una prueba sencilla. El texto del MIT la enuncia así: un grafo conexo tiene un recorrido de Euler si y solo si todos sus vértices tienen grado par [9]. Basta contar cuántas aristas toca cada vértice. Para los dígrafos, el mismo texto pide que cada vértice tenga tantas flechas de entrada como de salida y que el grafo sea débilmente conexo [9]. Sedgewick y Wayne piden la misma igualdad y otra condición: que desde cualquier vértice con aristas se pueda llegar, siguiendo las flechas, a cualquier otro que también tenga aristas [7].
Esa prueba resuelve la mitad del problema del cartero. Si la red está conectada y todas las esquinas tienen grado par, existe una ruta que pasa por cada calle una sola vez. Si alguna tiene grado impar, el teorema dice que esa ruta no existe, y repetir calles es obligatorio. El NIST remite a un algoritmo que considera bueno, publicado por Edmonds y Ellis L. Johnson en 1973 [1].
Con el hamiltoniano la historia es otra. El texto del MIT lo cuenta entre los problemas NP-completos [9]. Ese rótulo agrupa problemas para los que nadie sabe si existe un procedimiento eficiente. El libro lo explica a propósito de otro de la familia, el de satisfacer una fórmula lógica [9]. El problema del agente viajero, que busca la gira más barata por todas las ciudades, es una especialización del ciclo hamiltoniano según el NIST [5].
Cómo saber qué tipo de grafo tienes: un clasificador en Python
Este programa revisa los cuatro grafos de la figura, que comparten los mismos cinco vértices, rotulados con letras. Para cada uno responde si es dirigido, si es conexo y en qué grado, si tiene ciclo y, en los no dirigidos, si es bipartito. En los no dirigidos también cuenta los grados, que deciden si el grafo es euleriano. No usa librerías externas, solo una cola de doble extremo del módulo «collections» de Python [11]. Lo ejecuté con Python 3.11.15.
# Clasificador de grafos pequeños, sin librerías.
# Los cuatro grafos son los de la figura: mismos vértices A, B, C, D, E.
from collections import deque
grafos = {
"Dirigido": (True, [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E")]),
"Ponderado": (False, [("A", "B", 4), ("B", "C", 2), ("A", "C", 5), ("C", "D", 3), ("D", "E", 1)]),
"Bipartito": (False, [("A", "B"), ("A", "D"), ("C", "B"), ("C", "D"), ("E", "D")]),
"DAG": (True, [("A", "B"), ("B", "C"), ("A", "E"), ("E", "D"), ("D", "C")]),
}
VERTICES = ["A", "B", "C", "D", "E"]
def vecinos(aristas, dirigido):
"""Lista de adyacencia; si el grafo no es dirigido, cada arista va en los dos sentidos."""
adj = {v: [] for v in VERTICES}
for a in aristas:
u, v = a[0], a[1]
adj[u].append(v)
if not dirigido:
adj[v].append(u)
return adj
def alcanzables(adj, inicio):
"""Vértices a los que se llega desde 'inicio' siguiendo las aristas."""
vistos, cola = {inicio}, deque([inicio])
while cola:
u = cola.popleft()
for w in adj[u]:
if w not in vistos:
vistos.add(w)
cola.append(w)
return vistos
def tiene_ciclo(adj, dirigido):
"""Búsqueda en profundidad: hay ciclo si se vuelve a un vértice que sigue abierto."""
estado = {v: "nuevo" for v in VERTICES}
def visitar(u, padre):
estado[u] = "abierto"
for w in adj[u]:
if not dirigido and w == padre:
continue # la misma arista de ida y vuelta no es un ciclo
if estado[w] == "abierto" or (not dirigido and estado[w] == "cerrado"):
return True
if estado[w] == "nuevo" and visitar(w, u):
return True
estado[u] = "cerrado"
return False
return any(estado[v] == "nuevo" and visitar(v, None) for v in VERTICES)
def dos_lados(adj):
"""Intenta pintar con dos colores sin que una arista una dos del mismo color."""
color = {"A": 0}
cola = deque(["A"])
while cola:
u = cola.popleft()
for w in adj[u]:
if w not in color:
color[w] = 1 - color[u]
cola.append(w)
elif color[w] == color[u]:
return None
return sorted(v for v in color if color[v] == 0), sorted(v for v in color if color[v] == 1)
for nombre, (dirigido, aristas) in grafos.items():
adj = vecinos(aristas, dirigido)
sin_sentido = vecinos(aristas, False) # el mismo grafo, ignorando las flechas
print(f"== {nombre} ==")
print(" ¿Dirigido?", dirigido)
if dirigido:
print(" ¿Débilmente conexo?", alcanzables(sin_sentido, "A") == set(VERTICES))
print(" ¿Fuertemente conexo?", all(alcanzables(adj, v) == set(VERTICES) for v in VERTICES))
else:
print(" ¿Conexo?", alcanzables(adj, "A") == set(VERTICES))
grados = {v: len(adj[v]) for v in VERTICES}
print(" Grados:", grados)
print(" ¿Todos los grados pares?", all(g % 2 == 0 for g in grados.values()))
lados = dos_lados(adj)
print(" ¿Bipartito?", lados if lados else False)
print(" ¿Tiene ciclo?", tiene_ciclo(adj, dirigido))
if len(aristas[0]) == 3:
print(" Peso total:", sum(a[2] for a in aristas))
La salida es esta:
== Dirigido ==
¿Dirigido? True
¿Débilmente conexo? True
¿Fuertemente conexo? False
¿Tiene ciclo? True
== Ponderado ==
¿Dirigido? False
¿Conexo? True
Grados: {'A': 2, 'B': 2, 'C': 3, 'D': 2, 'E': 1}
¿Todos los grados pares? False
¿Bipartito? False
¿Tiene ciclo? True
Peso total: 15
== Bipartito ==
¿Dirigido? False
¿Conexo? True
Grados: {'A': 2, 'B': 2, 'C': 2, 'D': 3, 'E': 1}
¿Todos los grados pares? False
¿Bipartito? (['A', 'C', 'E'], ['B', 'D'])
¿Tiene ciclo? True
== DAG ==
¿Dirigido? True
¿Débilmente conexo? True
¿Fuertemente conexo? False
¿Tiene ciclo? False
Tres lecturas salen de esa salida. El grafo dirigido tiene el ciclo A → B → C → A, pero desde E no se llega a ninguna parte: es débilmente conexo y no fuertemente conexo. El ponderado no es bipartito, porque A, B y C forman un triángulo, un ciclo de longitud impar.
La tercera es la más útil. El DAG, si se le quitan las flechas, forma una vuelta completa A, B, C, D, E. Siguiendo las flechas, en cambio, nunca se regresa a un vértice. Por eso el programa revisa los ciclos dirigidos en los dígrafos, no los del dibujo sin flechas. Ninguno de los cuatro es euleriano. En los dos no dirigidos, el programa muestra vértices de grado impar. En los dirigidos no cuenta entradas ni salidas; contadas a mano, tampoco cuadran: en el primero, C recibe una flecha y emite dos.
Revisar el tipo es el primer paso. Lo que sigue son los algoritmos que trabajan sobre el grafo, cada uno con su propio desarrollo. Entre ellos están los recorridos por anchura y por profundidad, el algoritmo de Dijkstra, el árbol de expansión mínima y los árboles. El orden para estudiarlos está en la guía de algoritmos.
Primero el tipo, después el algoritmo
Vuelvo al cartero. Kwan Mei-Ko planteó una ruta; Goldman le puso un nombre que se quedó; Edmonds y Johnson dieron un algoritmo. Y el NIST deja anotado que basta mezclar calles de uno y de dos sentidos para que la mejor ruta pase a ser un problema NP-completo [1].
Creo, y lo digo como opinión, que esa es la lección que más se le escapa a quien empieza con datos de redes. Se busca el algoritmo de moda antes de preguntar si las relaciones tienen sentido, si pesan, si se repiten o si pueden volver sobre sí mismas. Esas cuatro preguntas cambian qué algoritmo sirve y si existe un método rápido para la pregunta.
La tabla de arriba no es un glosario para memorizar. Es la lista de chequeo que conviene pasar antes de escribir la primera línea de código.
Preguntas frecuentes
¿Cuál es la diferencia entre un grafo dirigido y uno no dirigido? En el dirigido cada arista es un par ordenado: va de un vértice a otro y se recorre en ese sentido [2]. En el no dirigido la arista solo une dos vértices, sin orden [2]. Una red de rutas de un solo sentido es dirigida; una de «comercian entre sí», no dirigida.
¿Qué es un DAG? Es un grafo dirigido acíclico: tiene flechas y ninguna de sus rutas regresa al vértice de partida [3][7]. Modela dependencias, como los prerrequisitos de un plan de estudios [9]. Sus vértices siempre se pueden poner en un orden en el que todas las flechas apuntan hacia adelante [7].
¿Qué es un grafo bipartito? Es uno cuyos vértices se dividen en dos grupos, con todas las aristas de un grupo al otro y ninguna dentro de un mismo grupo [9]. Sirve para emparejar, por ejemplo personas con vacantes. Si el grafo tiene un ciclo de longitud impar, no es bipartito [6].
¿Qué grafos son planos? Los que admiten un dibujo sin cruces de aristas [4]. Todo grafo que contenga a K5 o a K3,3, en el sentido técnico de cada fuente, deja de serlo [4][9]. Hay algoritmos que lo deciden en tiempo proporcional al tamaño del grafo [6].
¿Todo grafo conexo es fuertemente conexo? Si el grafo no es dirigido, sí: el curso 6.006 del MIT anota que cada arista sin sentido sirve de ida y de vuelta [8]. Si es dirigido, no necesariamente. Puede estar unido al ignorar las flechas y, aun así, tener vértices desde los que no se regresa; entonces es solo débilmente conexo [9].
¿Un grafo puede ser de varios tipos a la vez? Sí. Las categorías miran propiedades distintas, así que se combinan: una red de vuelos con distancias es dirigida y ponderada. Lo que no se puede es ser cíclico y acíclico al mismo tiempo, porque una definición niega a la otra [3].
Referencias
Las citas en otro idioma son traducción propia.
- NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada Chinese postman problem (autor CRC-A; entrada modificada el 2 de noviembre de 2020) — definición: hallar un recorrido cerrado de longitud mínima que pase por cada arista al menos una vez; «Finding an optimal solution in a graph with both directed and undirected edges is NP-complete»; se parece a trazar rutas de camiones de basura y buses escolares; buen algoritmo en Jack Edmonds y Ellis L. Johnson, Matching, Euler Tours, and the Chinese Postman, Mathematical Programming, 5:88-124, 1973; Kwan Mei-Ko, Graphic Programming Using Odd or Even Points, Chinese Math., 1:273-277, 1962; nota histórica: el artículo de Kwan se refería a optimizar la ruta de un cartero; Alan J. Goldman sugirió el nombre a Jack Edmonds cuando este estaba en el grupo de investigación de operaciones de Goldman en la U.S. National Bureau of Standards (hoy NIST); Edmonds apreció lo pegajoso del nombre y lo adoptó (comunicación personal de Goldman, 14 de diciembre de 2003). NIST DADS: Chinese postman problem — Consultada: 2026-11-17.
- NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entradas directed graph («A graph whose edges are ordered pairs of vertices»; también llamado dígrafo; el mapa de calles de un barrio es no dirigido y el de la ruta del cartero por ese barrio es dirigido; una calle de doble sentido equivale a dos de un solo sentido), undirected graph (aristas como pares sin orden; se puede representar como dirigido con dos aristas por cada arista), weighted graph (un peso o número por arista; «Some algorithms require all weights to be nonnegative, integral, positive, etc.»), multigraph (el mismo par de vértices puede unirse con varias aristas; las aristas forman una bolsa, no un conjunto; «A definition of “pseudograph” is a multigraph that may have self-loops») y self-loop (arista que empieza y termina en el mismo vértice; «Some types of graphs allow self-loops, and some do not»). NIST DADS: directed graph · NIST DADS: undirected graph · NIST DADS: weighted graph · NIST DADS: multigraph · NIST DADS: self-loop — Consultada: 2026-11-17.
- NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entradas connected graph («An undirected graph that has a path between every pair of vertices»), strongly connected graph (grafo dirigido con un camino de cada vértice a todos los demás), cycle (camino que empieza y termina en el mismo vértice e incluye al menos una arista), acyclic graph (ningún camino empieza y termina en el mismo vértice; «An acyclic undirected graphic is like a tree») y directed acyclic graph (grafo dirigido sin caminos que empiecen y terminen en el mismo vértice; también DAG). NIST DADS: connected graph · NIST DADS: strongly connected graph · NIST DADS: cycle · NIST DADS: acyclic graph · NIST DADS: directed acyclic graph — Consultada: 2026-11-17.
- NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entradas bipartite graph (grafo no dirigido cuyos vértices se parten en dos conjuntos sin aristas dentro de un mismo conjunto), complete graph (grafo no dirigido con una arista entre cada par de vértices; «A complete graph has n(n-1)/2 edges»), planar graph (de Joseph L. Ganley: «A graph that can be drawn in the plane with no crossing edges»; equivalentemente, sin subgrafo homeomorfo a K5 o a K3,3) y homeomorphic (dos grafos son homeomorfos si se vuelven isomorfos al insertar vértices nuevos de grado 2 en las aristas). NIST DADS: bipartite graph · NIST DADS: complete graph · NIST DADS: planar graph · NIST DADS: homeomorphic — Consultada: 2026-11-17.
- NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entradas Euler cycle (camino que empieza y termina en el mismo vértice e incluye cada arista exactamente una vez; «A Hamiltonian cycle includes each vertex once; an Euler cycle includes each edge once»; ver también Chinese postman problem), Hamiltonian cycle (camino que empieza y termina en el mismo vértice e incluye cada uno de los otros vértices exactamente una vez; especialización: traveling salesman; nombrado por Sir William Rowan Hamilton, 1805-1865) y Hamiltonian path (camino simple que incluye todos los vértices). NIST DADS: Euler cycle · NIST DADS: Hamiltonian cycle · NIST DADS: Hamiltonian path — Consultada: 2026-11-17.
- Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 4.1 Undirected Graphs — glosario: lazo («A self-loop is an edge that connects a vertex to itself»), aristas paralelas (unen el mismo par de vértices), ciclo (camino con al menos una arista cuyo primer y último vértice coinciden), grafo acíclico (sin ciclos), grafo bipartito (vértices divisibles en dos conjuntos con todas las aristas de uno al otro); bicolorabilidad: Bipartite.java determina si hay bipartición y, si no, devuelve un ciclo de longitud impar; planaridad: «A graph is planar if it can be drawn in the plane such that no edges cross one another», y el algoritmo de Hopcroft y Tarjan lo determina en tiempo lineal; problema: «Parallel edge detection». Princeton: Algorithms, 4.1 Undirected Graphs — Consultada: 2026-11-17.
- Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 4.2 Directed Graphs — dígrafo: conjunto de vértices y aristas dirigidas que conectan pares ordenados; un dígrafo es fuertemente conexo si hay un camino dirigido de cada vértice a todos los demás; «A directed acyclic graph (or DAG) is a digraph with no directed cycles»; aplicaciones del orden topológico: prerrequisitos de cursos y dependencias temporales; orden topológico: todas las aristas apuntan de un vértice anterior a uno posterior; «A digraph has a topological order if and only if it is a DAG»; ciclo euleriano dirigido: el dígrafo lo tiene si y solo si cada vértice tiene grado de entrada igual al de salida y todos los vértices con grado no nulo están en el mismo componente fuertemente conexo. Princeton: Algorithms, 4.2 Directed Graphs — Consultada: 2026-11-17.
- MIT OpenCourseWare. Erik Demaine, Jason Ku y Justin Solomon, 6.006 Introduction to Algorithms (primavera de 2020), Lecture 9: Breadth-First Search y Recitation 9 — aristas dirigidas como pares ordenados y no dirigidas como pares sin orden; «In this class, we assume all graphs are simple»: aristas distintas ((u, v) aparece una vez, aunque (v, u) puede aparecer) y entre vértices distintos; un grafo es fuertemente conexo si hay un camino de cada nodo a todos los demás; «Note that every connected undirected graph is also strongly connected because every undirected edge incident to a vertex is also outgoing». MIT OCW: 6.006, apuntes de la clase 9 (PDF) · MIT OCW: 6.006, recitación 9 (PDF) — Consultada: 2026-11-17.
- Eric Lehman, F. Thomson Leighton y Albert R. Meyer, MIT OpenCourseWare. Mathematics for Computer Science, texto del curso 6.042J (primavera de 2015; versión del 18 de mayo de 2015) — def. 9.0.1 (grafo dirigido); def. 9.5.1: «A directed acyclic graph (DAG) is a directed graph with no cycles», introducida con los prerrequisitos de las materias del MIT («it would take forever to graduate» si hubiera un recorrido cerrado); problema 9.8: dígrafo débilmente conexo (camino entre dos vértices que puede seguir aristas hacia atrás o hacia adelante) y recorrido de Euler cuando cada vértice tiene grado de entrada igual al de salida; cap. 11: «Self-loops aren’t allowed in simple graphs», multigrafos con más de una arista entre los mismos extremos; grafo completo Kn con n(n − 1)/2 aristas; def. 11.5.1 (grafo bipartito) y emparejamiento bipartito; problema 11.44: «A connected graph has an Euler tour if and only if every vertex has even degree», y el problema del ciclo hamiltoniano como uno de los problemas NP-completos; sec. 3.5: nadie sabe si el problema de satisfacibilidad tiene un procedimiento eficiente (P vs. NP); cap. 12: K3,3 (acertijo de las casetas), cruces en placas y microchips, teorema 12.8.1 (Kuratowski: no plano si y solo si contiene K5 o K3,3 como menor) y def. 12.8.2 (menor). MIT OCW: 6.042J, Mathematics for Computer Science (PDF) — Consultada: 2026-11-17.
- Apache Software Foundation. Dags, documentación de Apache Airflow 3.4.0 — «A Dag is a model that encapsulates everything needed to execute a workflow»; «The term “DAG” comes from the mathematical concept “directed acyclic graph”, but the meaning in Airflow has evolved well beyond just the literal data structure». Apache Airflow 3.4.0: Dags — Consultada: 2026-11-17.
- Python Software Foundation. collections: Container datatypes, documentación de Python 3.11 — «Deques are a generalization of stacks and queues», con inserciones y extracciones por cualquiera de los dos extremos. Python docs 3.11: collections — Consultada: 2026-11-17.
- Martin Grötschel y Ya-xiang Yuan. Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman, Documenta Mathematica, Extra Volume ISMP «Optimization Stories» (2012), pp. 43-50 — Kwan publicó su artículo en 1960 en Acta Mathematica Sinica (en chino); la traducción al inglés es de 1962 (Chinese Mathematics 1:273-277). Documenta Mathematica: DOI 10.4171/DMS/6/10 — Consultada: 2026-11-17.
Cómo investigamos esta página
- Pregunta que responde: cuáles son los tipos de grafos, cómo los define cada fuente y qué modela cada uno
- Fuentes: identificadas 29 → incluidas 25
- Criterios de inclusión: diccionario del NIST, libro de Princeton y cursos del MIT leídos en texto completo
- Fecha de corte de los datos: 2026-11-17