Diskussion:Isomorphie von Graphen

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Quelltext bearbeiten]

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

[Quelltext bearbeiten]

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)Beantworten

Topologische Isomorphie vs. Kombinatorische Isomorphie

[Quelltext bearbeiten]

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)) Beantworten

Komplexität...

[Quelltext bearbeiten]

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))Beantworten

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

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

[Quelltext bearbeiten]

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)Beantworten

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)Beantworten