Diskussion:Isomorphie von Graphen

Müsste folgende Zeile

(v,w) ist Kante von G1 genau dann, wenn (p(v),p(w)) Kante von G2 ist in gerichteten Graphen ohne Mehrfachkanten,

nicht eher heißen

(v,w) ist Kante von G1 genau dann, wenn entweder (p(v),p(w)) oder (p(w),p(v)) Kante von G2 ist in gerichteten Graphen ohne Mehrfachkanten,

Nach der Definition in einer meiner Vorlesungen (Visualisierung von Graphen bei Prof. Dorothea Wagner: Ein Automorphismus eines gerichteten Graphen ist eine Knotenpermutation, die alle Adjazenzen respektiert und entweder alle Richtungen erhält oder alle Richtungen umkehrt.

Isomorphie von gerichtetet Graphen

M. E. sind zwei gerichtete Graphen nicht isomorph, wenn die Richtungen ungekehrt werden.

Größere Probleme in diesem Artikel sehe ich bei den Mehrfachkanten. Was ist denn E1({v,w})? Ich habe nicht gefunden, dass diese Notation irgendwo bei Wiki definiert wurde.

BTW finde ich die Definition von isomorphen Graphen hinreichend belanglos, sodass es hier ohne großen Verlust gestrichen werden könnte.

Test in pol. Zeit

Was haltet ihr davon? http://arxiv.org/PS_cache/arxiv/pdf/1004/1004.1808v1.pdf 78.50.95.32 21:01, 18. Apr. 2010 (CEST)

Topologische Isomorphie vs. Kombinatorische Isomorphie

Meiner Meinung nach sollte der Unterschied zwischen Topologischer und Kombinatorischer Isomorphie herausgearbeitet werden! (nicht signierter Beitrag von 46.115.235.110 (Diskussion) 08:20, 14. Mär. 2011 (CET))

Komplexität...

https://dmv.mathematik.de/index.php/forum/nachrichten/457-neues-resultat-graphenisomorphie-problem-quasipolynomiell-loesbar (nicht signierter Beitrag von 84.144.6.72 (Diskussion) 18:58, 12. Dez. 2015 (CET))

Es fehlt noch ein Abschnitt oder auch ein eigener Artikel zu en:Graph isomorphism problem.--Pugo (Diskussion) 05:35, 17. Jan. 2017 (CET)

László Babai kündigte im Dezember 2015 an, einen Algorithmus gefunden zu haben

Im Text heißt es, László Babai kündigte im Dezember 2015 an, einen Algorithmus gefunden zu haben. Als ich das letzte Mal auf den Kalendar geschaut hatte, war Dezember 2020, als fünf Jahre später. Weiß jemand, was daruas geworden ist?--FerdiBf (Diskussion) 22:47, 19. Dez. 2020 (CET)

Nach dem Schluss der Lücke so weit ich sehe allgemein anerkannt, wenn auch noch nicht außerhalb arxiv in voller Länge veröffentlicht (nur extended abstract STOC 2016), stackexchange 2018, Wiebking, Graph isomorphism in quasipolynomial time parameterized by treewidth, 2019. Babai trug darüber auch auf dem ICM 2018 vor.--Claude J (Diskussion) 10:54, 20. Dez. 2020 (CET)