Kako izracunati maksimalan broj putanja na nekom grafu?
Sad ne znam koliko bi vama koristilo da vam pastam kod iz c-a, al svejedno jedini problem koji pravi kod generisanja puteva jeste taj koliko zapravo putanja moze biti.
Trenutno sa cim program moze da mi radi je kad je graf jedna linija na kojoj se nalazi nekoliko tacaka stim da su povezane
1-2-3-4-5
Odnosno putevi koji se nalaze na grafu su :
1-2
2-3
3-4
4-5
Graf je usmeren pa je zapravo (1->2, 2->3...)
I sad maksimalan broj puteva koji se mogu generisati je lako naci...
5*4/2
Jedan način koji mi pada na pamet jeste da konstruišeš matricu susedstava , i za svako od do sabereš sve vrednosti u matrici . Ukupna suma biće broj koji tražiš.
Ako sam te dobro razumeo...
To bi bilo ovako...
1 tacka ima 2 suseda
2 tacka ima 2 suseda
3 tacka ima 2 suseda
4 tacka ima 3 suseda
5 tacka ima 1 suseda
Koliki je broj puteva u grafu koji je definisan kao :