Gráfok és hálózatok kezelése számítógéppel

Gráfok és hálózatok kezelése számítógéppel
2002-05-20T18:37:24+02:00
2003-01-07T01:32:08+01:00
2022-11-02T08:41:54+01:00
  • Van egy problémám gráfokkal, talán tudsz nekem segíteni.

    Adott két irányítatlan véges gráf.
    A csomópontok véges számú jellemzővel bírnak.

    A kérdés az, hogy benne van-e az egyik a másikban.
    Másképp megfogalmazva: ha az egyik gráfról leszedünk valmennyi csomópontot és élet, kaphatjuk-e a másikat.

    Van erre valamilyen elfogadott algoritmus?

    Írtam egy ilyen proggit, de nem vagyok biztos benne, hogy 100% -os eredményt produkál.
    A feladat erősen számításigényes (több millió gráfra kell elvégezni a keresést, és nem is csak egyszer) úgyhogy sebességre kell optimalizálni, a bruteforce nem kielégítő.
    Mutasd a teljes hozzászólást!
  • Köszönjük az érdeklődést. A gráf-sorozat mindkét szerzője a JATE-n végzett matematikus(ML1970,PP1985).Természetesen illett volna hivatkozni a Kruskal algoritmus eredeti előfordulási helyét, ahol az egzakt bizonyitás is megtalálható.De ez elég nehezen érhető el,másrészt úgy gondoljuk, hogy itt a PROg.hu-ban inkább a konstrukció érdekes, mint a gráfelméleti bizonyítás.Az algoritmus helyes, higyjük el.Marton L.
    Mutasd a teljes hozzászólást!
  • Korrekt a cikk. Gondolom, annak a bizonyítása elég bonyolult, hogy az algoritmussal valóban minimális feszítőfát kapunk :)
    (Te a JATE-ra jártál?)
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd