Disclaimer: Ich bin ein absoluter Neuling in der Graphentheorie und ich bin mir nicht sicher, ob dies zu SO, Math SE usw. gehört.

Wenn 2 Adjazenzmatrizen A und B angegeben sind, wie kann ich feststellen, ob A und B isomorph sind.

Zum Beispiel A und B, die nicht isomorph sind, und C und D, die isomorph sind.

A = [ 0 1 0 0 1 1     B = [ 0 1 1 0 0 0
      1 0 1 0 0 1           1 0 1 1 0 0
      0 1 0 1 0 0           1 1 0 1 1 0
      0 0 1 0 1 0           0 1 1 0 0 1
      1 0 0 1 0 1           0 0 1 0 0 1
      1 1 0 0 1 0 ]         0 0 0 1 1 0 ]

C = [ 0 1 0 1 0 1     D = [ 0 1 0 1 1 0
      1 0 1 0 0 1           1 0 1 0 1 0
      0 1 0 1 1 0           0 1 0 1 0 1
      1 0 1 0 1 0           1 0 1 0 0 1
      0 0 1 1 0 1           1 1 0 0 0 1
      1 1 0 0 1 0 ]         0 0 1 1 1 0 ]   

(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)

Hier ist, wie ich meinen Algorithmus gestartet habe (bitte entschuldigen Sie meine mangelnde mathematische Genauigkeit). Bitte helfen Sie mir bei der Vervollständigung / Korrektur!

Wenn Größe (Anzahl der Kanten, in diesem Fall Anzahl der Einsen) von A! = Größe von B => Diagramme sind nicht isomorphZählen Sie für jeden Scheitelpunkt von A seinen Grad und suchen Sie nach einem passenden Scheitelpunkt in B, der den gleichen Grad hatun wurde nicht früher abgeglichen. Wenn es keine Übereinstimmung gibt => Diagramme sind nicht isomorph. Nun, da wir nicht schnell beweisen können, dass A und B nicht isomorph sind, was ist der nächste Schritt? Wäre es richtig, jede Permutation von Linien in A zu versuchen, bis A mit B übereinstimmt? Wirklich nicht sicher über dieses ...