In der Graphentheorie , einem Teilgebiet der Mathematik, bezeichnet die Graphkanonisierung das Problem, eine kanonische Form eines gegebenen Graphen G zu finden . Eine kanonische Form ist ein markierter Graph Canon( G ), der isomorph zu G ist , sodass jeder zu G isomorphe Graph dieselbe kanonische Form wie G besitzt . Aus einer Lösung des Graphkanonisierungsproblems lässt sich somit auch das Problem der Graphisomorphie lösen : Um zu prüfen, ob zwei Graphen G und H isomorph sind, berechnet man ihre kanonischen Formen Canon( G ) und Canon( H ) und prüft, ob diese beiden kanonischen Formen identisch sind.

Die kanonische Form eines Graphen ist ein Beispiel für eine vollständige Graphinvariante : Je zwei isomorphe Graphen besitzen dieselbe kanonische Form, und je zwei nicht-isomorphe Graphen besitzen unterschiedliche kanonische Formen. [ 1 ] [ 2 ] Umgekehrt kann jede vollständige Graphinvariante zur Konstruktion einer kanonischen Form verwendet werden. [ 3 ] Die Knotenmenge eines Graphen mit n Knoten kann mit den ganzen Zahlen von 1 bis n identifiziert werden . Mithilfe dieser Identifizierung lässt sich eine kanonische Form eines Graphen auch als Permutation seiner Knoten beschreiben. Kanonische Formen eines Graphen werden auch als kanonische Beschriftungen bezeichnet , [ 4 ] und die Graphkanonisierung wird auch als Graphkanonisierung bezeichnet .

Rechenkomplexität

Ungelöstes Problem in der Informatik
Ist die Graphkanonisierung in Polynomialzeit äquivalent zum Graphisomorphieproblem?
Weitere ungelöste Probleme in der Informatik

Das Graphisomorphieproblem ist das algorithmische Problem , festzustellen, ob zwei endliche Graphen isomorph sind . Offensichtlich ist das Graphkanonisierungsproblem mindestens genauso rechenaufwändig wie das Graphisomorphieproblem . Tatsächlich ist Graphisomorphie sogar AC⁰ - reduzierbar auf Graphkanonisierung. Es ist jedoch noch ungeklärt, ob die beiden Probleme in Polynomialzeit äquivalent sind . [ 2 ]

2019 kündigte László Babai einen quasi-polynomiellen Algorithmus zur Graphkanonisierung an, d. h. einen Algorithmus mit einer Laufzeit von O (n²) für ein festes n . [ 5 ] Obwohl die Existenz (deterministischer) polynomieller Algorithmen für Graphisomorphie in der Komplexitätstheorie weiterhin ein ungelöstes Problem darstellt, berichtete László Babai 1977, dass ein einfacher Knotenklassifizierungsalgorithmus mit einer Wahrscheinlichkeit von mindestens 1 − exp(−O( n )) nach nur zwei Verfeinerungsschritten eine kanonische Beschriftung eines zufällig aus der Menge aller n- Knoten-Graphen ausgewählten Graphen erzeugt. Kleine Modifikationen und ein zusätzlicher Tiefensuche- Schritt ermöglichen die Erzeugung kanonischer Beschriftungen solcher zufällig ausgewählter Graphen in linearer erwarteter Zeit. Dieses Ergebnis trägt dazu bei, die Frage zu klären, warum viele der berichteten Graphisomorphie-Algorithmen in der Praxis gut funktionieren. [ 6 ] [ 7 ] Dies war ein wichtiger Durchbruch in der probabilistischen Komplexitätstheorie , der in seiner Manuskriptform weite Bekanntheit erlangte und noch lange nach seiner Vorstellung auf einem Symposium als „unveröffentlichtes Manuskript“ zitiert wurde.

Eine allgemein bekannte kanonische Form ist der lexikografisch kleinste Graph innerhalb der Isomorphieklasse , also der Graph der Klasse mit der lexikografisch kleinsten Adjazenzmatrix, betrachtet als lineare Zeichenkette. Die Berechnung des lexikografisch kleinsten Graphen ist jedoch NP-schwer . [ 8 ]

Für Bäume wurde von Read (1972) ein prägnanter Kanonisierungsalgorithmus mit polynomieller Laufzeit und O ( n ) Speicherplatz vorgestellt . [ 9 ] Zunächst wird jeder Knoten mit der Zeichenkette „01“ beschriftet. Für jeden Nicht-Blattknoten x werden iterativ die führende 0 und die nachfolgende 1 aus der Beschriftung von x entfernt. Anschließend wird die Beschriftung von x zusammen mit den Beschriftungen aller benachbarten Blätter lexikografisch sortiert. Diese sortierten Beschriftungen werden verkettet, eine führende 0 und eine nachfolgende 1 hinzugefügt, dies wird zur neuen Beschriftung von x , und die benachbarten Blätter werden gelöscht. Falls zwei Knoten übrig bleiben, werden deren Beschriftungen lexikografisch sortiert verkettet.

Anwendungen

Die Graphkanonisierung ist die Grundlage vieler Graphisomorphie-Algorithmen. Eines der führenden Werkzeuge ist Nauty. [ 10 ]

Eine gängige Anwendung der Graphkanonisierung findet sich im Bereich des grafischen Data-Mining , insbesondere in chemischen Datenbankanwendungen . [ 11 ]

Eine Reihe von Identifikatoren für chemische Substanzen , wie SMILES und InChI , verwenden Kanonisierungsschritte in ihrer Berechnung. Dabei wird im Wesentlichen der Graph kanonisiert, der das Molekül repräsentiert. [ 12 ] [ 13 ] [ 14 ] Diese Identifikatoren dienen dazu, eine standardisierte (und teilweise lesbare) Methode zur Kodierung molekularer Informationen bereitzustellen und die Suche nach diesen Informationen in Datenbanken und im Web zu erleichtern.

Siehe auch

  • Kanonische Form  – Standarddarstellung eines mathematischen Objekts
  • Kanonisierung  – Verfahren zur Umwandlung von Daten in eine „standardisierte“, „normale“ oder kanonische Form

Referenzen

  1. ^ Arvind, Vikraman; Das, Bireswar; Köbler, Johannes (2008), „Ein Logspace-Algorithmus zur partiellen 2-Baum-Kanonisierung“, Computer Science – Theory and Applications: Drittes Internationales Computer Science Symposium in Russland, CSR 2008 Moskau, Russland, 7.–12. Juni 2008, Tagungsband , Lecture Notes in Comput. Sci., Band 5010, Springer, Berlin, S.  40–51 , doi : 10.1007/978-3-540-79709-8_8 , ISBN 978-3-540-79708-1, MR  2475148Die
  2. ^ a b Arvind, V.; Das, Bireswar; Köbler, Johannes (2007), „Die Raumkomplexität des k -Baum-Isomorphismus“, Algorithms and Computation: 18. Internationales Symposium, ISAAC 2007, Sendai, Japan, 17.–19. Dezember 2007, Tagungsband , Lecture Notes in Comput. Sci., Band 4835, Springer, Berlin, S.  822–833 , doi : 10.1007/978-3-540-77120-3_71 , ISBN 978-3-540-77118-0MR 2472661​ Die
  3. ^ Gurevich, Yuri (1997), „Von Invarianten zur Kanonisierung“ (PDF) , Bulletin of the European Association for Theoretical Computer Science (63): 115–119 , MR 1621595 Die
  4. ^ Babai, László ; Luks, Eugene (1983), „Canonical labeling of graphs“, Proc. 15th ACM Symposium on Theory of Computing , S.  171–183 , doi : 10.1145/800061.808746 , ISBN 0-89791-099-0Die
  5. ^ Babai, László (23. Juni 2019), Kanonische Form für Graphen in quasipolynomieller Zeit
  6. ^ Babai, László (1977), Zum Isomorphieproblem , unveröffentlichtes ManuskriptDie
  7. ^ Babai, László ; Kucera, L. (1979), „Canonical labeling of graphs in linear average time“, Proc. 20th Annual IEEE Symposium on Foundations of Computer Science , S.  39–46 , doi : 10.1109/SFCS.1979.8 , S2CID 14697933 Die
  8. ^ Babai, László ; Luks, E. (1983), „Canonical labeling of graphs“, Proc. 15th ACM Symposium on Theory of Computing , S.  171– 183
  9. ^ Read, Ronald C. (1972), „Die Kodierung verschiedener Arten von unbeschrifteten Bäumen“, Graphentheorie und Informatik , Academic Press, New York, S.  153–182 , MR 0344150 Die
  10. ^ McKay, Brendan D.; Piperno, Adolfo (2014), „Journal of Symbolic Computation“, Practical graph isomorphism, II , Bd. 60, S.  94–112 , arXiv : 1301.1493 , doi : 10.1016/j.jsc.2013.09.003 , ISSN 0747-7171 , S2CID 17930927  Die
  11. ^ Cook, Diane J .; Holder, Lawrence B. (2007), „6.2.1. Kanonische Beschriftung“, Mining Graph Data , John Wiley & Sons, S.  120–122 , ISBN 978-0-470-07303-2Die
  12. Weininger , David; Weininger, Arthur; Weininger, Joseph L. (Mai 1989). „SMILES. 2. Algorithmus zur Generierung eindeutiger SMILES-Notation“. Journal of Chemical Information and Modeling . 29 (2): 97–101 . doi : 10.1021/ci00062a008 . S2CID 6621315 . 
  13. ^ Kelley, Brian (Mai 2003). „Graph Canonicalization“ . Dr. Dobb's Journal .
  14. ^ Scheider, Nadine; Sayle, Roger A.; Landrum, Gregory A. (Oktober 2015). „Get Your Atoms in Order — An Open-Source Implementation of a Novel and Robust Molecular Canonicalization Algorithm“. Journal of Chemical Information and Modeling . 55 (10): 2111–2120 . doi : 10.1021/acs.jcim.5b00543 . PMID 26441310 .