Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Gráficos dirigidos y no dirigidos

¿Qué es un gráfico?

Un gráfico es una colección de y que representa las relaciones:nodesedges

  • son vértices que corresponden a objetos.Nodes

  • son las conexiones entre los objetos.Edges

  • Los bordes del gráfico a veces tienen, que indican la fuerza (o algún otro atributo) de cada conexión entre los nodos.Weights

Estas definiciones son generales, ya que el significado exacto de los nodos y aristas de un gráfico depende de la aplicación específica. Por ejemplo, puedes modelar las amistades en una red social usando un gráfico. Los nodos de gráfico son personas y los bordes representan amistades. La correspondencia natural de los gráficos con los objetos físicos y las situaciones significa que puede utilizar gráficos para modelar una amplia variedad de sistemas. Por ejemplo:

  • Vinculación de página web: los nodos de gráfico son páginas web y los bordes representan hipervínculos entre páginas.

  • Aeropuertos — los nodos del gráfico son aeropuertos, y los bordes representan vuelos entre aeropuertos.

En, las funciones y construyen objetos que representan gráficos no dirigidos y dirigidos.MATLAB®graphdigraph

  • tienen aristas que no tienen una dirección.Undirected graphs Los bordes indican una relación, en la que cada arista se puede atravesar en ambas direcciones.two-way Esta figura muestra un gráfico simple no dirigido con tres nodos y tres aristas.

  • tienen bordes con dirección.Directed graphs Los bordes indican una relación, en que cada arista solo se puede atravesar en una sola dirección.one-way Esta figura muestra un gráfico dirigido simple con tres nodos y dos aristas.

La posición, la longitud o la orientación exactas de los bordes en una ilustración de gráfico normalmente no tienen significado. En otras palabras, el mismo gráfico se puede visualizar de varias maneras diferentes reorganizando los nodos y/o distorsionando los bordes, siempre que la estructura subyacente no cambie.

Autoloops y Multigrafías

Gráficos creados utilizando y pueden tener uno o más, que son aristas que conectan un nodo a sí mismo.graphdigraphself-loops Además, los gráficos pueden tener varios bordes con los mismos nodos de origen y de destino, y el gráfico se conoce entonces como un.multigraph Un Multigráfico puede contener o no bucles autoloops.

Para los fines de las funciones de algoritmo de gráficos en, un gráfico que contiene un nodo con un único bucle propio no es un Multigráfico.MATLAB Sin embargo, si el gráfico contiene un nodo con bucles autoloops, es un Multigráfico.multiple

Por ejemplo, la siguiente figura muestra un Multigráfico no dirigido con bucles autoloops. El nodo A tiene tres autoloops, mientras que el nodo C tiene uno. El gráfico contiene estas tres condiciones, cualquiera de las cuales lo convierte en un Multigráfico.

  • El nodo A tiene tres autoloops.

  • Los nodos A y B tienen cinco aristas entre ellos.

  • Los nodos A y C tienen dos aristas entre ellos.

Para determinar si un gráfico determinado es un Multigráfico, utilice la función.ismultigraph

Creación de gráficos

Las formas principales de crear un gráfico incluyen el uso de una matriz de adyacencia o una lista de aristas.

La matriz de adyacencia

Una forma de representar la información en un gráfico es con un cuadrado.adjacency matrix Las entradas distinto de cero en una matriz de adyacencia indican una arista entre dos nodos y el valor de la entrada indica el peso de la arista. Los elementos diagonales de una matriz de adyacencia son normalmente cero, pero un elemento diagonal distinto de cero indica un, o un nodo que está conectado a sí mismo por un borde.self-loop

  • Cuando se utiliza para crear un grafo no dirigido, la matriz de adyacencia debe ser simétrica.graph En la práctica, las matrices son con frecuencia triangulares para evitar repeticiones. Para construir un gráfico no dirigido utilizando sólo el triángulo superior o inferior de la matriz de adyacencia, utilice o.graph(A,'upper')graph(A,'lower')

  • Cuando se utiliza para crear un grafo dirigido, la matriz de adyacencia no necesita ser simétrica.digraph

  • Para los gráficos grandes, la matriz de adyacencia contiene muchos ceros y es típicamente una matriz dispersa.

  • No se puede crear un Multigráfico a partir de una matriz de adyacencia.

Por ejemplo, considere este gráfico no dirigido.

Usted puede representar el gráfico con esta matriz de adyacencia:

(012103230).

Para construir el gráfico en, ingrese:MATLAB

A = [0 1 2; 1 0 3; 2 3 0]; node_names = {'A','B','C'}; G = graph(A,node_names)
G =     graph with properties:      Edges: [3×2 table]     Nodes: [3×1 table]

Puede utilizar las funciones o para crear un gráfico utilizando una matriz de adyacencia, o puede utilizar la función para encontrar la matriz de adyacencia dispersa ponderada o no ponderada de un gráfico preexistente.graphdigraphadjacency

Lista de aristas

