Componente conectado (teoría de grafos)

En teoría de grafos, un componente conectado (o simplemente un componente) de un grafo indirecto es un subgrafo en el que: por ejemplo, el grafo mostrado en la ilustración de la derecha tiene tres componentes conectados. Un gráfico que está conectado tiene exactamente un componente conectado, que consiste en todo el gráfico.

De manera similar a los espacios topológicos, una forma alternativa de definir componentes conectados implica las clases de equivalencia de una relación de equivalencia definida en los vértices del grafo. En un gráfico indirecto, se dice que un vértice v es alcanzable desde un vértice u si hay un camino de u A v. En esta definición, por convención, un solo vértice se cuenta como una trayectoria de longitud cero, y el mismo vértice se puede presentar más de una vez dentro de una trayectoria. La accesibilidad es una relación de equivalencia, ya que: .

El número de componentes conectados es un invariante topológico importante de un gráfico. En la teoría topológica de gráficos se puede interpretar como el número cero de Betti del gráfico. En la teoría de grafos algebraicos es igual a la multiplicidad de 0 como el valor propio de la matriz Laplaciana del grafo. También es el índice del primer coeficiente distinto de cero del polinomio cromático de un grafo. Los números de componentes conectados juegan un papel clave en el teorema de todos los gráficos que tienen coincidencias perfectas, y en la definición de la dureza de los gráficos.

Es inmediato calcular los componentes conectados de un gráfico en tiempo lineal (en términos de los números de los vértices y bordes del gráfico) utilizando la búsqueda de amplitud o la búsqueda de profundidad. De cualquier manera, una búsqueda que comienza en algún vértice V en particular encontrará todo el componente conectado que contiene v (y nada más) antes de regresar. Para encontrar todos los componentes conectados de un gráfico, debe desplazarse por sus vértices, iniciando una nueva investigación en amplitud o profundidad cada vez que llegue a un vértice que no se haya incluido ya en un componente conectado encontrado anteriormente. Hopcroft y Tarjan (1973) esencialmente describen este algoritmo, y afirman que en este punto era "bien conocido" . También hay algoritmos eficientes para trazar dinámicamente los componentes conectados de un gráfico al agregar vértices y aristas, como una aplicación inmediata de una estructura de datos de conjuntos disjuntos. Estos algoritmos requieren un tiempo amortizado de O (α (n)) para cada operación, donde agregar vértices y aristas y determinar el componente conectado en el que cae un vértice son ambas operaciones, y α(n) es un inverso de crecimiento lento de la función de Ackermann. Un problema relacionado es rastrear el número de componentes conectados cuando todos los bordes se eliminan de un gráfico, uno por uno; existe un algoritmo para resolver esto con un tiempo constante para cada consulta, y O(|V||E|) para mantener la estructura de datos; esto conduce a un costo amortizado de O(|V|) para cualquier cancelación de bordes. Para los bosques, el costo se puede reducir a O (q + | V / log / V|), o al costo amortizado O(log| V/) para cada borrado de bordes. Los investigadores también estudiaron algoritmos para encontrar componentes conectados en modelos de computación más limitados, como programas en los que la memoria operativa está limitada a un número logarítmico de bits (definido por la clase de complejidad L). Lewis & amp; Papadimitriou (1982) preguntaron si es posible verificar en un espacio logarítmico si dos vértices pertenecen al mismo componente conectado de un gráfico indirecto, y definieron una clase de complejidad SL de problemas que equivalen a la conectividad del espacio logarítmico. Finalmente Reingold (2008) fue capaz de encontrar un algoritmo para resolver este problema de conectividad en el espacio logarítmico, demostrando que L=SL.

Teoría de grafos

Acoplamiento (teoría de grafos)

En la disciplina matemática de la teoría de grafos, una coincidencia o conjunto de aristas independientes en un grafo es un conjunto bipartito de aristas sin vé...

Teoría del mundo pequeño

La teoría del mundo pequeño o mundos pequeños, o el efecto de un mundo pequeño es una teoría matemática, y las afirmaciones sociológicas de que todas las redes ...

Problemas solucionables en tiempo polinomial

Redes sociales

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad