L'un des principaux problèmes de l'énumération des graphes est de déterminer la «forme» d'un graphe, par exemple la classe d'isomorphisme d'un graphe particulier. Je suis pleinement conscient que chaque graphique peut être représenté comme une matrice symétrique. Cependant, pour obtenir sa forme, vous auriez besoin d'une collection de permutations de lignes / colonnes, ce qui rend une matrice un peu moins adaptée. Il est également un peu plus difficile de «voir» le graphique, une fois qu'il est sous cette forme.
Ma question est la suivante: existe-t-il des algèbres «graphiques» qui peuvent décrire la «forme» des graphiques?
Je pense aux types de systèmes formels que les topologues algébriques ont tendance à proposer. En particulier, des choses comme l'algèbre pour les invariants de nœuds, ou les systèmes de notation comme les opéras ou les polygraphes . Ces types d'algèbres de doodle ne sont pas aussi bien développés, donc il y a peut-être une raison de croire qu'il n'y a pas une telle algèbre pour les graphiques, mais je voudrais bien demander avant de supposer le contraire.
MISE À JOUR:
Ma question est probablement très étroite et ne répond pas immédiatement par un «oui», donc si cela ne dérange pas les modérateurs, je vais l'élargir en demandant:
Existe-t-il des systèmes existants (du type que je décris ci-dessus) qui pourraient être adaptés (facilement ou autrement) pour créer un tel système? S'il y en a plus d'un, n'hésitez pas à les mentionner tous. Et ajoutez également ceux déjà mentionnés.
Motivation
Ma motivation pour une telle question est en fait de classer les graphiques asymétriques. Je ne suis qu'un étudiant de premier cycle, donc mon examen de l'état actuel de la théorie des graphes algébriques est assez mince. Mais je n'ai pas encore vu beaucoup, le cas échéant, de travail pour essayer de décrire systématiquement tous les graphiques de manière algébrique, et en particulier celui qui utilise des métaphores visuelles plutôt que des symboles.
Exemple pratique où un tel système serait utile
Supposons que l'on veuille décrire une preuve que tous les graphes eulériens doivent avoir des sommets de degré pair. Une preuve standard utilise généralement des arguments sur les degrés pairs et impairs, sans mentionner les arêtes réelles utilisées. Un étudiant typique trouverait une telle preuve pour la première fois et commencerait probablement à dessiner des graphiques, essayant de se convaincre de l'argument. Mais peut-être qu'un meilleur outil que l'argument purement «logique» serait de montrer que toute collection de «symboles» d'un tel langage ne pourrait pas remplir une condition de «complétude».
Ouais, je sais, je suis agité à la main dans cette dernière partie .. Si je ne l'étais pas, je commencerais probablement à créer un tel système moi-même!
Mais en ignorant mon imprécision pendant un instant, j'ai l'impression que bon nombre des anciens théorèmes bien connus de la théorie des graphes ne sont pas difficiles mais nécessitent une certaine conceptualisation qu'un très bon cadre pourrait `` lier '' et `` assembler '' dans une vue unifiée.
la source
Réponses:
Beaucoup de gens ont essayé de trouver un langage algébrique pour décrire la forme d'un graphique. Cette question est essentiellement celle qui motive la théorie des graphes structurels .
Au cœur de ce domaine des mathématiques discrètes se trouve l'étude des décompositions de graphes. Certaines des personnes travaillant dans ce domaine sont Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković et leurs collaborateurs, bien que cette liste soit biaisée par mes propres intérêts de recherche.
Des types particuliers de décompositions de graphes ont conduit à certains des résultats les plus généraux de la théorie des graphes. Par exemple, l'un des principaux outils techniques développés pour le projet des mineurs de graphes, qui a conduit au théorème de Robertson-Seymour , est le théorème de la structure des graphes . Cela montre que les classes de graphiques qui excluent certains mineurs peuvent être construites à partir de graphiques plus simples.
Les décompositions étudiées à ce jour sont en quelque sorte non algébriques. Mon intuition personnelle est qu'il y a des indications qu'il n'y a pas de système "sympa" comme celui que vous recherchez. Rendre cette déclaration glib précise nécessiterait probablement une entreprise non triviale dans la théorie des modèles finis, mais je soupçonne qu'elle pourrait également conduire à de nouveaux résultats intéressants en théorie des graphes (avec succès ou non).
la source
Cette question est importante dans la programmation fonctionnelle car les représentations habituelles des graphiques sont inélégantes et inefficaces à utiliser dans des langages purement fonctionnels.
Une belle approche a été présentée à l'ICFP l'année dernière: "Graphiques algébriques avec classe (perle fonctionnelle)" , par Andrey Mokhov.
Je ne sais pas s'il répond pleinement à vos besoins, mais il peut représenter algébriquement un large éventail de différents types de graphiques dirigés et non dirigés.
la source