Otra forma de representar la información en un gráfico es enumerando todos los bordes.

Por ejemplo, considere el mismo gráfico no dirigido.

Ahora representa el gráfico por la lista de bordes

Edge     Weight(A,B)(A,C)12(B,C)3

Desde la lista de bordes es fácil concluir que el gráfico tiene tres nodos únicos, y, que están conectados por los tres bordes enumerados.ABC Si el gráfico tenía nodos desconectados, no se encontrarían en la lista de aristas y tendrían que especificarse por separado.

En, la lista de aristas está separada por una columna en nodos y nodos.MATLABsourcetarget Para los gráficos dirigidos, la dirección del borde (desde el origen hasta el destino) es importante, pero para los gráficos no dirigidos, el nodo de origen y de destino son intercambiables. Una forma de construir este gráfico utilizando la lista de aristas es utilizar entradas separadas para los nodos de origen, los nodos de destino y los pesos de arista:

source_nodes = {'A','A','B'}; target_nodes = {'B','C','C'}; edge_weights = [1 2 3]; G = graph(source_nodes, target_nodes, edge_weights);

Ambos y permiten la construcción de un gráfico simple o Multigráfico de una lista de bordes.graphdigraph Después de construir un gráfico, puede mirar los bordes (y sus propiedades) con el comando.GG.Edges El orden de los bordes está ordenado por el nodo de origen (primera columna) y, secundariamente, por el nodo de destino (segunda columna).G.Edges Para los gráficos no dirigidos, el nodo con el índice más pequeño aparece como el nodo de origen y el nodo con el índice más grande aparece como el nodo de destino.

Dado que la implementación subyacente de y depende de matrices dispersas, muchos de los mismos costos de indexación se aplican.graphdigraph Usar uno de los métodos anteriores para construir un gráfico a la vez desde los pares de tripletes es más rápido que crear un gráfico vacío y agregar iterativamente más nodos y aristas.(source,target,weight) Para obtener el mejor rendimiento, minimice el número de llamadas a,,,, y.graphdigraphaddedgeaddnodermedgermnode

Identificadores de nodo de gráfico

De forma predeterminada, todos los nodos de un gráfico creados con o están numerados.graphdigraph Por lo tanto, siempre puede referirse a ellos por su numérico.node index

Si el gráfico tiene nombres de nodo (es decir, contiene una variable), también puede hacer referencia a los nodos de un gráfico utilizando sus nombres.G.NodesName Por lo tanto, los nodos nombrados en un gráfico pueden ser referidos por sus índices de nodo o nombres de nodo. Por ejemplo, se puede llamar al nodo,.1'A'

El término abarca ambos aspectos de la identificación de nodos.node ID El ID de nodo hace referencia tanto al índice de nodo como al nombre del nodo.

Para mayor comodidad, recuerda qué tipo de ID de nodo utilizas cuando llamas a la mayoría de las funciones gráficas.MATLAB Por lo tanto, si hace referencia a los nodos de un gráfico por sus índices de nodos, la mayoría de las funciones gráficas devuelven una respuesta numérica que también hace referencia a los nodos por sus índices.

A = [0 1 1 0; 1 0 1 0; 1 1 0 1; 0 0 1 0]; G = graph(A,{'a','b','c','d'}); p = shortestpath(G,1,4) 
p =       1     3     4 

Sin embargo, si hace referencia a los nodos por sus nombres, la mayoría de las funciones de gráficos devuelven una respuesta que también hace referencia a los nodos por sus nombres (contenidos en una matriz de celdas de vectores de caracteres o matriz de cadenas).

p1 = shortestpath(G,'a','d')
p1 =    1×3 cell array      {'a'}    {'c'}    {'d'}

Se utiliza para buscar el ID de nodo numérico para un nombre de nodo determinado.findnode Por el contrario, para un ID de nodo numérico determinado, índice en para determinar el nombre de nodo correspondiente.G.Nodes.Name

Modificar o consultar gráfico existente

Después de construir un u objeto, puede utilizar una variedad de funciones para modificar la estructura del gráfico o para determinar cuántos nodos o aristas tiene el gráfico.graphdigraph Esta tabla enumera algunas funciones disponibles para modificar o consultar y objetos.graphdigraph

addedge

Agregue uno o más bordes a un gráfico

rmedge

Quite uno o más bordes de un gráfico

addnode

Agregue uno o más nodos a un gráfico

rmnode

Quite uno o más nodos de un gráfico

findnode

Localice un nodo específico en un gráfico

findedge

Localice una arista específica en un gráfico

numnodes

Busque el número de nodos en un gráfico

numedges

Encuentre el número de aristas en un gráfico

edgecount

Número de aristas entre los nodos especificados

flipedge

Invierta la dirección de los bordes del gráfico dirigidos

reordernodes

Permute el orden de los nodos en un gráfico

subgraph

Extraiga el subgráfico

Consulte algunos ejemplos comunes de modificación de gráficos.Modificar nodos y aristas del gráfico existente

Consulte también

|

Temas relacionados