fragen zur graphentheorie



  • hallo

    ich versuche gerade graphentheorie zu verstehen und mir stellen sich folgende fragen:

    1. ungerichtete graphen ohne mehrfachkanten aber möglicherweise mit schleifen können als adjazenzmatrix als dreiecksmatrix gespeichert werden, da sie über die diagonale spiegelsymetrisch sind? somit speichert man (n^2 + n) / 2 matrizen-einträge, ja?

    2. ungerichtete graphen ohne mehrfachkanten ohne schleifen können gleich abgespeichert werden wobei man hypotenuse des dreiecks der dreiecksmatrix weglassen kann, womit dann der speicherbedarf auf n * (n - 1) / 2 elemente sinkt, ja?

    3. wenn man prüfen will ob zwei graphen isomorph zueinander sind und man sie als adjazenzmatrizen vorliegen hat, muss man dann nicht einfach prüfen ob zu jedem knoten ein äquivalent existiert welches die selben kanten zu den anderen knoten hat? sieht für mich nach O(n^2) aus.

    gruss



  • Bin mir unsicher, was du mit Schleifen meinst, deswegen unter Vorbehalt:

    1.) Ja.
    2.) Ja.
    3.) Nein, da Knoten anders benannt sein koennen.



  • asfdlol schrieb:

    3. wenn man prüfen will ob zwei graphen isomorph zueinander sind und man sie als adjazenzmatrizen vorliegen hat, muss man dann nicht einfach prüfen ob zu jedem knoten ein äquivalent existiert welches die selben kanten zu den anderen knoten hat? sieht für mich nach O(n^2) aus.

    Um das genauer auszuführen, was knivil gesagt hat: du kannst ja in einer adjazenzmatrix beliebige zeilen und spalten permutieren ohne den graphen zu ändern(=isomorph). Und nun ebtrachte den Graphen mit n Knoten in denen jeder Knoten genau k Kanten mit dem selben Wert hat und der Rest 0 ist.



  • knivil schrieb:

    Bin mir unsicher, was du mit Schleifen meinst, deswegen unter Vorbehalt:

    1.) Ja.
    2.) Ja.
    3.) Nein, da Knoten anders benannt sein koennen.

    danke für die antwort. mit schleife meine ich eine kante die vom knoten k zum knoten k führt. also sozusagen eine kante eines knotens zu sich selbst.
    das mit der anderen benennung ist mir klar aber man kann sieht die matrizeneinträge ja dennoch und kann dennoch schauen ob zwei zeilen gleich sind oder nicht. oder verstehe ich es gerade komplett falsch?



  • otze schrieb:

    asfdlol schrieb:

    3. wenn man prüfen will ob zwei graphen isomorph zueinander sind und man sie als adjazenzmatrizen vorliegen hat, muss man dann nicht einfach prüfen ob zu jedem knoten ein äquivalent existiert welches die selben kanten zu den anderen knoten hat? sieht für mich nach O(n^2) aus.

    Um das genauer auszuführen, was knivil gesagt hat: du kannst ja in einer adjazenzmatrix beliebige zeilen und spalten permutieren ohne den graphen zu ändern(=isomorph). Und nun ebtrachte den Graphen mit n Knoten in denen jeder Knoten genau k Kanten mit dem selben Wert hat und der Rest 0 ist.

    ahh, nun begreife ich. ja, dann ist das tatsächlich nicht effizient zu lösen. viele dank.

    edit: das bedeutet aber dass die laufzeit nicht nur von der menge der eingegeben knoten abhängig ist sondern auch mit der konstruktion des graphes abhängig ist, oder? bei dem von dir beschrieben graphen gibt es ja viele permutationen, bei gewissen anderen dürfte es gar keine geben wenn ich nicht wieder falsch liege.



  • ja, dann ist das tatsächlich nicht effizient zu lösen.

    Als kleine Ergänzung: Tatsächlich ist es ein offenes Problem, ob Graph-Isomorphismus (GI) effizient zu lösen ist, d.h. es ist weder bekannt ob GI in P ist oder ob GI NP-vollständig ist (vorausgesetzt P != NP).



  • ...wobei übrigens das oberflächlich recht ähnliche Subgraph-Isomorphismus-Problem dank der NP-Vollständigkeit von Hamilton-Kreis recht trivial NP-vollständig ist.


Log in to reply