Gráfico (matemáticas)

Un gráfico es una abstracción matemática de un sistema real de cualquier naturaleza, cuyos objetos tienen conexiones por pares. Un gráfico como objeto matemático es una colección de dos conjuntos: el conjunto de objetos en sí, llamado conjunto de vértices , y el conjunto de sus conexiones por pares, llamado conjunto de aristas. Un elemento de un conjunto de aristas es un par de elementos de un conjunto de vértices.

Los gráficos se utilizan ampliamente en la ciencia y la tecnología modernas. Se utilizan tanto en las ciencias naturales (física y química) como en las ciencias sociales (por ejemplo, sociología), pero el uso de gráficos ha recibido la mayor escala en informática y tecnologías de red.

Como el ejemplo más simple de la vida, podemos dar un diagrama de vuelo de cierta aerolínea, que está modelado por un gráfico, donde los vértices del gráfico son ciudades y los bordes son vuelos que conectan pares de ciudades. Un árbol de directorios en una computadora también es un gráfico: unidades, carpetas y archivos son vértices, y los bordes muestran el anidamiento de archivos y carpetas en carpetas y unidades [1] . La estructura de Wikipedia está modelada por un gráfico dirigido , en el que los artículos son los vértices del gráfico y los hipervínculos son arcos ( mapa temático ).

Los grafos son el principal objeto de estudio de la teoría de grafos .

Definiciones

Los sistemas de la naturaleza real modelados por grafos son muy diversos, por lo que existen distintos tipos de grafos. La abstracción más simple de sistemas con elementos que tienen conexiones por pares es un gráfico simple .

Gráfico simple

Definición. Un gráfico simple es una colección de dos conjuntos: un conjunto no vacío y un conjunto de pares desordenados de diferentes elementos del conjunto . Un conjunto se llama conjunto de vértices , un conjunto se llama conjunto de aristas $G(V,E)$ $V$ $mi$ $V$ $V$ $mi$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\ derecha\}\notin E,\quad v\in V

es decir, el conjunto consta de subconjuntos de 2 elementos del conjunto . $mi$ $V$

Términos relacionados

La teoría de grafos no tiene una terminología bien establecida. Por lo tanto, algunas publicaciones pueden utilizar términos distintos a los que se enumeran a continuación.

Un vértice (nodo, punto) ( eng. vértice, nodo, punto ) de un gráfico es un elemento de un conjunto de vértices ; $GRAMO$ ${\ Displaystyle v \ en V (G)}$

Una arista (línea) ( inglés edge, line ) de un gráfico es un elemento del conjunto de aristas , o , donde ; $GRAMO$ ${\ estilo de visualización e \ en E (G)}$ $e=\izquierda\{v_{1},v_{2}\derecha\}$ $v_{1}\en V(G),\quad v_{2}\en V(G)$

Los elementos de un gráfico son sus vértices y aristas del gráfico; $GRAMO$ ${\ Displaystyle v \ en V (G)}$ ${\ estilo de visualización e \ en E (G)}$

El orden ( order en inglés ) de un gráfico es el número cardinal del conjunto de vértices , o, en otras palabras, el número de vértices; $GRAMO$ $n=|V(G)|$

El tamaño ( tamaño inglés ) del gráfico es el número cardinal del conjunto de aristas o, en otras palabras, el número de aristas; $GRAMO$ $m=|E(G)|$

Un vértice es incidente a una arista si ; entonces también dicen que hay un borde en ; $v$ $mi$ ${\ estilo de visualización v \ en e}$ $mi$ $v$

Los vértices finales (finales) ( ing. endvertices, extremos ) son dos vértices incidentes en un borde. El borde conecta ( inglés une ) sus vértices extremos;

Los vértices vecinos (adyacentes) ( inglés vecinos, adyacentes ) son tales vértices y eso o, en otras palabras, ambos vértices son terminales para un borde; $v_{1}$ $v_{2}$ ${\ estilo de visualización \ izquierda \ {v_ {1}, v_ {2} \ derecha \} \ en E (G)}$

Las aristas adyacentes ( inglés aristas adyacentes ) son aristas incidentes a un vértice o y -adyacentes; $e_{1}=\izquierda\{v,v_{1}\derecha\}$ $e_{2}=\izquierda\{v,v_{2}\derecha\}$

El grado (valencia) de un vértice ( ing. grado, valencia ) es el número de aristas que le inciden. El grado de un vértice se denota como ; ${\ estilo de visualización d (v)}$

Un vértice aislado ( ing. isolated ) es un vértice con grado , es decir, no es el final de ninguna arista; ${\ estilo de visualización d (v) = 0}$

