Grafo

concepto en matemáticas y ciencias de la computación

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)[1]​ es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.[2]​ Son objeto de estudio de la teoría de grafos.[3]

Grafo etiquetado con 6 vértices y 7 aristas.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas o arcos).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Por lo general, un grafo se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los grafos son uno de los objetos de estudio de las matemáticas discretas.

Los bordes pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay un borde entre dos personas si se dan la mano, entonces este grafo no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si una ventaja de una persona A a una persona B significa que A le debe dinero a B , entonces este grafo es dirigido, porque la deuda no es necesariamente recíproca.

Los grafos son el tema básico estudiado por la teoría de grafos. La palabra «grafo» (en inglés, graph) fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a una relación directa entre las matemáticas y la estructura química (lo que él llamó una imagen químico-gráfica).[4][5]

Historia y problema de los puentes de Königsberg editar

 
Los siete puentes de Königsberg.

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: "¿Es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?"

Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.

De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como <<grado>> al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.

Definiciones editar

Un grafo   es un par ordenado  , donde:

Normalmente   suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo   a su número de vértices,  .

El grado de un vértice o nodo   es igual al número de arcos que lo tienen como extremo.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Dos o más aristas son paralelas si relacionan el mismo par de vértices.

Grafo no dirigido editar

 
Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo   donde:

  •  
  •   es un conjunto de pares no ordenados de elementos de  .

Un par no ordenado es un conjunto de la forma  , de manera que  . Para los grafos, estos conjuntos pertenecen al conjunto potencia de  , denotado  , y son de cardinalidad 2.

Grafo dirigido editar

 
Grafo dirigido

Un grafo dirigido o digrafo es un grafo   donde:

  •  
  •   es un conjunto de pares ordenados de elementos de  .

Dada una arista  ,   es su nodo inicial y   su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Variantes sobre las definiciones principales editar

Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces   o   pueden ser un multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

Propiedades editar

  • Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
  • Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
  • Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
  • Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Representación editar

 
Matriz de adyacencia

Las dos representaciones principales de grafos son las siguientes:

  • Matriz de adyacencia (MA): Se utiliza una matriz de tamaño n × n donde las filas y las columnas hacen referencia a los vértices para almacenar en cada casilla la longitud entre cada par de vértices del grafo. La celda MA[i, j] almacena la longitud entre el vértice i y el vértice j. Si su valor es infinito significa que no existe arista entre esos vértices, y MA[i, i] = 0.
 
Listas de adyacencia
  • Lista de adyacencia (LA): Se utiliza un vector de tamaño n (un elemento por cada vértice) donde LA[i] almacena la referencia a una lista de los vértices adyacentes a i. En una red esta lista almacenará también la longitud de la arista que va desde i al vértice adyacente.

Ejemplos editar

 

La imagen es una representación del siguiente grafo:

  • V:={1,2,3,4,5,6}
  • E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.

Tipos de grafos editar

Grafo orientado editar

Una definición de grafo orientado es que es un grafo dirigido en el que a lo sumo uno de (x, y) y (y, x) pueden ser aristas del grafo. Es decir, es un grafo dirigido que puede formarse como una orientación de un grafo no dirigido (simple).

Algunos autores utilizan "grafo orientado" con el mismo significado que "grafo dirigido". Algunos autores usan "grafo orientado" para referirse a cualquier orientación de un grafo no dirigido o multigrafo dado.

Grafo regular editar

Un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Un grafo regular con vértices de grado k se llama grafo k -regular o grafo regular de grado k.

Grafo completo editar

 
Un grafo completo con cinco vértices y diez aristas. Cada vértice tiene una arista a cada otro vértice.

Un grafo completo es un grafo en el que cada par de vértices está unido por una arista. Un grafo completo contiene todas las aristas posibles.

Grafo finito editar

Un grafo finito es un grafo en el que el conjunto de vértices y el conjunto de aristas son conjuntos finitos. En caso contrario, se denomina grafo infinito.

Comúnmente en teoría de grafos se implica que los grafos discutidos son finitos. Si los grafos son infinitos, suele indicarse específicamente.

Grafo conectado editar

En un grafo no dirigido, un par desordenado de vértices {x, y} se llama conectado si un camino lleva de x a y. En caso contrario, el par desordenado se denomina desconectado.

