Gráfico (matemáticas discretas)

De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Un gráfico con seis vértices y siete aristas.

En matemáticas , y más específicamente en teoría de grafos , un grafo es una estructura que equivale a un conjunto de objetos en el que algunos pares de objetos están en algún sentido "relacionados". Los objetos corresponden a abstracciones matemáticas llamadas vértices (también llamados nodos o puntos ) y cada uno de los pares de vértices relacionados se llama borde (también llamado enlace o línea ). [1] Normalmente, un gráfico 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 gráficos son uno de los objetos de estudio de las matemáticas discretas .

Los bordes pueden estar dirigidos o no dirigidos. Por ejemplo, si los vértices representan a las personas en una fiesta, y existe una arista entre dos personas si se dan la mano, entonces este gráfico está sin dirección, ya que cualquier persona A puede estrechar la mano de una persona B sólo si B también da la mano a una . Por el contrario, si cualquier ventaja de una persona A a una persona B corresponde a A le debe dinero a B , entonces este gráfico está dirigido, porque deber dinero no es necesariamente recíproco. El primer tipo de gráfico se denomina gráfico no dirigido, mientras que el último tipo de gráfico se denomina gráfico dirigido .

Los gráficos son la materia básica que estudia la teoría de grafos . La palabra "gráfico" fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 en una relación directa entre las matemáticas y la estructura química (lo que él llamó imagen químico-gráfica). [2] [3]

Definiciones [ editar ]

Las definiciones en la teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficos y estructuras matemáticas relacionadas .

Gráfico [ editar ]

Un gráfico con tres vértices y tres aristas.

Un gráfico (a veces llamado gráfico no dirigido para distinguir de un gráfico dirigido , o gráfico simple para distinguir de un multigraph ) [4] [5] es un par G = ( V , E ) , donde V es un conjunto cuyos elementos se llaman vértices (singular: vértice), y E es un conjunto de vértices emparejados, cuyos elementos se denominan aristas (a veces enlaces o líneas ).

El vértices x y y de un borde { x , y } se denominan los puntos finales del borde. El borde se dice que se unen a x e y ya sea incidente en x e y . Un vértice no puede pertenecer a ninguna arista, en cuyo caso no se une a ningún otro vértice.

Un multigraph es una generalización que permite que varios bordes tengan el mismo par de extremos. En algunos textos, los multigrafos se denominan simplemente gráficos. [6] [7]

A veces, los gráficos pueden contener bucles , que son bordes que unen un vértice consigo mismo. Para permitir bucles, la definición anterior debe cambiarse definiendo los bordes como conjuntos múltiples de dos vértices en lugar de dos conjuntos. Estos gráficos generalizados se denominan gráficos con bucles o simplemente gráficos cuando el contexto deja claro que los bucles están permitidos.

Generalmente, se supone que el conjunto de vértices V es finito; esto implica que el conjunto de aristas también es finito. Los gráficos infinitos a veces se consideran, pero se ven más a menudo como un tipo especial de relación binaria , ya que la mayoría de los resultados en gráficos finitos no se extienden al caso infinito o necesitan una prueba bastante diferente.

Un gráfico vacío es un gráfico que tiene un conjunto vacío de vértices (y por lo tanto un conjunto vacío de aristas). El orden de una gráfica es su número de vértices | V | . El tamaño de un gráfico es su número de aristas | E | . Sin embargo, en algunos contextos, como para expresar la complejidad computacional de los algoritmos, el tamaño es | V | + | E | (de lo contrario, un gráfico no vacío podría tener un tamaño de 0). El grado o valencia de un vértice es el número de aristas que le inciden; para gráficos [1]con bucles, un bucle se cuenta dos veces.

En una gráfica de orden n , el grado máximo de cada vértice es n - 1 (o n si se permiten bucles), y el número máximo de aristas es n ( n - 1) / 2 (o n ( n + 1) / 2 si se permiten bucles).

Los bordes de un gráfico definen una relación simétrica en los vértices, llamada relación de adyacencia . En concreto, dos vértices x y y son adyacentes si { x , y } es un borde. Un gráfico puede estar completamente especificado por su matriz de adyacencia A , que es una matriz cuadrada, con A ij especificando el número de conexiones desde el vértice i al vértice j . Para un gráfico simple , que indica desconexión o conexión respectivamente, mientras tanto(es decir, una arista no puede comenzar y terminar en el mismo vértice). Los gráficos con bucles propios se caracterizarán porque algunos o todos son iguales a un número entero positivo, y los gráficos múltiples (con múltiples aristas entre vértices) se caracterizarán porque algunos o todos son iguales a un número entero positivo. Los gráficos no dirigidos tendrán una matriz de adyacencia simétrica ( ).

Gráfico dirigido [ editar ]

Un gráfico dirigido con tres vértices y cuatro bordes dirigidos (la flecha doble representa un borde en cada dirección).

Un gráfico dirigido o dígrafo es un gráfico en el que los bordes tienen orientaciones.

En un sentido restringido pero muy común del término, [8] un gráfico dirigido es un par que comprende:

  • , un conjunto de vértices (también llamados nodos o puntos );
  • , un conjunto de aristas (también llamadas aristas dirigidas , enlaces dirigidos , líneas dirigidas , flechas o arcos ) que son pares ordenados de vértices (es decir, una arista está asociada con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente un gráfico simple dirigido .

En el borde dirigido de a , los vértices y se denominan los puntos finales del borde, la cola del borde y la cabeza del borde. El borde se dice que se unen y ya sea incidente en y en . Un vértice puede existir en un gráfico y no pertenecer a una arista. El borde se llama borde invertido de . Los bordes múltiples , no permitidos bajo la definición anterior, son dos o más bordes con la misma cola y la misma cabeza.

En un sentido más general del término que permite múltiples aristas, [8] un gráfico dirigido es un triple ordenado que comprende:

  • , un conjunto de vértices (también llamados nodos o puntos );
  • , Un conjunto de bordes (también llamados bordes dirigidos , enlaces dirigidos , líneas dirigidas , flechas o arcos );
  • , una función de incidencia que asigna cada borde a un par ordenado de vértices (es decir, un borde está asociado con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente multigraph dirigido .

Un bucle es una arista que une un vértice consigo mismo. Los gráficos dirigidos como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple dirigido) o es incidente (para un multigraph dirigido) que no está dentro . Entonces, para permitir bucles, las definiciones deben expandirse. Para gráficos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar la ambigüedad, estos tipos de objetos pueden denominarse precisamente un gráfico simple dirigido que permite bucles y un multigraph dirigido que permite bucles (o un carcaj ), respectivamente.

Los bordes de un grafo simple dirigido que permiten bucles es una relación homogénea ~ en los vértices de eso se llama relación de adyacencia de . Específicamente, para cada borde , se dice que sus extremos y son adyacentes entre sí, lo que se denota ~ .

Gráfico mixto [ editar ]

Un gráfico mixto es un gráfico en el que algunos bordes pueden estar dirigidos y otros no. Es un triple ordenado G = ( V , E , A ) para un gráfico simple mixto y G = ( V , E , A , ϕ E , ϕ A ) para un multigrafo mixto con V , E (los bordes no dirigidos), A (los bordes dirigidos), ϕ E y ϕ Adefinido como arriba. Los gráficos dirigidos y no dirigidos son casos especiales.

Gráfico ponderado [ editar ]

Un gráfico ponderado con diez vértices y doce aristas.

Un gráfico ponderado o una red [9] [10] es un gráfico en el que se asigna un número (el peso) a cada borde. [11] Dichos pesos podrían representar, por ejemplo, costos, longitudes o capacidades, según el problema en cuestión. Estos gráficos surgen en muchos contextos, por ejemplo, en problemas de ruta más corta , como el problema del viajante de comercio .

Tipos de gráficos [ editar ]

Gráfico orientado [ editar ]

Una definición de un gráfico orientado es que es un gráfico dirigido en el que como máximo uno de ( x , y ) e ( y , x ) pueden ser bordes del gráfico. Es decir, es un gráfico dirigido que se puede formar como una orientación de un gráfico no dirigido (simple).

Algunos autores usan "gráfico orientado" para significar lo mismo que "gráfico dirigido". Algunos autores usan "gráfico orientado" para referirse a cualquier orientación de un gráfico o multigrafo no dirigido dado.

Gráfico regular [ editar ]

Un gráfico regular es un gráfico en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Una gráfica regular con vértices de grado k se denomina k- gráfica regular o gráfica regular de grado k .

Gráfico completo [ editar ]

Un gráfico completo con cinco vértices y diez aristas. Cada vértice tiene una arista con respecto a todos los demás vértices.

Un gráfico completo es un gráfico en el que cada par de vértices está unido por una arista. Un gráfico completo contiene todos los bordes posibles.

Gráfico finito [ editar ]

Un gráfico finito es un gráfico en el que el conjunto de vértices y el conjunto de bordes son conjuntos finitos . De lo contrario, se llama grafo infinito .

Lo más común es que en la teoría de grafos se dé a entender que los gráficos analizados son finitos. Si las gráficas son infinitas, por lo general se indica específicamente.

Gráfico conectado [ editar ]

En una gráfica no dirigida, un par desordenado de vértices { x , y } se llama conectado si una ruta va de x a y . De lo contrario, el par desordenado se llama desconectado .

Un gráfico conectado es un gráfico no dirigido en el que cada par desordenado de vértices del gráfico está conectado. De lo contrario, se denomina gráfico desconectado .

En un grafo dirigido, un par ordenado de vértices ( x , y ) se llama fuertemente conectada si A conduce camino dirigido desde x a y . De lo contrario, el par ordenado se llama débilmente conectado si un no dirigidos cables camino desde x a y después de sustituir todos sus bordes dirigidos con los bordes no dirigidos. De lo contrario, el par ordenado se llama desconectado .

Un gráfico fuertemente conectado es un gráfico dirigido en el que cada par ordenado de vértices en el gráfico está fuertemente conectado. De lo contrario, se denomina gráfico débilmente conectado si cada par ordenado de vértices en el gráfico está débilmente conectado. De lo contrario, se llama gráfico desconectado .

Un gráfico conectado a k vértices o un gráfico conectado por k bordes es un gráfico en el que no existe ningún conjunto de k - 1 vértices (respectivamente, bordes) que, cuando se eliminan, desconectan el gráfico. Un gráfico conectado con k -vértices a menudo se llama simplemente un gráfico conectado con k .

Gráfico bipartito [ editar ]

Un gráfico bipartito es un gráfico simple en el que el conjunto de vértices se puede dividir en dos conjuntos, W y X , de modo que no haya dos vértices en W que compartan una arista común y que no haya dos vértices en X que compartan una arista común. Alternativamente, es un gráfico 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 bordes dentro de W o X .

Gráfico de ruta [ editar ]

Un gráfico de trayectoria o un gráfico lineal de orden n ≥ 2 es un gráfico en el que los vértices se pueden enumerar en un orden v 1 , v 2 ,…, v n tal que las aristas son { v i , v i +1 } donde i = 1, 2,…, n - 1. Los gráficos de ruta se pueden caracterizar como gráficos conectados 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 gráfico de ruta aparece como un subgráfico de otro gráfico, es una ruta en ese gráfico.

Gráfico plano [ editar ]

Un gráfico plano es un gráfico cuyos vértices y aristas se pueden dibujar en un plano de modo que no se crucen dos aristas.

Gráfico de ciclo [ editar ]

Un gráfico de ciclo o gráfico circular de orden n ≥ 3 es un gráfico en el que los vértices se pueden enumerar en un orden v 1 , v 2 ,…, v n tal que los bordes son { v i , v i +1 } donde i = 1, 2,…, n - 1, más el borde { v n , v 1 }. Los gráficos de ciclo se pueden caracterizar como gráficos conectados en los que el grado de todos los vértices es 2. Si un gráfico de ciclo aparece como un subgráfico de otro gráfico, es un ciclo o circuito en ese gráfico.

Árbol [ editar ]

Un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta , o de manera equivalente, un grafo no dirigido acíclico conectado .

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

Polytree [ editar ]

A poliárbol (o árbol dirigido o árbol orientado o red individualmente conectado ) es un gráfico dirigido acíclico (DAG) cuyo subyacente grafo no dirigido es un árbol.

A polyforest (o bosque dirigida o forestal orientada a ) es un gráfico acíclico dirigido cuyo subyacente grafo no dirigido es un bosque.

Clases avanzadas [ editar ]

Los tipos de gráficos más avanzados son:

  • El gráfico de Petersen y sus generalizaciones;
  • gráficos perfectos ;
  • cografías ;
  • grafos de cuerdas ;
  • otros gráficos con grandes grupos de automorfismos : gráficos de vértice transitivo , arco transitivo y distancia transitivo ;
  • Gráficos fuertemente regulares y sus generalizaciones Gráficos de distancia regular .

Propiedades de los gráficos [ editar ]

Dos aristas de un gráfico se denominan adyacentes si comparten un vértice común. Dos aristas de un gráfico dirigido se denominan consecutivas si la cabeza del primero es la cola del segundo. De manera similar, dos vértices se llaman adyacentes si comparten un borde común ( consecutivo si el primero es la cola y el segundo es la cabeza de un borde), en cuyo caso se dice que el borde común une los dos vértices. Una arista y un vértice en esa arista se denominan incidentes .

La gráfica con un solo vértice y sin aristas se llama gráfica trivial . Un gráfico con solo vértices y sin aristas se conoce como grafo sin aristas . El gráfico sin vértices y sin aristas a veces se denomina gráfico nulo o gráfico vacío , pero la terminología no es coherente y no todos los matemáticos permiten este objeto.

Normalmente, los vértices de un gráfico, por su naturaleza como elementos de un conjunto, son distinguibles. Este tipo de gráfico puede llamarse etiquetado con vértice . Sin embargo, para muchas preguntas es mejor tratar los vértices como indistinguibles. (Por supuesto, los vértices aún pueden distinguirse por las propiedades del propio gráfico, por ejemplo, por el número de bordes incidentes). Las mismas observaciones se aplican a los bordes, por lo que los gráficos con bordes etiquetados se denominan bordes etiquetados . Los gráficos con etiquetas adheridas a bordes o vértices generalmente se designan como etiquetados . En consecuencia, los gráficos en los que los vértices son indistinguibles y los bordes no se pueden distinguir se denominan no etiquetados . (En la literatura, el término etiquetado puede aplicarse a otros tipos de etiquetado, además del que solo sirve para distinguir diferentes vértices o aristas).

La categoría de todos los gráficos es la categoría coma Conjunto ↓ D , donde D : Conjunto → Set es el funtor tomar un conjunto s a s × s .

Ejemplos [ editar ]

Un gráfico con seis vértices y siete aristas.
  • El diagrama es una representación esquemática del gráfico con vértices y aristas.
  • En informática , los gráficos dirigidos se utilizan para representar conocimientos (por ejemplo, gráficos conceptuales ), máquinas de estados finitos y muchas otras estructuras discretas.
  • Una relación binaria R en un conjunto X define un gráfico dirigido. Un elemento x de X es un predecesor directo de un elemento y de X si y solo si xRy .
  • Un gráfico dirigido puede modelar redes de información como Twitter , con un usuario siguiendo a otro. [12] [13]
  • Los gráficos de Cayley de grupos generados finitamente, así como los gráficos laterales de Schreier, dan ejemplos particularmente regulares de gráficos dirigidos.
  • En la teoría de categorías , cada categoría pequeña tiene un multigraph dirigido subyacente cuyos vértices son los objetos de la categoría, y cuyos bordes son las flechas de la categoría. En el lenguaje de la teoría de categorías, se dice que hay un functor olvidadizo desde la categoría de categorías pequeñas a la categoría de temblores .

Operaciones gráficas [ editar ]

Hay varias operaciones que producen nuevos gráficos a partir de los iniciales, que pueden clasificarse en las siguientes categorías:

  • operaciones unarias , que crean un nuevo gráfico a partir de uno inicial, como:
    • contracción del borde ,
    • gráfico de líneas ,
    • gráfico dual ,
    • gráfico de complemento ,
    • reescritura de gráficos ;
  • operaciones binarias , que crean un nuevo gráfico a partir de dos iniciales, como:
    • unión disjunta de gráficos ,
    • producto cartesiano de gráficos ,
    • producto tensorial de gráficos ,
    • fuerte producto de gráficos ,
    • producto lexicográfico de gráficos ,
    • Gráficos en serie-paralelos .

Generalizaciones [ editar ]

En un hipergráfico , una arista puede unir más de dos vértices.

Un grafo no dirigido puede verse como un complejo simplicial que consta de 1 simplices (las aristas) y 0-simplices (los vértices). Como tales, los complejos son generalizaciones de gráficos, ya que permiten simplices de dimensiones superiores.

Cada gráfico da lugar a una matroide .

En la teoría de modelos , un gráfico es solo una estructura . Pero en ese caso, no hay limitación en el número de aristas: puede ser cualquier número cardinal , ver gráfico continuo .

En biología computacional , el análisis de gráficos de potencia introduce gráficos de potencia como una representación alternativa de gráficos no dirigidos.

En los sistemas de información geográfica , las redes geométricas se modelan de cerca a partir de gráficos y toman prestados muchos conceptos de la teoría de gráficos para realizar análisis espaciales en redes de carreteras o redes de servicios públicos.

Ver también [ editar ]

  • Gráfico conceptual
  • Gráfico (tipo de datos abstracto)
  • Base de datos de gráficos
  • Dibujo gráfico
  • Lista de temas de teoría de grafos
  • Lista de publicaciones en teoría de grafos
  • Teoría de redes

Notas [ editar ]

  1. a b Trudeau, Richard J. (1993). Introducción a la teoría de grafos (reedición ampliada y corregida. Ed.). Nueva York: Dover Pub. pag. 19. ISBN 978-0-486-67870-2. Consultado el 8 de agosto de 2012 . Un gráfico es un objeto que consta de dos conjuntos llamados su conjunto de vértices y su conjunto de bordes .
  2. ^ Ver:
    • JJ Sylvester (7 de febrero de 1878) "Química y álgebra" , Nature , 17  : 284. doi : 10.1038 / 017284a0 . De la página 284: "Cada invariante y covariante se vuelve así expresable mediante un gráfico exactamente idéntico a un diagrama o químicograma de Kekulé".
    • JJ Sylvester (1878) "Sobre una aplicación de la nueva teoría atómica a la representación gráfica de las invariantes y covariantes de la cuántica binaria, - con tres apéndices", American Journal of Mathematics, Pure and Applied , 1 (1): 64-90 . doi : 10.2307 / 2369436 . JSTOR  2369436 . El término "gráfico" aparece por primera vez en este documento en la página 65.
  3. ^ Bruto, Jonathan L .; Yellen, Jay (2004). Manual de teoría de grafos . Prensa CRC . pag. 35 . ISBN 978-1-58488-090-5.
  4. ^ Bender y Williamson , 2010 , p. 148.
  5. Ver, por ejemplo, Iyanaga y Kawada, 69 J , p. 234 o Biggs, pág. 4.
  6. ^ Bender y Williamson , 2010 , p. 149.
  7. ^ Graham y col., P. 5.
  8. a b Bender y Williamson , 2010 , p. 161.
  9. ^ Strang, Gilbert (2005), Álgebra lineal y sus aplicaciones (4a ed.), Brooks Cole, ISBN 978-0-03-010567-8
  10. ^ Lewis, John (2013), Estructuras de software Java (4ª ed.), Pearson, p. 405, ISBN 978-0133250121
  11. ^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Fundamentos de las matemáticas discretas (Ed. Para estudiantes internacionales). Boston: Pub PWS-KENT. Co. p. 463. ISBN 978-0-53492-373-0. Un gráfico ponderado es un gráfico en el que se asigna un número w (e) , llamado su peso , a cada borde e .
  12. Grandjean, Martin (2016). "Un análisis de redes sociales de Twitter: mapeo de la comunidad de humanidades digitales" . Artes y humanidades convincentes . 3 (1): 1171458. doi : 10.1080 / 23311983.2016.1171458 .
  13. ^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang y Reza Bosagh Zadeh WTF: El sistema a quién seguir en Twitter , Actas de la 22ª conferencia internacional en World Wide Web . doi : 10.1145 / 2488388.2488433 .

Referencias [ editar ]

  • Balakrishnan, VK (1997). Teoría de grafos (1ª ed.). McGraw-Hill. ISBN 978-0-07-005489-9.
  • Bang-Jensen, J .; Gutin, G. (2000). Dígrafos: teoría, algoritmos y aplicaciones . Saltador.
  • Bender, Edward A .; Williamson, S. Gill (2010). Listas, Decisiones y Gráficos. Con una introducción a la probabilidad .
  • Berge, Claude (1958). Théorie des graphes et ses applications (en francés). París: Dunod.
  • Biggs, Norman (1993). Teoría de grafos algebraicos (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 978-0-521-45897-9.
  • Bollobás, Béla (2002). Teoría moderna de gráficos (1ª ed.). Saltador. ISBN 978-0-387-98488-9.
  • Diestel, Reinhard (2005). Teoría de grafos (3ª ed.). Berlín, Nueva York: Springer-Verlag. ISBN 978-3-540-26183-4.
  • Graham, RL; Grötschel, M .; Lovász, L. (1995). Manual de combinatoria . MIT Press. ISBN 978-0-262-07169-7.
  • Gross, Jonathan L .; Yellen, Jay (1998). Teoría de grafos y sus aplicaciones . Prensa CRC. ISBN 978-0-8493-3982-0.
  • Gross, Jonathan L .; Yellen, Jay (2003). Manual de teoría de grafos . CRC. ISBN 978-1-58488-090-5.
  • Harary, Frank (1995). Teoría de grafos . Addison Wesley Publishing Company. ISBN 978-0-201-41033-4.
  • Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Diccionario enciclopédico de matemáticas . MIT Press. ISBN 978-0-262-09016-2.
  • Zwillinger, Daniel (2002). Tablas y fórmulas matemáticas estándar de CRC (31ª ed.). Chapman y Hall / CRC. ISBN 978-1-58488-291-6.

Lectura adicional [ editar ]

  • Trudeau, Richard J. (1993). Introducción a la teoría de grafos (reedición ampliada y corregida. Ed.). Nueva York: Publicaciones de Dover . ISBN 978-0-486-67870-2. Consultado el 8 de agosto de 2012 .

Enlaces externos [ editar ]

  • Medios relacionados con Graph (matemáticas discretas) en Wikimedia Commons
  • Weisstein, Eric W. "Gráfico" . MathWorld .