Ամենաերկար ճանապարհի խնդիր

Գրաֆերի տեսության մաթեմատիկական կարգապահությունում, **ամենաերկար ճանապարհի խնդիրը** տրված գրաֆում մաքսիմալ երկարությամբ պարզ ճանապարհը գտնելու խնդիրն է։ Այդ ճանապարհը կոչվում է պարզ, եթե այն չունի մի քանի կրկնվող գագաթներ։ Ի տարբերություն ամենակարճ ճանապարհի խնդրի, որն օգտագործվում է գտնելու 2 գագաթների միջև ամենակարճ ճանապարհը և կարող էր լուծվել պոլինոմիալ ժամանակում այն գրաֆերում, որոնք չունեն բացասական զանգված ունեցող ցիկլեր, այս խնդրի լուծման տարբերակը NP-ամբողջությունն է, որը նշանակում է, որ օպտիմալ լուծումը չի գտնվի պոլինոմիալ ժամանակում, եթե&nbsp;P&nbsp;=&nbsp;NP.

այս խնդրի լուծման ստանդարտ տարբերակի դեպքում պետք է հաշվի առնել, արդյոք այդ գրաֆը պարունակում է *k*ից մեծ կամ հավասար երկարությամբ պարզ ճանապարհ, որտեղ ճանապարհի երկարությունը պետք է հավասար լինի ճանապարհին եղած գագաթների թվին։

## NP-ամբողջություն
Խնդրի լուծման NP-ամբողջությունը կարող է ցուցադրվել, եթե օգտագործենք Համիլթոնյան ճանապարհի խնդրի կրճատումը։ Իսկապես, եթե որոշակի ընդհանուր գրաֆ ունի համիլթոնյան ճանապարհ, այս ճանապարհը հնարավոր ամենաերկար ճանապարհն է, քանի որ այն անցնում է բոլոր հնարավոր գագաթներով։ Համիլթոնյան ճանապարհի խնդիրը լուծելու համար՝օգտագործելով ամենաերկար ճանապարհի ալգորիթմը, մենք օգտագործում ենք այդ ալգորիթմը միևնույն մուտքագրված գրաֆի համար և տեղադրում ենք *k*=|*V*|, որը գրաֆում եղած գագաթների թիվն է։

Եթե գրաֆում կա համիլթոնյան ճանապարհ, ապա ալգորիթմը կվերադարձնի*այո*, քանի որ համիլթոնյան ճանապարհի երկարությունը հավասար է |*V*|։ Հակառակ դեպքում, երբ ալգորիթմը դուրս բերի*այո*, դա նշանակում է, որ գրաֆում կա |*V*| երկարությամբպարզ ճանապարհ։ Քանի որ դա|*V*| երկարությամբ պարզ ճանապարհն է, հետևաբար դա այն ճանապարհն է, որն անցնում է գրաֆի բոլոր գագաթներով առանց կրկնության, և դա ճշգրտության համիլթոնյան ճանապարհն է։

Քանի որ համիլթոնյան ճանապարհի խնդիրը NP-ամբողջությունն է, սա ցույց է տալիս, որ այս խնդիրը NP-բարդ է։ Ցույց տալու համար, որ դա NP-ամբողջություն է, պետք է նաև ցույց տանք, որ այս խնդիրը NP-ում է։ Դա հեշտ է տեսնել, սակայն, քանի որ վկայականը *այո*-տարածության համար *k* երկարությամբ ճանապարհի նկարագրություննէ։

## Ամենակարճ ճանապարհի խնդրի հետ կապը
Ամենաերկար ճանապարհի խնդիրը կարող է վերածվել ամենակարճ ճանապարհի խնդրի (չնայած, որ գրաֆը կարող է ունենալ բացասական զանգվածով ցիկլեր), կիրառելով օպտիմալացման երկակիությունը (դրական մեծության մաքսիմալացումը նույննէ, ինչ որ բացասական մեծության մինիմալացումը)։ Եթե ամենաերկար ճանապարհի խնդրի մուտքագրված գրաֆը*G* է, իսկ ամենակարճ պարզ ճանապարհինը՝ *H*, որը լրիվ նույնն է, ինչ որ *G*-ն, բայց բացասական եզրային զանգվածներով, դա ամենաերկար պարզ ճանապարհն է*G*-ում։ Սակայն, օրիգինալ*G* գրաֆի որոշ դրական զանգված ունեցող ցիկլեր տանում են դեպի *H*-ի բացասական զանգված ունեցող ցիկլեր։ Բացասական զանգված ունեցող ցիկլերով գտնելով ամենակարճ պարզ ճանապարհը գրաֆում՝ կարող ենք ասել, որ NP-ամբողջություն ունենք։ Եթե *G*-ն ցիկլեր չի պարունակում, ապա *H*-ը չի ունենա բացասական զանգվածով ցիկլեր և ամենակարճ ճանապարհը գտնելու ալգորիթմը չի կարող օգտագործվել *H*-ում պոլինոմիալ ժամանակում օրիգինալ խնդրի լուծման համար։ Այսպիսով, ամենաերկար ճանապարհի խնդիրը հեշտ է լուծել ացիկլիկ գրաֆերում։

