¿Qué son los gráficos en términos simples?

18

¿Qué son los gráficos, en informática, y para qué se utilizan? En términos laicos preferiblemente.

He leído la definición en Wikipedia :

En informática, un gráfico es un tipo de datos abstractos destinado a implementar los conceptos de gráfico e hipergrafía de las matemáticas.

Una estructura de datos gráficos consta de un conjunto finito (y posiblemente mutable) de pares ordenados, llamados aristas o arcos, de ciertas entidades llamadas nodos o vértices. Como en matemáticas, se dice que una arista (x, y) apunta o va de x a y. Los nodos pueden ser parte de la estructura del gráfico, o pueden ser entidades externas representadas por índices enteros o referencias.

pero estoy buscando una definición menos formal, más fácil de entender.

CondiciónRacer
fuente
¿Te refieres a gráficos de la estructura de datos?
Sistema
1
Si, lo siento. Gráficos como se describe aquí en.wikipedia.org/wiki/Graph_(abstract_data_type) , solo que estoy buscando una definición menos formal y más fácil de entender.
ConditionRacer
@ Justin984 Los enlaces de Wikipedia con paréntesis (y hay tantos) no funcionan, los paréntesis no funcionan bien con el formato Markdown para enlaces. Ahora, para referencia futura, agregue cualquier aclaración a su pregunta en la pregunta misma, no en los comentarios, no son tan visibles y es fácil pasarlos por alto.
Editaré
@ Justin984 También tenga en cuenta que Computer Science Stack Exchange podría ser un poco más apropiado para preguntas como esta que los Programadores. No me malinterpreten, la pregunta está perfectamente en el tema aquí, y obtuvo excelentes respuestas, pero no estaría de más si revisara una comunidad que esté un poco más centrada en los conceptos básicos de informática que nosotros (no Sin embargo, si publica la misma pregunta en varios sitios, si la publica en el sitio incorrecto, podemos moverla al correcto automáticamente).
Yannis

Respuestas:

26

Un ejemplo laico perfecto podría ser Facebook . Su red, sus amigos y sus amigos, etc., se conocen colectivamente como el gráfico social .

En este "gráfico", las personas se consideran nodos del gráfico y los bordes son enlaces de amistad .

En Facebook, el amigo es una relación bidireccional (A es el amigo de B => B es el amigo de A), por lo que el gráfico es un gráfico no dirigido . Una red como Google+ o Twitter se consideraría un Gráfico Dirigido ya que la dirección de la relación tiene significado aquí.

Todos estos gráficos se denominan gráficos cíclicos , ya que las relaciones entre los nodos pueden formar ciclos. Un árbol genealógico , por otro lado, es un tipo especial de gráfico que, entre otras cosas, es acíclico ya que no puede haber ciclos en la relación del árbol genealógico. (Técnicamente se llama Gráfico Acíclico Dirigido (DAG) ya que es dirigido y acíclico)

Esto debería cubrir toda la jerga básica que involucra gráficos, por lo que ahora debería poder seguir el resto del material en el campo.

Karthik T
fuente
1
No puedo creer que no se me haya ocurrido que se llama la API gráfica de Facebook. ¡Buen ejemplo!
ConditionRacer
44
¿Árbol genealógico no cíclico? No debería ser, pero desafortunadamente es ...
Marjan Venema
1
@MarjanVenema, ¿ el árbol genealógico es cíclico ? (Es un grafo dirigido, por lo que la dirección es importante en la determinación de los ciclos, y presumiblemente relaciones de paso no cuentan realmente.)
huon
@dbaupp: No deseo entrar en detalles aquí, así que solo mencionaré una palabra: incesto.
Marjan Venema
55
@ MarjanVenema, te estás perdiendo mi punto. Un ciclo en un gráfico dirigido es un patrón como A -> B -> C -> A(es decir, un círculo de flechas), el incesto solo da A -> B -> Cy A -> D -> C(es decir, un diamante). Un ciclo en un árbol genealógico necesita viajar en el tiempo.
Huon
16

