Qué es: conectividad fuerte, conectividad unidireccional, conectividad débil, sin conectividad
Las siguientes son las definiciones de fuertemente conectado, unidireccionalmente conectado, débilmente conectado y desconectado:
Componente conectado: un subgrafo conectado máximo de un gráfico no dirigido G se llama G A componente conectado (o rama conectada). Un gráfico conectado tiene solo un componente conectado, en sí mismo un gráfico no dirigido no conectado tiene múltiples componentes conectados.
Gráfico fuertemente conectado: en el gráfico dirigido G=(V,E), si para dos vértices diferentes x e y en V, hay caminos de x a y y de y a x, entonces. Se dice que G es un grafo fuertemente conexo. Correspondientemente existe el concepto de componentes fuertemente conectados. Un gráfico fuertemente conectado tiene solo un componente fuertemente conectado, que en sí mismo es un gráfico dirigido no fuertemente conectado tiene múltiples componentes fuertemente conectados.
Gráfico conectado unidireccional: Sea G=
Gráfico débilmente conectado: reemplace todos los bordes dirigidos del gráfico dirigido con bordes no dirigidos, y el gráfico resultante se denomina gráfico base del gráfico original. Si el gráfico base de un gráfico dirigido es un gráfico conexo, el gráfico dirigido es un gráfico débilmente conexo.
Ruta principal: Todos los vértices del camino son diferentes entre sí. El camino principal debe ser un camino simple, pero lo contrario no es cierto.
En teoría de grafos, los grafos conectados se basan en el concepto de conectividad. En un gráfico no dirigido G, si hay un camino que conecta el vértice i con el vértice j (por supuesto, debe haber un camino de j a i), entonces se dice que i y j están conectados. Si G es un gráfico dirigido, entonces todos los bordes en el camino que conecta i y j deben estar en la misma dirección.
Si dos puntos cualesquiera de la gráfica están conectados, entonces la gráfica se llama gráfica conexa. Si este gráfico es dirigido, se llama gráfico fuertemente conectado (nota: debe haber caminos en ambas direcciones). La conectividad de gráficos es la propiedad básica de los gráficos.
Información ampliada:
Problema de aristas de un grafo fuertemente conexo:
Un grafo fuertemente conexo con n vértices tiene como máximo n (n-1) aristas. son al menos n aristas.
1. La situación más común: es decir, dos de n vértices están conectados si no se tiene en cuenta la dirección, hay n (n-1)/2 aristas que conectan dos n vértices. el gráfico fuertemente conectado es un gráfico dirigido, por lo que cada arista tiene dos direcciones, n(n-1)/2×2=n(n-1), por lo que un gráfico fuertemente conectado con n vértices tiene como máximo n(n-1 ) bordes.
2. La situación mínima: es decir, n vértices forman un círculo y las direcciones de los lados del círculo son las mismas, es decir, todos están en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj. son n lados.
Encontrar los componentes conectados de un gráfico no dirigido:
Como ejemplo de aplicación de recorrido de un gráfico, analicemos cómo encontrar los componentes conectados de un gráfico. El subgrafo conectado máximo en un gráfico no dirigido se llama componente conectado. El propósito de encontrar los componentes conectados de un gráfico es determinar si un vértice del gráfico puede alcanzar otro vértice del gráfico, es decir, si existe un camino entre dos vértices cualesquiera del gráfico.
Para un gráfico conectado, atravesar el gráfico comenzando desde cualquier vértice del gráfico puede acceder a todos los vértices del gráfico, es decir, hay una ruta entre dos vértices cualesquiera en el gráfico conectado.
Gráfico conectado a la enciclopedia Baidu