¿Cuáles son los principios o características esenciales de los algoritmos gráficos en informática?

¡Interesante pregunta!

En primer lugar, los gráficos son matemáticamente equivalentes a las matrices: siempre que tenga una matriz cuadrática, puede interpretarla como la definición de un gráfico (donde el valor en la fila n-ésima y la columna m-ésima define la conectividad entre la n-ésima y el enésimo elemento). Si los valores en la matriz son diferentes de solo 0 o 1, tiene un gráfico ponderado. Si la matriz es asimétrica, tiene un gráfico dirigido. Si la matriz no es cuadrática, aún puede interpretarla como la matriz de adyacencia de un gráfico bipartito (los elementos representados por filas y columnas provienen de diferentes conjuntos).

Por lo tanto, no es una distinción discreta entre algoritmos gráficos y no gráficos. La pregunta es cuándo debería pensar en sus datos como gráficos y cuándo como matrices. Creo que la característica principal de los casos en los que tiene sentido pensar en gráficos es cuando la matriz correspondiente es escasa, es decir , no hay muchas entradas distintas de cero por fila y columna. Cuando piensa en cosas básicas como el recorrido de una gráfica primero en profundidad o primero en amplitud, eso no tiene sentido si llegaría a todos los vecinos después de solo una iteración. Muchos conceptos como la longitud de la ruta, los grados de los nodos, … también suponen implícitamente que no todo está conectado a todo (puede ser, por supuesto, pero estos conceptos no son muy útiles).

Sin embargo, suceden cosas interesantes al cambiar entre las dos vistas. Muchos algoritmos gráficos se pueden resolver de manera muy eficiente realizando operaciones algebraicas lineales en su matriz de adyacencia o matrices derivadas, ver, por ejemplo, agrupación espectral, también PageRank, aunque formulado intuitivamente en términos gráficos, se calcula como una operación de matriz iterada. Viceversa, puede comenzar desde una matriz y darse cuenta de que puede descubrir cosas nuevas acerca de sus datos al mirarlos como si fuera una matriz de adyacencia, aunque no tengo un ejemplo sorprendente en este momento.

En resumen, no es tan claro como podría haber esperado con su pregunta, pero en general, ver algoritmos de gráficos como algoritmos que trabajan en matrices dispersas podría ser una buena característica para distinguirlos de los demás.