Un vértice colgante (hoja) ( ing. hoja ) es un vértice con un grado , es decir, que es el final de exactamente un borde. $d(v)=1$

Por lo general, un gráfico se representa como un diagrama : vértices - puntos, bordes - líneas.

Pseudógrafo

Un seudógrafo es una colección de dos conjuntos: un conjunto no vacío y un conjunto de pares desordenados de elementos del conjunto . $G(V,E)$ $V$ $mi$ $V$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V

El elemento está permitido en el conjunto de aristas del seudógrafo . ${\ estilo de visualización \ izquierda \ {v, v \ derecha \} \ en E (G)}$

Un bucle es un elemento que es una arista cuyos vértices finales coinciden. $e=\izquierda\{v,v\derecha\}$

En otras palabras, si los elementos del conjunto E pueden ser bucles, entonces el gráfico se llama seudógrafo [2] .

Multigrafo

Un multigrafo es una colección de dos conjuntos: un conjunto no vacío y un conjunto múltiple de pares desordenados de diferentes elementos del conjunto . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V\quad \left\{v,v\right\}\notin \mathbf {E} ,\quad v\in V

Las aristas múltiples son elementos idénticos del conjunto múltiple , es decir, aristas cuyos vértices finales coinciden. $\left\{e,e,\dots ,e\right\}\in \mathbf {E}$

En otras palabras, si no es un conjunto, sino una familia, es decir, si contiene los mismos elementos, entonces tales elementos se denominan aristas múltiples, y el gráfico se denomina multigrafo [2] . $mi$ $\mathbf {E}$

Pseudomultigrafo

Un pseudomultigrafo es una colección de dos conjuntos: un conjunto no vacío y un conjunto múltiple de pares desordenados de elementos del conjunto . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V

En otras palabras, si una familia contiene los mismos elementos (múltiples aristas) y puede contener bucles, entonces el gráfico se denomina pseudomultigrafo [2] . $\mathbf {E}$ $\mathbf {E}$

Gráfico dirigido

El gráfico dirigido (dígrafo) ( eng. gráfico dirigido o dirgaph ) es un conjunto de dos conjuntos: un conjunto no vacío y un conjunto de arcos o pares ordenados de diferentes elementos del conjunto $G(V,E)$ $V$ $mi$ $V$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_{2}\ derecha\},\prec\derecha\rangle\en E,\quad v\en V

junto con dos pantallas

init:E\rightarrow V,\quad ter:E\rightarrow V

donde el mapeo asigna a cada arco su vértice inicial (el comienzo del arco) , y el mapeo asigna a cada arco su vértice final (el final del arco) . Dicen que el arco va de a $init:E\rightarrow V$ $inicializar(e)$ $ter:E\rightarrow V$ $ter(e)$ $mi$ $inicializar(e)$ $ter(e)$

Gráfico mixto

Un grafo mixto es una colección de tres conjuntos: un conjunto de vértices no vacío y un conjunto de arcos o pares ordenados de diferentes elementos del conjunto y un conjunto de aristas de pares desordenados de diferentes elementos del conjunto . ${\ Displaystyle G (V, E, U)}$ $V$ $mi$ $V$ $tu$ $V$

G(V,E,U)=\left\langle V,E,U\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_ {2}\right\},\prec \right\rangle \in E,\quad \left\{v_{3},v_{4}\right\}\in U,\quad v\in V

junto con dos pantallas

init:E\rightarrow V,\quad ter:E\rightarrow V

Los grafos dirigidos y no dirigidos son casos especiales de grafos mixtos.

Gráficos isomorfos

Un grafo se llama isomorfo a un grafo si existe una biyección del conjunto de vértices del grafo al conjunto de vértices del grafo , que tiene la siguiente propiedad: si el grafo tiene una arista de vértice a vértice , entonces el grafo debe tener una arista de vértice a vértice y viceversa; si el gráfico tiene una arista de vértice a vértice , entonces el gráfico debe tener una arista de vértice a vértice . En el caso de un grafo dirigido , esta biyección también debe conservar la orientación de la arista. En el caso de un gráfico ponderado, la biyección también debe conservar el peso de la arista. $GRAMO$ $H$ $F$ $GRAMO$ $H$ $GRAMO$ $A$ $B$ $H$ $fa)$ $pensión completa)$ $H$ $A$ $B$ $GRAMO$ $f^{-1}(A)$ $f^{-1}(B)$

Otras definiciones relacionadas

Una ruta en un gráfico es una secuencia finita de vértices en la que cada vértice (excepto el último) está conectado al siguiente vértice de la secuencia por una arista. Una cadena es una ruta sin bordes repetidos. Un camino simple es un camino sin vértices repetidos (lo que significa que no hay bordes repetidos en un camino simple).

Una ruta orientada (o camino ) en un dígrafo es una secuencia finita de vértices y arcos en los que cada elemento es incidente con el anterior y el siguiente.

Un ciclo es una cadena en la que coinciden el primer y el último vértice. En este caso , la longitud del camino (o ciclo) es el número de sus aristas constituyentes . Tenga en cuenta que si los vértices y son los extremos de algún borde, entonces de acuerdo con esta definición, la secuencia es un ciclo. Para evitar tales casos "degenerados", se introducen las siguientes nociones. $tu$ $v$ $(u, v, u)$

Un camino (o ciclo) se llama simple si los bordes en él no se repiten; elemental si es simple y los vértices en él no se repiten (a excepción del inicial y final en el caso de un ciclo).

Las propiedades más simples de caminos y ciclos:

cada camino que conecta dos vértices contiene un camino elemental que conecta los mismos dos vértices;
todo camino simple no elemental contiene un ciclo elemental ;
todo ciclo simple que pasa por algún vértice (o arista) contiene un (sub)ciclo elemental que pasa por el mismo vértice (o arista);
un bucle es un ciclo elemental.

Una relación binaria en el conjunto de vértices de un grafo, dada como "hay un camino de a ", es una relación de equivalencia y, por lo tanto, divide este conjunto en clases de equivalencia, llamadas componentes conexas del grafo. Si un gráfico tiene exactamente un componente conexo, entonces el gráfico es conexo. Sobre la componente conexa, podemos introducir el concepto de distancia entre vértices como la longitud mínima de un camino que conecta estos vértices. $tu$ $v$

Cualquier subgrafo conexo máximo de un gráfico se denomina componente conexo (o simplemente componente) del gráfico . La palabra "máximo" significa máximo con respecto a la inclusión, es decir, no contenido en un subgrafo conexo con una gran cantidad de elementos. $GRAMO$ $GRAMO$

Un borde en un gráfico se llama puente si su eliminación aumenta el número de componentes.

Características adicionales de los gráficos

La gráfica se llama:

conectado si para cualquiera delos vérticeshay un camino dea. $tu$ $v$ $tu$ $v$
fuertemente conexo o direccionalmente conexo si está orientado y hay un camino orientado desde cualquier vértice a cualquier otro.
un árbol si es conexo y no contiene ciclos no triviales.
completa si cualquiera de sus dos (diferentes, si no se permiten bucles) vértices están conectados por una arista.
bipartito si sus vértices se pueden dividir en dos subconjuntos que no se intersecanymodo que cualquier borde conecta un vértice decon un vértice de. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-parcial si sus vértices se pueden dividir en subconjuntos que no se intersecan , , …, de modo que no haya aristas que conecten los vértices del mismo subconjunto. $k$ $V_{1}$ $V_{2}$ $V_{k}$
bipartito completo , si cada vértice de un subconjunto está conectado por una arista a cada vértice de otro subconjunto.
planar , si el gráfico se puede representar mediante un diagrama en un plano sin bordes cruzados.
ponderado si a cada borde del gráfico se le asigna un cierto número, llamado el peso del borde.
cordal si el gráfico no contiene ciclos inducidos de longitud superior a tres.

También sucede:

Generalización del concepto de grafo

Un gráfico simple es un complejo simplicial unidimensional .

De manera más abstracta, un grafo se puede definir como un triple , donde y son unos conjuntos ( de vértices y aristas , respectivamente), y es una función de incidencia (o incidenter ) que asigna a cada arista (ordenada o desordenada) un par de vértices y de (sus extremos ). Casos particulares de este concepto son: $(V,E,\varphi)$ $V$ $mi$ $\varphi$ $e\en E$ $tu$ $v$ $V$

Gráficos de Euler : un gráfico en el que hay un camino de Euler cíclico ( ciclo de Euler );

Formas de representar un gráfico en informática

Matriz de adyacencia

Una tabla donde tanto las columnas como las filas corresponden a los vértices del gráfico. En cada celda de esta matriz, se escribe un número que determina la presencia de una conexión desde la fila superior a la columna superior (o viceversa).

Esta es la forma más conveniente de representar gráficos densos.

La desventaja son los requisitos de memoria, que son directamente proporcionales al cuadrado del número de vértices.

matriz bidimensional;
Matriz con huecos;
Configuración implícita (usando una función).

Matriz de incidencia

Una tabla donde las filas corresponden a los vértices del gráfico y las columnas corresponden a los enlaces (bordes) del gráfico. En una celda de matriz en la intersección de una fila con una columna , se escribe lo siguiente: $i$ $j$

una en caso de que la conexión "salga" de la parte superior ,

j

i

-1, si la conexión "entra" en el vértice, 0 en todos los demás casos (es decir, si la conexión es un bucle o la conexión no es incidente en el vértice)

Este método es bastante amplio (el tamaño es proporcional a ) para el almacenamiento, por lo que se usa muy raramente, en casos especiales (por ejemplo, para encontrar rápidamente ciclos en un gráfico). $|V||E|$

Lista de adyacencias

Una lista donde cada vértice del gráfico corresponde a una cadena que almacena una lista de vértices adyacentes. Tal estructura de datos no es una tabla en el sentido habitual, sino una "lista de listas".

Tamaño de la memoria: . $O(|V|+|E|)$

Esta es la forma más conveniente de representar gráficos dispersos, así como al implementar algoritmos básicos de recorrido de gráficos en amplitud o profundidad, donde necesita obtener rápidamente los "vecinos" del vértice que se ve actualmente.

Lista de aristas

Una lista donde cada borde del gráfico corresponde a una cadena que almacena dos vértices incidentes en el borde.

Tamaño de la memoria: . $O(|E|)$

Esta es la forma más compacta de representar gráficos, por lo que a menudo se usa para almacenamiento externo o intercambio de datos.

Lenguajes de descripción y programas gráficos

Idiomas de descripción

Para describir gráficos que sean adecuados para el procesamiento de máquinas y al mismo tiempo convenientes para la percepción humana, se utilizan varios lenguajes estandarizados, que incluyen:

PUNTO
GraphML
Formato de gráfico trivial
GML
GXL
XGMML
DGML

Programas de construcción

Se ha desarrollado una serie de programas comerciales para la construcción de gráficos, por ejemplo, la construcción de gráficos es la base de los paquetes de software de aplicación ILOG (desde 2009 propiedad de IBM Corporation ), entre otros programas: GoView, Lassalle AddFlow, LEDA (hay una edición gratuita ).

También hay un programa gráfico gratuito igraph y una biblioteca gratuita llamada Boost .

Programas de visualización

Las siguientes herramientas de software se utilizan para visualizar gráficos :

Graphviz ( Licencia pública de Eclipse )
Visualizador gráfico LION.
El analizador de gráficos es un programa en ruso con una interfaz de usuario simple ( GNU LGPL ; solo Windows).
Gephi es un marco gráfico para representar y estudiar gráficos ( GNU GPL , CDDL ).
La biblioteca GraphX es una biblioteca .NET gratuita para calcular y dibujar gráficos, usando WPF 4.0 .
La biblioteca MSAGL es una biblioteca gratuita para .NET [3] .

Véase también

Notas

↑ Burkatovskaya, 2014 , pág. 3.
↑ 1 2 3 Burkatovskaya, 2014 , pág. 6.
↑ Diseño gráfico automático de Microsoft - Investigación de Microsoft . investigación.microsoft.com. Consultado el 15 de noviembre de 2015. Archivado desde el original el 14 de mayo de 2012. (indefinido)

Literatura

Burkatovskaya Yu. B. Teoría de grafos. - Tomsk: Editorial de la Universidad Politécnica de Tomsk, 2014. - T. 1. - 200 p.
Distel R. Teoría de grafos. - Novosibirsk: Editorial del Instituto de Matemáticas. S. L. Sobolev SO RAN, 2002. - 336 p. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Conferencias sobre teoría de grafos. M.: Nauka, 1990. 384 págs. (Ed. 2, rev. M.: URSS, 2009. 392 p.)
Kasyanov V. N., Evstigneev V. A. Grafos en programación: procesamiento, visualización y aplicación. - San Petersburgo. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov MN Gráficos en Maple. — M. : Fizmatlit, 2007. — 168 p. - ISBN 978-5-9221-0745-7 .
Kormen T. M. et al. Parte VI. Algoritmos para trabajar con grafos // Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2ª ed. - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Mineral O. Teoría de grafos. — M .: Nauka, 1968. — 336 p.
Gráficos // Diccionario enciclopédico de un joven matemático / Comp. A. P. Savin. - M .: Pedagogía , 1985. - S. 86 -88. — 352 págs.
Salii VN, Bogomolov AM Fundamentos algebraicos de la teoría de sistemas discretos. - M .: Literatura física y matemática, 1997. - ISBN 5-02-015033-9 .
Wilson R. Introducción a la teoría de grafos. — M .: Mir, 1977. — 208 p.
Harari F. Teoría de grafos. — M .: Mir, 1973.