Un grafo conexo es un grafo no dirigido en el que cada par desordenado de vértices del grafo está conexo. En caso contrario, se denomina "grafo desconectado".

En un grafo dirigido, un par ordenado de vértices (x, y) se llama fuertemente conectado si un camino dirigido lleva de x a y. En caso contrario, el par ordenado se denomina débilmente conectado si un camino no dirigido va de x a y después de reemplazar todas sus aristas dirigidas por aristas no dirigidas. En caso contrario, el par ordenado se denomina desconectado.

Un grafo fuertemente conectado es un grafo dirigido en el que cada par ordenado de vértices del grafo está fuertemente conectado. En caso contrario, se denomina grafo débilmente conectado si cada par ordenado de vértices del grafo está débilmente conectado. En caso contrario, se denomina grafo desconectado.

Un grafo k-conectado por vértices o grafo k-conectado por aristas' es un grafo en el que ningún conjunto de k - 1 vértices (respectivamente, aristas) que, cuando se eliminan, desconectan el grafo. Un grafo conectado por vértices k a menudo se llama simplemente grafo conectado por k.

Grafo bipartito editar

Un grafo bipartito' es un grafo simple en el que el conjunto de vértices puede ser particionado en dos conjuntos, W y X, de modo que no hay dos vértices en W que compartan una arista común y no hay dos vértices en X que compartan una arista común. Alternativamente, es un grafo con un número cromático de 2.

En un grafo bipartito completo, el conjunto de vértices es la unión de dos conjuntos disjuntos, W y X, de modo que cada vértice en W es adyacente a cada vértice en X pero no hay aristas dentro de W o X.

Grafo de trayectorias editar

Un grafo de caminos o grafo lineal de orden n ≥ 2 es un grafo en el que los vértices se pueden enumerar en un orden v1, v2, ... , vn tal que las aristas son las {mset}} donde i = 1, 2, ..., n - 1. Los grafos de sendero se pueden caracterizar como grafos conexos en los que el grado de todos los vértices menos dos es 2 y el grado de los dos vértices restantes es 1. Si un grafo de sendero aparece como un subgraph de otro grafo, es un camino en ese grafo.

Grafo plano editar

Un grafo plano es un grafo cuyos vértices y aristas se pueden dibujar en un plano de forma que ninguna de las aristas se cruce con otra.

Grafo cíclico editar

Un grafo de ciclo o grafo circular de orden n ≥ 3 es un grafo en el que los vértices se pueden enumerar en un orden v1, v2, ... , vn tal que las aristas son las {vi, vi+1} donde i = 1, 2, ... , n - 1, más la arista {vn, v1}. Los grafos de ciclo pueden caracterizarse como grafos conexos en los que el grado de todos los vértices es 2. Si un grafo de ciclo aparece como subgrafo de otro grafo, es un ciclo o circuito en ese grafo.

Árbol editar

Un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una trayectoria, o equivalentemente un conectado no dirigido cíclico.

Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por a lo sumo un camino, o equivalentemente un grafo acíclico no dirigido, o equivalentemente una unión disjunta de árboles.

Poliarbol editar

Un poliárbol (o árbol dirigido o árbol orientado o red uniconexa) es un grafo acíclico dirigido (DAG) cuyo grafo no dirigido subyacente es un árbol.

Un polibosque (o bosque dirigido o bosque orientado) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque.

Clases avanzadas editar

Clases más avanzadas de grafos son:

Grafos particulares editar

Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:

Una generalización de los grafos son los llamados hipergrafos.

Véase también editar

Referencias editar

  1. Real Academia Española. «grafo : Diagrama que representa mediante puntos y líneas las relaciones entre pares de elementos y que se usa para resolver problemas lógicos, topológicos y de cálculo combinatorio.». Diccionario de la lengua española (23.ª edición). Consultado el 14 de agosto de 2019. 
  2. Trudeau, Richard J. (1993). Dover Pub., ed. Introduction to Graph Theory (Edición corregida y aumentada.). ISBN 978-0-486-67870-2. 
  3. Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. edición). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archivado desde el original el 5 de mayo de 2019. Consultado el 8 de agosto de 2012. «A graph is an object consisting of two sets called its vertex set and its edge set. » 
  4. See: . The term "graph" first appears in this paper on page 65.
  5. Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archivado desde el original el 4 de febrero de 2023. Consultado el 16 de febrero de 2016. 

Enlaces externos editar