Los gráficos son uno de los conceptos matemáticos más importantes utilizados en informática.

Has visto gráficos muchas veces. Imagine que está tomando un vuelo en avión de una ciudad a otra. Inevitablemente, encontrará una bonita revista brillante de la aerolínea en el bolsillo del asiento frente a usted. Cerca de la parte posterior de esa revista, casi siempre puede encontrar un mapa que representa las ciudades atendidas por esa aerolínea representadas como círculos, con los vuelos que conectan esas ciudades representadas como líneas curvas. Eso es un gráfico! Las ciudades, representadas como círculos, son los nodos de este gráfico y los vuelos, representados como líneas curvas, son los bordes. Los gráficos son simplemente cosas con nodos y aristas que conectan los nodos.

Puede embellecer esos gráficos simples de varias maneras. No desea ver solo un montón de círculos y líneas cuando mira ese mapa. Esas ciudades tienen nombres. Etiquetar esas ciudades da como resultado un gráfico etiquetado. (También puede etiquetar los bordes, por ejemplo, el vuelo 1234.) La informática a menudo asocia datos con los nodos, a veces con los bordes, pero eso es solo una extensión de la etiqueta. Todavía es un gráfico etiquetado. Otro adorno resulta si puede volar directamente de la ciudad A a la ciudad B, pero no de la ciudad B a la ciudad A. Una forma obvia de retratar esto es colocar una flecha en la línea que conecta las ciudades para representar esta relación unidireccional. Ahora tienes un gráfico dirigido.

Las listas enlazadas, los árboles, los diagramas de transición de estado y muchas otras estructuras de datos informáticos son ejemplos de gráficos. Es un concepto muy poderoso.

David Hammen
fuente
En realidad, extendería ese ejemplo para tener en cuenta que todas las entidades descritas en su ejemplo podrían representarse como vértices en un gráfico (ciudad, plano, revista, mapa, etc.), siendo el mapa en sí un solo vértice.
Demian Brecht el
14

Una mejor pregunta sería "¿Para qué no se utilizan los gráficos?". La informática es, en muchos aspectos, el estudio de los gráficos.

Un gráfico, en términos simples, es una colección de objetos abstractos arbitrarios llamados "nodos" o "vértices" que representan puntos de conexión. Luego se conectan a través de "caminos" o "bordes". El tipo de datos abstracto "Graph" es una implementación del matemático "Graph". Entonces, básicamente, tiene nodos y bordes como sus campos y varias operaciones que puede realizar en ellos. Puede, por ejemplo, agregar un nuevo nodo a la colección del gráfico (esto podría ser una lista o una matriz o alguna otra estructura dependiendo del idioma). Entonces podría vincular ese nodo a los nodos existentes. Las operaciones también incluirían atravesar el gráfico, verificar si dos nodos comparten un borde (están conectados), recuperar valores de nodos o bordes y la eliminación de nodos o bordes del gráfico.

En cuanto a la utilización, los gráficos se utilizan en todo el lugar. Las redes las utilizan especialmente, pero se encuentran en Inteligencia Artificial, Minería de Datos, Desarrollo de Juegos, Geoinformática y una gran cantidad de otras disciplinas. En informática formal, ven aún más uso, es decir, como una forma de representar el estado.

Efectivamente, cualquier cosa que pueda representar como un conjunto de conexiones puede representarse como un gráfico e implementarse a través de ese ADT de alguna forma.

Aquí hay un gráfico de ejemplo que hice:

Ejemplo de gráfico

Ingeniero mundial
fuente
3

Un gráfico es solo una colección de objetos conectados entre sí por líneas llamadas vértices.

El término "gráfico" es una abstracción y generalización de muchas estructuras de datos utilizadas en el desarrollo de software. Las listas enlazadas, los árboles binarios y los AST son todos gráficos.

Básicamente, cualquier colección de objetos que tiene punteros que asocian los objetos entre sí es un gráfico. Una vez que tenga un gráfico, puede aplicarle los principios de la teoría de gráficos para resolver ciertos problemas .

Robert Harvey
fuente