Հիմնական նյութ
Համակարգչային գիտություն
Գրաֆիկների ներկայացում
Գրաֆիկները ներկայացնելու տարբեր եղանակներ կան՝ յուրաքանչյուրն իր լավ և վատ կողմերով։ Տարբեր իրավիճակներում կամ ալգորիթմներում, որտեղ գրաֆիկներն օգտագործում ենք որպես մուտքագրված արժեք, կարող ենք ստանալ տարբեր՝ լավ կամ վատ, օգտակար կամ անօգտակար արդյունքներ։ Այստեղ կտեսնենք գրաֆիկները ներկայացնելու երեք եղանակ։
Կկենտրոնանանք երեք չափանիշների վրա։ Առաջինն այն է, թե որքան հիշողություն է զբաղեցնում գրաֆը։ Դրա համար կօգտագործենք ասիմպտոտային նշագրում։ Այո, մենք կարող ենք ասիմպտոտային նշագրումը, աշխատելու ժամանակներ հաշվելուց բացի, այլ տեղերում էլ օգտագործել։ Դա ֆունկցիաները բնութագրելու լավ եղանակ է, իսկ ֆունկցիան իր հերթին կարող է բնութագրել աշխատելու ժամանակը, պահանջվող հիշողության քանակը և այլն։ Մյուս երկու չափանիշները կապված են ժամանակի հետ։ Մեկը՝ թե որքան ժամանակ է պետք հասկանալու համար՝ կողը գրաֆիկում է, թե ոչ։ Իսկ մյուսը՝ թե որքան ժամանակում կգտնենք գագաթի հարևաններին։
Տարածված է գագաթները գտնել ոչ թե անունով (Օդրի, Բոսթոն կամ սվիտեր), այլ թվով։ Այսինքն՝ մենք համարակալում ենք vertical bar, V, vertical bar գագաթները 0-ից vertical bar, V, vertical bar, minus, 1։ Ահա սոցիալական ցանցն իր 10 գագաթներով, որոնց մեջ անունների փոխարեն գրված են թվեր․
Կողերի ցուցակներ
vertical bar, E, vertical bar կող ունեցող գրաֆը ներկայացնելու պարզ եղանակ է ցուցակը, որն անվանում ենք կողերի ցուցակ։ Կողը ներկայացնելու համար մենք ունենք միայն գագաթի թվերի կամ կողերի օբյեկտների զանգված։ Եթե կողերն ունեն կշիռ, կա՛մ զանգվածին ավելացրու երրորդ տարր, կա՛մ տողի օբյեկտին տուր կողի կշռի արժեքը։ Քանի որ կողն ունի միայն երկու կամ երեք թիվ, կողերի ցուցակի ընդհանուր հիշողությունը \Theta, left parenthesis, E, right parenthesis է։ Օրինակ՝ այսպես կարող ես սոցիալական ցանցերի գրաֆիկի համար ներկայացնել կողերի ցուցակը JavaScript-ում․
[ [0{,}1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]Կողերի ցուցակները պարզ են, բայց եթե ուզում ենք գտնել, թե արդյոք գրաֆիկն ունի ինչ-որ կող, պետք է անցնենք կողերի վրայով, որ գտնենք այն։ Եթե կողերը ցուցակում դասավորված չեն, կատարում ենք գծային որոնում vertical bar, E, vertical bar կողի վրայով։ Մտածելու հարց: Ինչպե՞ս կարող ես դասավորել կողերի ցուցակը, որպեսզի ինչ-որ կողը գտնելու ժամանակը լինի O, left parenthesis, \lg, E, right parenthesis։ Պատասխանը մի փոքր շփոթեցնող է։
Կցման մատրիցներ
vertical bar, V, vertical bar գագաթներով գրաֆի համար կցման մատրիցը 0-ներով ու 1-երով vertical bar, V, vertical bar, dot, vertical bar, V, vertical bar մատրից է, որտեղ i-երորդ տողի j-երորդ սյան արժեքը 1 է այն դեպքում, երբ left parenthesis, i, comma, j, right parenthesis կողը գրաֆում է։ Եթե ուզում ես գտնել կողի կշիռը, այն կարող ես գրել i-երորդ տողի j-երորդ սյան մեջ և կշիռ չունեցող արժեքներում գրել
null, որը ցույց է տալիս, որ այդ կողը գոյություն չունի։ Ահա սոցիալական ցանցի գրաֆիկի կցման մատրիցը․JavaScript-ում մատրիցը ներկայացնում ենք այսպես՝
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]Կցման մատրիցով կարող ենք հաստատուն ժամանակում գտնել՝ արդյոք կողը գոյություն ունի, թե ոչ՝ ուղղակի ստուգելով մատրիցի համապատասխան վանդակում գրված թիվը։ Օրինակ, եթե կցման մատրիցի անունը
graph է, ապա կարող ենք հարցում կատարել, թե արդյոք left parenthesis, i, comma, j, right parenthesis կողը գրաֆում է, թե ոչ՝ սուգելով graph[i][j]-ը։ Ուրեմն ի՞նչն է կցման մատրիցի վատ կողմը։ Երկու վատ կողմ կա իրականում։ Առաջինը՝ այն զբաղեցնում է \Theta, left parenthesis, V, squared, right parenthesis տեղ, նույնիսկ երբ գրաֆը նոսր է․ ունի քիչ կողեր։ Այլ կերպ ասած՝ նոսր գրաֆի դեպքում ուղղակի 0-ներն են շատ, և մենք օգտագործում ենք շատ տեղ, որպեսզի ներկայացնենք քիչ կողեր։ Երկրորդը՝ եթե ուզում ես գտնել, թե որ գագաթներն են i գագաթին կից, պետք է անցնես i տողի բոլոր vertical bar, V, vertical bar վանդակների վրայով, նույնիսկ եթե քիչ քանակությամբ գագաթներ են i գագաթին կից։Ուղղություն չունեցող գրաֆում կցման մատրիցը սիմետրիկ է․ եթե i-երորդ տողի j-երորդ սյան վանդակը 1 է, ապա j-երորդ տողի i-երորդ սյան վանդակը նույնպես 1\ է։ Ուղղություն ունեցող գրաֆում այն սիմետրիկ չէ։
Կցման ցուցակներ
Գրաֆը կցման ցուցակներով ներկայացնելը միավորում է կցման մատրիցները կողերի ցուցակների հետ։ Ամեն i գագաթի համար պահեստավորիր դրան կից գագաթների զանգվածը։ Մենք ունենք vertical bar, V, vertical bar կցման ցուցակների զանգված՝ ամեն գագաթի համար մեկ կցման ցուցակ։ Ահա սոցիալական ցանցի գրաֆիկի կցման ցուցակի տեսքը․
JavaScript-ում այս կցման ցուցակները ներկայացնում ենք այսպես՝
[ [1, 6, 8],
[0, 4, 6, 9],
[4, 6],
[4, 5, 8],
[1, 2, 3, 5, 9],
[3, 4],
[0, 1, 2],
[8, 9],
[0, 3, 7],
[1, 4, 7] ] Պարտադիր չէ, որ գագաթների թվերը կցման ցուցակում լինեն ինչ-որ հերթականությամբ, բայց լավ է դրանք աճման կարգով դասավորելը, ինչպես ցույց է տրված այս օրինակում։
Կարող ենք ամեն գագաթի կցման ցուցակը գտնել հաստատուն ժամանակում, քանի որ պետք է միայն գտնել ցուցիչը։ Գտնելու համար, թե արդյոք left parenthesis, i, comma, j, right parenthesis գագաթը կա գրաֆիկում, հաստատուն ժամանակում գտնում ենք i-ի կցման ցուցակն ու փնտրում j-ն i-ի կցման ցուցակում։ Որքա՞ն կլինի սա գտնելու վատագույն ժամանակը։ Պատասխանն է՝ \Theta, left parenthesis, d, right parenthesis, որտեղ d-ն i գագաթի աստիճանն է, քանի որ այդքան է i-ի կցման ցուցակի երկարությունը։ i գագաթի աստիճանը կարող է լինել ընդհուպ մինչև vertical bar, V, vertical bar, minus, 1 (եթե i-ն կից է բոլոր մյուս vertical bar, V, vertical bar, minus, 1 գագաթներին) կամ 0 (եթե i-ն չունի կից գագաթներ)։ Ուղղություն չունեցող գրաֆում, եթե j գագաթը i-ի կցման ցուցակում է, ապա i գագաթը j-ի կցման ցուցակում է։ Եթե գրաֆը կշիռ ունեցող է, ապա յուրաքանչյուր կցման ցուցակի ամեն մի տարրը պետք է լինի կամ երկանդամ զանգված, կամ օբյեկտ, որը գագաթին տալիս է գագաթի թիվ ու կողի կշիռ։
for ցիկլով կարող ես անցնել կցման ցուցակի գագաթների վրայով։ Օրինակ՝ պատկերացրու՝ ունես կցման ցուցակի տեսքով ֆունկցիա՝ վերագրված
graph փոփոխականով, հետևաբար graph[i]-ը զանգված է, որտեղ i գագաթի հարևան գագաթներն են։ Հետո կանչում ենք doStuff ֆունկցիան i-ին կից բոլոր գագաթների վրա։ Կարող ես օգտագործել այս JavaScript կոդը․for (var j = 0; j < graph[i].length; j++) {
doStuff(graph[i][j]);
}Եթե երկփակագիծ նշագրումը շփոթեցնում է, կարող ես կոդն այսպես գրել՝
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
doStuff(vertex[j]);
}Որքա՞ն տեղ են զբաղեցնում կցման ցուցակները։ Ունենք vertical bar, V, vertical bar ցուցակ, և չնայած որ յուրաքանչյուր ցուցակը կարող է ունենալ ընդհուպ մինչև vertical bar, V, vertical bar, minus, 1 գագաթ, ուղղություն չունեցող գրաֆի կցման ցուցակներն ընդհանուր պարունակում են 2, vertical bar, E, vertical bar տարր։ Ինչո՞ւ 2, vertical bar, E, vertical bar։ Ամեն left parenthesis, i, comma, j, right parenthesis կողը կցման ցուցակներում հայտնվում է երկու անգամ՝ մեկ անգամ i-ի ցուցակում և մեկ անգամ j-ի ցուցակում, իսկ կողերի քանակը vertical bar, E, vertical bar է։ Ուղղություն ունեցող գրաֆում կցման ցուցակներն ունեն ընդհանուր vertical bar, E, vertical bar տարր՝ յուրաքանչյուր կողի համար մեկ հատ։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։