Eines der Hauptprobleme bei der Aufzählung von Graphen ist die Bestimmung der "Form" eines Graphen, z. B. der Isomorphismusklasse eines bestimmten Graphen. Mir ist völlig bewusst, dass jeder Graph als symmetrische Matrix dargestellt werden kann. Um die Form zu erhalten, benötigen Sie jedoch eine Sammlung von Zeilen- / Spaltenpermutationen, wodurch eine Matrix etwas weniger geeignet ist. Es ist auch etwas schwieriger, das Diagramm zu "sehen", sobald es in dieser Form vorliegt.
Meine Frage ist: Gibt es 'grafische' Algebren, die die 'Form' von Graphen beschreiben können?
Ich denke darüber nach, welche Arten von formalen Systemen algebraische Topologen entwickeln. Insbesondere Dinge wie die Algebra für Knoteninvarianten oder Notationssysteme wie Operaden oder Polygraphen . Diese Art von "Doodle-Algebren" ist bei weitem nicht so gut entwickelt, daher gibt es vielleicht einen Grund zu der Annahme, dass es für Graphen keine solche Algebra gibt, aber ich würde fragen, bevor ich etwas anderes annehme.
AKTUALISIEREN:
Meine Frage ist wahrscheinlich sehr eng und kann nicht sofort mit einem "Ja" beantwortet werden. Wenn es den Moderatoren nichts ausmacht, werde ich sie erweitern, indem ich frage:
Gibt es Systeme (wie ich sie oben beschrieben habe), die (einfach oder auf andere Weise) angepasst werden könnten, um ein solches System zu erstellen? Wenn es mehr als eine gibt, können Sie alle erwähnen. Und werfen Sie auch die bereits erwähnten hinein.
Motivation
Meine Motivation für eine solche Frage ist eigentlich die Klassifizierung asymmetrischer Graphen. Ich bin nur ein Student, daher ist meine Überprüfung des aktuellen Standes der algebraischen Graphentheorie ziemlich dünn. Aber ich habe noch nicht viel zu tun, wenn überhaupt, um systematisch alle Graphen auf algebraische Weise zu beschreiben, insbesondere solche, die visuelle Metaphern gegenüber symbolischen verwenden.
Praktisches Beispiel, wo ein solches System nützlich wäre
Angenommen, man möchte einen Beweis beschreiben, dass alle Eulerschen Graphen Eckpunkte von gleichem Grad haben müssen. Ein Standardbeweis verwendet normalerweise Argumente über gerade und ungerade Grade, ohne die tatsächlich verwendeten Kanten zu erwähnen. Ein typischer Student würde zum ersten Mal einen solchen Beweis finden und wahrscheinlich mit dem Zeichnen von Grafiken beginnen, um sich von dem Argument zu überzeugen. Aber vielleicht wäre es ein besseres Werkzeug als das reine "logische" Argument, zu zeigen, dass eine Sammlung von "Symbolen" aus einer solchen Sprache eine "Vollständigkeits" -Bedingung nicht erfüllen könnte.
Ja, ich weiß, ich bin in diesem letzten Teil von Hand gewellt. Wenn ich es nicht wäre, würde ich wahrscheinlich selbst anfangen, ein solches System zu erstellen!
Wenn ich jedoch meine Unbestimmtheit für einen Moment ignoriere, habe ich das Gefühl, dass viele der alten und bekannten Theoreme in der Graphentheorie nicht schwierig sind, sondern eine Konzeptualisierung erfordern, die ein wirklich guter Rahmen zu einer einheitlichen Sichtweise zusammenfügen und verpacken könnte.
quelle
Antworten:
Viele Menschen haben versucht, eine algebraische Sprache zu finden, um die Form eines Graphen zu beschreiben. Diese Frage motiviert im Wesentlichen die Strukturgraphentheorie .
Im Zentrum dieses Bereichs der diskreten Mathematik steht das Studium der Graphzerlegung. Einige der in diesem Bereich tätigen Personen sind Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković und ihre Mitarbeiter, obwohl diese Liste von meinen eigenen Forschungsinteressen beeinflusst wird.
Bestimmte Arten von Graphzerlegungen haben zu einigen der allgemeinsten Ergebnisse in der Graphentheorie geführt. Eines der wichtigsten technischen Werkzeuge, die für das Graph-Minors-Projekt entwickelt wurden und zum Robertson-Seymour-Theorem führten , ist beispielsweise das Graphstruktur-Theorem . Dies zeigt, dass Klassen von Diagrammen, die einige kleinere ausschließen, aus einfacheren Diagrammen aufgebaut werden können.
Die bisher untersuchten Zerlegungen sind in gewissem Sinne nicht algebraisch. Meine persönliche Intuition ist, dass es Anzeichen dafür gibt, dass es kein "nettes" System wie das gibt, das Sie suchen. Um diese glib-Aussage präzise zu machen, wäre wahrscheinlich ein nicht triviales Unternehmen in der endlichen Modelltheorie erforderlich, aber ich vermute, dass dies auch zu interessanten neuen Ergebnissen in der Graphentheorie führen könnte (ob erfolgreich oder nicht).
quelle
Diese Frage ist bei der funktionalen Programmierung wichtig, da die übliche Darstellung von Graphen in rein funktionalen Sprachen unelegant und ineffizient ist.
Ein schöner Ansatz wurde letztes Jahr auf der ICFP vorgestellt: "Algebraische Graphen mit Klasse (Functional Pearl)" von Andrey Mokhov.
Ich weiß nicht, ob es Ihren Anforderungen vollständig entspricht, aber es kann algebraisch eine Vielzahl verschiedener Arten von gerichteten und ungerichteten Graphen darstellen.
quelle