Tutorial de estructura de datos de gráficos
Un nodo en un gráfico se llama vértice (plural - vértices). A veces todavía se llama nodo; También se puede llamar un punto. Un enlace en un gráfico se llama borde. A veces todavía se llama un enlace; También se puede llamar una línea.
Gráfico con muchas características
Esta figura muestra un gráfico con muchas características:
Los círculos (discos) son vértices. Cualquier línea recta o línea o bucle curvado es un borde.
Características del gráfico
Vértice
Un vértice es un objeto. Puede ser una casa; Puede ser una persona; Puede ser un sustantivo abstracto; puede ser cualquier objeto que se te ocurra.
Borde
Un borde es una conexión (relación) entre dos vértices; La conexión puede ser abstracta.
Bucle
Un bucle es un borde que se conecta un vértice a sí mismo.
Flecha
Considere a dos personas: John y Peter. Si John le da a Peter $ 100, y si John y Peter son vértices, entonces el borde de préstamo apuntará hacia Peter. Si ambos socios olvidan que Peter le debe a John, y Peter le da a John $ 100, entonces en el otro extremo del mismo borde, una punta de flecha apuntará hacia John. Si Peter prestara pero $ 75 a John y no $ 100, entonces una ventaja diferente conectaría a Peter con John. Este segundo borde tendrá su punta de flecha apuntando hacia John. En el segundo caso, hay dos bordes, con una punta de flecha cada una, apuntando en direcciones opuestas.
El vértice al que apunta un borde es un vértice de la cabeza para ese borde. El vértice del que se va un borde es un vértice de cola.
Incidente
Un borde conecta dos vértices. Se dice que el borde es incidente en cualquier vértice. El borde no necesita tener una punta de flecha. Los dos vértices se conocen como los puntos finales del borde. Es posible tener un gráfico donde un vértice no pertenezca a ningún borde, pero eso no se considerará en este tutorial.
Gráfico no dirigido
Un borde puede ser una flecha, o no puede. Un gráfico donde no hay borde es una flecha es un gráfico no dirigido. Un borde puede representarse mediante una línea recta o una curva o un bucle.
Gráfico dirigido
Un gráfico donde cada borde es una flecha (dirección) es un gráfico dirigido. Un borde de flecha se puede representar mediante una línea recta con una punta de flecha o una curva con una punta de flecha o un bucle con una punta de flecha.
La ausencia de una dirección en el borde de un gráfico no dirigido, significa que cada borde del gráfico no dirigido es bidireccional.
Grado de vértice
El número de bordes que son incidentes en un vértice es el grado del vértice. Un bucle tiene dos incidentes en un vértice, por lo que un bucle se cuenta dos veces.
Pedido de un gráfico
El orden de un gráfico es el número de vértices en el gráfico.
Multigraph
Un multigraph es un gráfico, donde para algunos pares de vértices, hay más de un bordes. Un multigraph no dirigido es un gráfico en el que los bordes no tienen direcciones (no son flechas). Un multigraph dirigido es uno en el que cada borde es una flecha, y para pares de vértices que tienen más de una flecha, un vértice es la cola de esas flechas y el otro vértice es la cabeza de las mismas flechas. El siguiente diagrama muestra un multigraph no dirigido:
Más de un bordes (yo.mi. múltiples bordes) para un par de vértices también se llaman bordes paralelos.
Carcaj
Un carcaj es un multigraph que permite bucles (uno o más bucles). Algunos multigraphs no permiten bucles.
Gráfico simple
Un gráfico simple es un gráfico donde no hay dos pares de vértices tienen múltiples bordes. Los bucles no están permitidos en un gráfico simple.
Gráfico vacío
Un gráfico vacío es un gráfico sin vértices y, por lo tanto, sin bordes.
Gráfico mixto
Un gráfico mixto es un gráfico donde algunos bordes son flechas, y otros no lo son; En otras palabras: algunos bordes tienen direcciones, y otros no están dirigidos.
Gráfico pesado
Es posible tener un gráfico en el que se asigne un número, conocido como peso, a cada borde. Algunos bordes tienen el mismo número, pero los números son generalmente diferentes. Tal gráfico se llama gráfico ponderado. Los números para un gráfico en particular pueden representar longitudes o costos (precios) o magnitud de algún tipo, dependiendo del problema.
Indegree y Outnegree
El vocabulario, el Indegree y OutdeGree son aplicables solo a un gráfico dirigido. El gráfico puede o no ser un multigraph. El gráfico puede o no tener bucles.
El número de puntas de flecha conectadas a un vértice es el degradamiento de ese vértice. Una flecha con una sola punta de flecha tiene un extremo de la cabeza y un extremo de la cola. El número de colas conectadas a un vértice es el exterior de ese vértice.
Nota: Un gráfico con múltiples bordes para el par de vértices, donde los bordes múltiples están en direcciones opuestas, no se aborda en este tutorial.
Representación de software de un gráfico
Un gráfico puede representarse en el software de la forma en que se dibuja en el diagrama. Un gráfico también se puede representar en software por una matriz matemática (matriz bidimensional). Una de esas matrices se llama matriz de adyacencia.
Matriz de adyacencia
Una matriz de adyacencia es una matriz cuadrada. Los encabezados para las filas son todos los vértices, escritos en orden ascendente. Los encabezados para las columnas siguen siendo los mismos vértices, escritos en orden ascendente. El conteo de las filas o columnas de una matriz comienza desde 1 y no cero como con matrices. Al identificar un elemento en una matriz, el número de fila se escribe primero antes del número de columna.
Para un gráfico no dirigido, cada entrada (elemento) en la matriz de adyacencia es el número de bordes que conectan los dos vértices correspondientes. Se debe contar un bucle dos veces. Para un gráfico dirigido, cada entrada en la matriz de adyacencia es el número de bordes que dejan un vértice de fila e ingresan el vértice de la columna correspondiente o es el número de bordes que dejan una columna vértice e ingresan el vértice de fila correspondiente. La elección es la del programador. En esta situación (cualquier caso), aún se debe contar una bucle una vez.
Nota: Un gráfico es un diagrama es una estructura de datos por derecho propio. Una matriz de adyacencia también es una estructura de datos por derecho propio.
Gráfico no dirigido y matriz de adyacencia
Los siguientes diagramas muestran un gráfico no dirigido y la matriz de adyacencia correspondiente:
La diagonal principal de una matriz es la diagonal desde la parte superior izquierda hasta la parte inferior derecha. Una matriz no dirigida es simétrica sobre la diagonal principal. La entrada de matriz para la fila A y la columna C es 1, lo que significa que hay un borde que conecta el vértice A y el vértice C. La entrada de matriz para la fila C y la columna B es 3, lo que significa que hay 3 bordes que conectan el vértice C y el vértice B. Las otras entradas se explican de manera similar.
La suma de las entradas para una fila da el número de bordes (grado) para el vértice correspondiente. La suma de las entradas para la fila A es 2, lo que significa que 2 bordes están conectados al vértice A. La suma de las entradas para la fila B es 6, lo que significa que 6 bordes están conectados al vértice B. El resto de las entradas se explican de manera similar.
Gráfico dirigido y matriz de adyacencia
Los siguientes diagramas muestran un gráfico dirigido y la matriz de adyacencia correspondiente:
La matriz de adyacencia para un gráfico dirigido no es necesariamente simétrico sobre la diagonal principal. La entrada de la matriz para la fila A y la columna C es 1, lo que significa que un borde sale del vértice a al vértice C. La entrada de la matriz para la fila C y la columna B es 3, lo que significa que 3 bordes salen del vértice C al vértice B. Las otras entradas se explican de manera similar.
La suma de las entradas para una columna da el Indegree para el vértice (columna). La suma de las entradas para una fila da el exterior para el vértice (fila). La suma de las entradas para la columna A es 1, lo que significa que un borde se dirige a Vértice A. La suma de las entradas para la fila B es 2, lo que significa que 2 bordes salen del vértice B. El resto de las entradas se explican de manera similar.
Operaciones de gráficos
Una estructura de datos, como un gráfico, consta de un conjunto de valores de datos o un conjunto de objetos, más la relación entre los objetos, más las operaciones (funciones) entre los objetos. Las relaciones en un gráfico están indicadas por los bordes. En eso, un gráfico debe tener al menos las siguientes operaciones:
Adyacente (G, X, Y)
G significa gráfico. Esta operación verifica si un borde conecta el vértice x y el vértice y. El valor y la posición de una entrada en una matriz indican la conexión de un borde (y su tipo).
Vecinos (G, X)
Esta operación devuelve una lista de todos los vértices que están directamente conectados al vértice X. El valor y la posición de una entrada en una matriz indican la conexión de un borde.
remove_vertex (g, x)
Esta operación elimina un vértice, x de un gráfico. Si el vértice no tenía borde, no hay problema. Sin embargo, si el vértice tenía enlaces, entonces los enlaces (bordes) también deben eliminarse. El valor y la posición de una entrada en una matriz indican la presencia de un vértice en particular. Si se elimina un vértice, la matriz debe reajustarse.
add_vertex (g, x)
Esto agrega un vértice, x sin agregar bordes o reemplaza un vértice que tenía bordes pero que se había eliminado. El valor y la posición de una entrada en una matriz indican la presencia de un vértice en particular. Si se agrega un vértice, la matriz debe reajustarse.
add_edge (g, x, y)
Esta operación agrega un nuevo borde entre el vértice x y el vértice y si el borde no estaba allí. El valor y la posición de una entrada en una matriz indican la presencia de un borde particular. Si se agrega un borde, la matriz debe reajustarse.
remove_edge (g, x, y)
Esta operación eliminaría el borde entre el vértice x y el vértice y si el borde estuviera allí. El valor y la posición de una entrada en una matriz indican la presencia de un borde particular. Si se elimina un borde, la matriz debe reajustarse.
get_vertex_value (g, x)
Esta operación devuelve el valor, v asociado con el vértice, x. Para lograr esto, necesita un conjunto de subconjuntos para las etiquetas de vértice y sus valores.
set_vertex_value (g, x, v)
Esta operación ofrece un nuevo valor, v para el valor asociado con el vértice, x. Para lograr esto, necesita un conjunto de subconjuntos para las etiquetas de vértice y sus valores.
Algunos gráficos también asocian los valores a sus bordes. Dichos gráficos necesitan las siguientes operaciones adicionales:
get_edge_value (g, x, y)
Esta operación devuelve el valor, v asociado con el borde, (x, y). Para lograr esto, necesita un conjunto de subconjuntos para bordes y sus valores.
set_edge_value (g, x, y, v)
Esta operación ofrece un nuevo valor, V para el valor asociado con el borde, (x, y). Para lograr esto, necesita un conjunto de subconjuntos para bordes y sus valores.
Conclusión
Un gráfico es un conjunto de vértices conectados con bordes. Un gráfico puede ser no dirigido o dirigido. Los bordes pueden ser no direccionales o direccionales. Los bucles pueden estar presentes o ausentes en un gráfico. Lo que debe aprender a continuación está establecido, configurado de potencia y multisetaje relacionado con gráficos. Después de eso, debe aprender los diferentes tipos de gráficos, como un gráfico orientado, gráfico regular, gráfico completo, gráfico bipartito, gráfico de torneo, gráfico de red de flujo, etc.
Chrys