Gráf-izomorfizmus

Címkék
Gráf-izomorfizmus
2005-01-12T23:49:13+01:00
2005-01-14T01:12:02+01:00
2022-11-01T05:40:39+01:00
  • Hat, ha iranyitott korok nincsenek csak (magyarul az iranyitott graf aciklikus), akkor GI-teljes a kerdes, polinomialis algoritmust tehat nem lesz konnyu talalni. Kicsit kar, hogy nem faid vannak, ma reggel a biciklin kitalaltam egy jo kis algoritmust fakra.

    Egyebkent nem vagyok igazan otthon a kerdesben, fog. sincs, hogy melyik lenne a state-of-the-art legjobb algoritmus. Nyilvan attol is fugg, milyen inputra teszteled. Sok sikert a keresgeleshez!
    --borogass
    Mutasd a teljes hozzászólást!
  • Itt találtam valami használható-féleséget, ha érdekel:

    1.5.9 Graph Isomorphism

    De ez általános gráfokra csinálja. Viszont nagyon büszke rá, hogy milyen hatékony. Egyébként igen, irányított kör- mentes (így sajnos nem feltétlenül fa).
    Mutasd a teljes hozzászólást!
  • Tutti biztos vagy benne? En ugy tudom, hogy az altalanos graf-izomorfizmus problemarol (es egy csomo spec esete, pl. paros grafokra) azt sejtik, hogy nem P-beli, de nem is NP-teljes. Szerintem ez nyitott kerdes, ugyhogy ha a te grafjaidra NP-teljes volna, akkor megcafoltad a 30 eves sejtest. Persze nem lehetetlen, de ugye nem haragszol, ha ketelkedem ... Egyebkent egy problemat GI-teljesnek neveznek, ha legalabb olyan nehez, mint az (altalanos) graf-izomorfizmus problema.

    A kormentes alatt azt erted, hogy nincs benne iranyitott kor, vagy hogy a graf egy iranyitott fa? Az elobbi esetben a sejtes szerint se nem P-beli, se nem NP-teljes (azaz keresgelhetsz jo kis heurisztikakat). Fak izomoriaja viszont allitolag eldontheto polinomidoben (linearis) idoben [lasd: AV Aho, JE Hopcroft, and JD Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.; illetve google]. Azt nem tudom, mukodik-e iranyitott fakra is, meg kellene nezni. Vagy meg jobb lenne kitalalni
    --borogass
    Mutasd a teljes hozzászólást!
  • Ezer bocsánat!!
    Nem gondoltam, hogy a sejtésem ily hamar beigazolódik. Ebbizony NP-teljes probléma.
    Mutasd a teljes hozzászólást!
  • Csókolom!
    Az lenne a problémám, hogy két irányított gráfról kellene eldöntenem (amiket az adjacencia mátrixukkal reprezentálok, C-ben), hogy izomorfak-e. Tud valaki egy hatékonyabb algoritmust annál, minthogy legenerálom az összes közöttük menő izomorfizmust?
    Ha segít, a gráfok körmentesek, és részbenrendezést reprezentálnak.
    Mutasd a teljes hozzászólást!
Címkék
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd