¿Qué tipo de problemas en los gráficos es más rápido (en términos de O grande) para resolver usando matrices de incidencia de estructuras de datos en lugar de matrices de adyacencia más amplias?Matriz de incidencia en lugar de matriz de adyacencia
Las complejidades espaciales de las estructuras son:
Adyacencia: O (V^2) Incidencia: O (VE)
Con la consecuencia de que una estructura de incidencia ahorra espacio si hay muchos más vértices que los bordes.
Usted puede mirar en el tiempo la complejidad de algunas operaciones típicas del gráfico:
Encontrar todos los vértices adyacentes a un vértice: Adj: O (V) Inc: O (VE)
Comprobar si dos vértices son adyacentes: Adj: O (1) Inc: O (E)
contar el valencia de un vértice: Adj: O (V) Inc: O (E)
Y así sucesivamente. Para cualquier algoritmo dado, puede usar bloques de construcción como los anteriores para calcular qué representación le brinda una mayor complejidad general en el tiempo. Como nota final, usar una matriz de cualquier tipo es extremadamente ineficiente en cuanto a espacio para todos los gráficos, excepto para los más densos, y recomiendo no usar ninguno a menos que haya descartado conscientemente alternativas como listas de adyacencia.
Tengo gráficos muy densos, con casi todas las conexiones. – psihodelia
¿No hay formas de almacenar eficientemente la matriz dispersa? – CMCDragonkai
Personalmente, nunca he encontrado una aplicación real de la representación de matriz de incidencia en un concurso de programación o problema de investigación. Creo que puede ser útil para probar algunos teoremas o para algunos problemas muy especiales. Un libro da un ejemplo de "contar el número de árboles de expansión" como un problema en el que esta representación es útil.
Otro problema con esta representación es que no tiene sentido almacenarla, porque es realmente fácil calcularla dinámicamente (para responder a lo que contiene la celda dada) de la lista de bordes.
Puede parecer más útil en hiper-gráficos, pero solo si es denso.
Así que mi opinión es - es útil solo para trabajos teóricos.
No estoy seguro de que sea fácil encontrar un límite superior computacional basado en la representación subyacente. La mayor parte de la complejidad algorítmica será en términos del _número_ de bordes o vértices, no de la representación subyacente. Cualquier límite inferior en la complejidad se aplicará ya sea que se implemente en lápiz y papel o en una computadora. ¿Piensas que si hay clases específicas de problemas que tienes en mente, entonces tal vez menciones esas y podamos tratar de resolverlo? – Gian
La matriz de incidencia es MxN y la matriz de adyacencia es NxN si N es muy grande y tu gráfica es muy dispersa, tendrás MxN