## Ալգորիթմներ ացիկլիկ գրաֆերի համար
Ինչպես նշվեց վերևում, ամենաերկար ճանապարհի խնդիրը ացիկլիկ գրաֆերում կարող է լուծվել պոլինոմիալ ժամանակում՝ բացասականացնելով եզրային զանգվածները և կիրառելով ամենակարճ ճանապարհը գտնելու ալգորիթմը։ Վերոնշյալ ալգորիթմը չի օգտագործում այս կրճատումը և հասնում է կոմպլեքսության ավելի լավ ժամանակում։

### Կշռված ուղղված ացիկլիկ գրաֆեր
մինի|Պարզ DAG-ը շերտերի հեռավորության հետ, կարմիրը ամենաերկար ճանապարհն է նախորդ շետերի և ամենաերկար եզրի միջև դեպի ընթացիկ գագաթը, որը նշված է (6)-ով։
Եթե *G*-ն ուղղված ացիկլիկ գրաֆն է, ամենաերկար ճանապարհի խնդիրը *G*-ում կարող է լուծվել գծային ժամանակում՝օգտագործելով դինամիկ ծրագրավորումը։ Ենթադրում ենք, որ topOrder(G)-ի ելքերը գագաթների հերթականությունն է տոպոլոգիական կարգով (Սա կարող է հաշվվել տոպոլոգիական տեսակավորման միջոցով, և այս քայլը պահանջում է, որ մուտքագրված գրաֆը լինի ուղղված ացիկլիկ գրաֆ)։ Բացի այդ, թույլ տանք, որ*V*(*G*)-ն դրված լինի *G*-ի գագաթներում և*E*(*G*)-ն տեղադրված լինի *G*-ի եզրերում և, երբ զանգվածները սահմանված են, թույլ տանք, որ (*G*,&nbsp;*e*) զանգվածը լինի *e*-ի եզրային զանգվածը *G*գրաֆում(եթե գրաֆը կշռված չէ, մտցնել 0-ից տարբեր ցանկացած հաստատուն &nbsp;(*G*,*e*)) զանգվածի մի քանի դեպքերի համար։ Հետո հետևյալ ալգորիթմը հաշվում է ամենաերկար ճանապարհի երկարությունը։

 **algorithm** dag-longest-path **is**
 **input**։ 
 Directed acyclic graph G
 **output**։ 
 Length of the longest path
 
 length_to = array with |V(G)| elements of type int with default value 0
 
 **for each** vertex v **in** topOrder(G) **do**
 **for each** edge (v, w) **in** E(G) **do**
 **if** length_to[w] <= length_to[v] + weight(G, (v, w)) **then**
 length_to[w] = length_to[v] + weight(G, (v, w))
 
 return max(length_to[v] for v in V(G))

Ճշտությունը կարող է ստուգվել հետևյալ կերպ՝ նախ բոլոր գագաթները պետք է ունենան 0 հեռավորություն գլխավոր գագաթից, իսկ հետո բոլոր գագաթները պետք է ունենան 1 հեռավորությունը գլխավոր գագաթից...։ Յուրաքանչյուր գագաթի համար այն իրոք ունի մաքսիմալ երկարությամբ ճանապարհ, որը բաղկացած է գլխավոր գագաթին ավելի մոտ գտնվող շերտերի միջև ամենամեծ երկարությունն ունեցող ճանապարհներից։ Այս ձևով, ամենաերկար ճանապարհով մի հանգույցը կապվում է մյուսին։
length_to(*w*)&nbsp;=&nbsp;max(weight(*G*,&nbsp;(*v*,&nbsp;*w*))&nbsp;+&nbsp;length_to(*v*)) for all edges (v, w) in G,

Այս ալգորիթմի գործարկման ամենավատ ժամանակը սա է. O(*T*&nbsp;+&nbsp;|*V*|&nbsp;+&nbsp;|*E*|&nbsp;+&nbsp;|V|), եթե *T*-ն տոպոլոգիական կանոնի կողմից պահանջված ժամանակն է։ Տոպոլոգիական կանոնի հաշվարկման համար ընտրում ենք ստանդարտ ալգորիթմ, որի պարզեցված տեսքն այսպիսինն է
O(|*V*|&nbsp;+&nbsp;|*E*|&nbsp;+&nbsp;|*V*|&nbsp;+&nbsp;|*E*|&nbsp;+&nbsp;|*V*|), որը պարզեցնում է հերթականները O(|*V*|&nbsp;+&nbsp;|*E*|).

Բացի այդ, երկարացնելով այս ալգորիթմը՝ կարող ենք հաշվել նաև իրական ճանապարհը։ Սա անելու համար անհրաժեշտ է ներկայացնել նախորդ(կամ փոխարինող)-դասավորությունը, որը թարմացվում է ամնե անգամ, երբ length_to-ն փոփոխվում է։ Սա անելով, ինչ-որ մեկը կարող է վերակառուցել ուղղված ացիկլիկ գրաֆի գլխավոր գագաթից դուրս եկող ճանապարհը և հենց մաքսիմալ երկարության ճանապարհը վերակառուցվի, դա կդառնա մեկը ամենաերկար ճանապարհներից։

## Աղբյուր
* Հոդվածի սկզբնական տարբերակը թարգմանվել է անգլերեն վիքիպեդիայի համանուն հոդվածից։

## Մանրամասն հղումներ
* NP-Completeness
* Source of the algorithm

Կատեգորիա:Գրաֆների տեսություն
Կատեգորիա:Գրաֆների ալգորիթմներ