|
Titlul: Problema NP-completa oare? Scris de: Parfene Narcis din Decembrie 06, 2011, 14:45:29 Salut,
As vrea sa ma ajutati cu un raspuns la problema urmatoare: Se da un graf conex si un nod in acest graf. Sa se verifice daca acest nod face parte sau nu dintr-un ciclu. Este aceasta o problema NP-completa? Sa stiu cum abordez rezolvarea. Multumesc! Titlul: Răspuns: Problema NP-completa oare? Scris de: Paul-Dan Baltescu din Decembrie 06, 2011, 15:14:47 Un nod intr-un graf nu face parte dintr-un ciclu daca si numai daca toate muchiile incidente sunt critice. Problema determinarii muchiilor critice are complexitate O(N+M).
Titlul: Răspuns: Problema NP-completa oare? Scris de: Savin Tiberiu din Decembrie 07, 2011, 11:25:52 De fapt nu cred ca trebuie sa calculezi muchiile critice. Cred ca daca faci un simplu DF din nodul respectiv, trebuie sa vezi daca exista vreo muchie de intoarcere incidenta cu nodul initial. Cred ca sunt echivalente solutia mea cu a lu paul, doar ca eu verific intr-o modalitate ceva mai simpla.
Titlul: Răspuns: Problema NP-completa oare? Scris de: Andrei Grigorean din Decembrie 07, 2011, 11:39:48 Tibi are dreptate, insa daca vrei sa afli pentru toate nodurile din graf daca aparatin vreunui ciclu trebuie sa determini muchiile critice.
|