Uno de los principales problemas en la enumeración de gráficos es determinar la 'forma' de un gráfico, por ejemplo, la clase de isomorfismo de cualquier gráfico particular. Soy plenamente consciente de que cada gráfico se puede representar como una matriz simétrica. Sin embargo, para obtener su forma, necesitaría una colección de permutaciones de fila / columna, lo que hace que una matriz sea un poco menos adecuada. También es un poco más difícil 'ver' el gráfico, una vez que está en esa forma.
Mi pregunta es: ¿hay alguna álgebra 'gráfica' que pueda describir la 'forma' de los gráficos?
En lo que estoy pensando es en qué tipo de sistemas formales tienden a surgir los topólogos algebraicos. En particular, cosas como el álgebra para invariantes de nudos, o sistemas de notación como operads o polígrafos . Este tipo de 'álgebras de garabatos' no está tan bien desarrollado, por lo que quizás haya una razón para creer que no existe tal álgebra para los gráficos, pero creo que debería preguntar antes de suponer lo contrario.
ACTUALIZAR:
Mi pregunta es probablemente muy estrecha y no responde de inmediato con un "sí", por lo que si a los moderadores no les importa, la ampliaré preguntando:
¿Hay algún sistema existente (del tipo que describo anteriormente) que pueda adaptarse (fácilmente o de otro modo) para crear dicho sistema? Si hay más de uno, no dude en mencionarlos a todos. Y agregue los que ya se mencionaron también.
Motivación
Mi motivación para tal pregunta es en realidad sobre la clasificación de gráficos asimétricos. Soy solo un estudiante universitario, por lo que mi revisión del estado actual de la teoría de gráficos algebraicos es bastante escasa. Pero todavía tengo que ver mucho, si es que hay alguno, trabajando para tratar de describir sistemáticamente todos los gráficos de forma algebraica, y en particular, uno que use metáforas visuales sobre simbólicas.
Ejemplo práctico donde tal sistema sería útil
Supongamos que uno quiere describir una prueba de que todos los gráficos de Eulerian deben tener vértices de grado par. Una prueba estándar generalmente usa argumentos sobre grados pares e impares, sin mencionar los bordes reales utilizados. Un estudiante típico encontraría esa prueba por primera vez, y probablemente comenzaría a dibujar gráficos, intentando convencerse a sí mismo del argumento. Pero quizás una herramienta mejor que el argumento 'lógico' puro, sería mostrar que cualquier colección de 'símbolos' de tal lenguaje no podría satisfacer alguna condición de 'integridad'.
Sí, lo sé, estoy siendo ondulado a mano en esta última parte ... ¡Si no lo fuera, aunque probablemente comenzaría a crear un sistema así!
Pero ignorando mi vaguedad por un momento, tengo la sensación de que muchos de los viejos y conocidos teoremas de la teoría de grafos no son difíciles, pero requieren cierta conceptualización de que un marco realmente bueno podría 'vincularse' y 'empaquetarse' en una vista unificada.
fuente
Respuestas:
Muchas personas han tratado de encontrar un lenguaje algebraico para describir la forma de un gráfico. Esta pregunta es esencialmente la que motiva la teoría de grafos estructurales .
En el corazón de esta área de las matemáticas discretas está el estudio de las descomposiciones de grafos. Algunas de las personas que trabajan en esta área son Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković y sus colaboradores, aunque esta lista está sesgada por mis propios intereses de investigación.
Tipos particulares de descomposiciones de gráficos han llevado a algunos de los resultados más generales en la teoría de gráficos. Por ejemplo, una de las principales herramientas técnicas desarrolladas para el proyecto de gráficos menores, que condujo al teorema de Robertson-Seymour , es el teorema de la estructura de gráficos . Esto muestra que las clases de gráficos que excluyen algunos menores pueden construirse a partir de gráficos más simples.
Las descomposiciones estudiadas hasta la fecha son, en cierto sentido, no algebraicas. Mi intuición personal es que hay indicios de que no existe un sistema "agradable" como el que busca. Hacer que esta afirmación simplista sea precisa probablemente requeriría una empresa no trivial en la teoría de modelos finitos, pero sospecho que también podría conducir a nuevos e interesantes resultados en la teoría de gráficos (ya sea exitosa o no).
fuente
Esta pregunta es importante en la programación funcional ya que la representación habitual de gráficos es poco elegante e ineficiente para usar en lenguajes puramente funcionales.
Un buen enfoque fue presentado en ICFP el año pasado: "Gráficos algebraicos con clase (Pearl funcional)" , por Andrey Mokhov.
No sé si responde completamente a sus necesidades, pero puede representar algebraicamente una amplia gama de diferentes tipos de gráficos dirigidos y no dirigidos.
fuente