Lant graf

[•Syad]

Ma poate ajuta si pe mine cineva cu conditia de verificare a unui lant intr-un graf?Adica daca exista sau nu.Multumesc

[•Mishu91]

Ce înțelegi printr-un lanț? Că un lanț poate fi format și dintr-o muchie și atunci în orice graf în care există cel puțin o muchie există lanț.

[•Syad]

Nu specifica, dar banuiesc ca trebuie sa fie minim 3 varfuri.

[•Mishu91]

De unde este problema?

[•Syad]

Nu este o problema...este o cerinta...vrea sa fie un fel de algoritm care trebuie stiut.

[•Mishu91]

Nu este o problema...este o cerinta...vrea sa fie un fel de algoritm care trebuie stiut.

Și unde ai întâlnit-o, în ce context?

[•Syad]

Poi asa suna."Verificare conditie lant"

[•skyel]

Probabil se refera la existenta unui drum intr-un graf de la un nod i la un nod j. Caz in care ai putea sa faci o parcurgere a grafului.

[•nparfene2004]

Considerand lantul D = d[1], d[2], ..., d[k] si graful dat prin matricea de adiacenta a,
o verificare daca D este lant in graf s-ar face cam asa:

Cod:

int eLant = 1 ;
for (i=1; i<k ; i++)
   if (a[d[i]][d[i+1]] == 0)
	e_lant = 0 ;

if (eLant == 1) cout<<"este lant" ;
  else cout<<"Nu este lant" ;

Editat de moderator: Pentru tagul code trebuie sa pui paranteze patrate, adica [], nu <>.

[•chera_lary]

Nu neaparat! Ca sa fie adevarat ceea ce spui tu, nodurile trebuie sa fie consecutive! Ar putea exista lant 1-5-3-7-9;
Ca sa verifici daca exita lant de la un nod x la un nod y, aplici o parcurgere df sau bf incepand cu unul din nodurile x sau y si retii intr-un vector fie el s, nodurile vizitate!
Daca ai aplicat parcurgerea incepand cu x, verifici sa vezi daca s[y] == 1. Daca da atunci exista drum de la x la y.

[•alexandru92]

Toate nodurile din D sunt adiacente doua cate doua. Te las pe tine sa vezi de ce

[•Mishu91]

Este foarte amuzant că fiecare încearcă să ghicească enunțul problemei. Totuși, pune un link sau spune-ne sursa unde ai găsit problema, dacă vrei să fii ajutat.

[•pauldb]

Cred ca va impacientati degeaba. Mie imi suna a tema primita la facultate si cam toate temele de acolo suna asa.

[•Syad]

Nu este tema de facultate, este o posibila cerinta la teza de clasa a 11-a pe care o dau marti.

Se poate inchide, am rezolvat.

[editat de moderator] evita sa postezi consecutiv