Numărarea drumurilor: ce schimbă un ciclu în graf
Precizează dacă nodurile pot fi repetate înainte de a număra traseele. Un ciclu poate produce infinit de multe parcurgeri numai în condițiile potrivite.
În acest material
Cuvântul „drum” este folosit uneori cu convenții diferite. Înainte să numeri posibilități într-un graf, trebuie să stabilești dacă ai voie să repeți noduri sau muchii și dacă există o limită a lungimii. Algoritmul depinde de aceste reguli.
Repetarea poate schimba un număr finit în infinit
Dacă ai voie să repeți muchii și poți intra într-un ciclu, îl poți parcurge de mai multe ori. Dar pentru trasee de la sursa S la destinația T, ciclul contează numai dacă este accesibil din S și din el se poate ajunge la T.
Un ciclu aflat într-o componentă complet separată nu produce trasee suplimentare între S și T. Nici un ciclu din care nu mai poți ajunge la T nu poate fi folosit într-un traseu complet cerut.
Exemplu cu o alegere repetabilă
Ai arcele S-A, A-B, B-A și A-T. Poți merge direct S-A-T sau poți repeta bucla A-B-A o dată, de două ori și așa mai departe înainte de A-T. Fără limită de lungime și cu repetări permise, există infinit de multe asemenea parcurgeri.
Dacă enunțul cere drumuri simple, adică fără repetarea nodurilor, aceste repetări nu sunt permise. Numărul devine finit, dar calcularea lui într-un graf general este o problemă diferită de o simplă propagare a unor sume.
Cu arcele S-A, A-B, B-A, A-T, putem repeta A-B-A înainte de destinația T. Dacă repetările sunt permise și lungimea nu este limitată, numărul traseelor este infinit.Mărește schema ↗
De ce grafurile aciclice sunt speciale
Un graf orientat aciclic nu conține cicluri orientate. Nodurile pot fi ordonate astfel încât fiecare arc să meargă înainte în acea ordine, numită topologică. Numărul de drumuri spre un nod poate fi propagat către succesorii lui după ce contribuțiile anterioare au fost calculate.
Dacă aplici aceeași recurență fără să tratezi ciclurile, valorile pot depinde circular unele de altele. O ordine arbitrară de parcurgere nu rezolvă această dependență. Mai întâi verifici premisa de aciclicitate sau alegi alt model.
O lungime fixată este altă problemă
Dacă ceri trasee cu exact k muchii, numărul este finit chiar dacă graful are cicluri, pentru un graf finit. Starea poate include numărul de pași efectuați. Aceasta nu este aceeași cerință cu toate traseele de orice lungime.
La citirea enunțului, subliniază repetarea, orientarea și limita de lungime. Aceste trei detalii decid sensul rezultatului înainte de alegerea structurii de date sau a tipului numeric.
Revezi componentele tare conexe, sortarea topologică și programarea dinamică.
Întrebări frecvente
Când există infinit de multe trasee între sursă și destinație?
Dacă repetarea este permisă fără limită și există un ciclu accesibil din sursă din care se poate ajunge la destinație. Ciclul poate fi repetat de oricâte ori înainte de continuarea traseului.
Orice ciclu din graf face numărul traseelor infinit?
Nu. Pentru perechea sursă-destinație, ciclul trebuie să fie pe o zonă accesibilă din sursă și din care destinația este accesibilă. Un ciclu separat nu contribuie.
De ce trebuie precizat dacă un drum poate repeta vârfuri?
Fără repetarea vârfurilor, numărul drumurilor simple într-un graf finit este finit, deși numărarea lor poate fi dificilă. Permiterea repetărilor schimbă atât răspunsul, cât și algoritmul.