Հիմնական նյութ

Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 1

Դաս 10: Գրաֆիկներ

Գրաֆիկների ներկայացում

Գրաֆիկները ներկայացնելու տարբեր եղանակներ կան՝ յուրաքանչյուրն իր լավ և վատ կողմերով։ Տարբեր իրավիճակներում կամ ալգորիթմներում, որտեղ գրաֆիկներն օգտագործում ենք որպես մուտքագրված արժեք, կարող ենք ստանալ տարբեր՝ լավ կամ վատ, օգտակար կամ անօգտակար արդյունքներ։ Այստեղ կտեսնենք գրաֆիկները ներկայացնելու երեք եղանակ։

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

Տարածված է գագաթները գտնել ոչ թե անունով (Օդրի, Բոսթոն կամ սվիտեր), այլ թվով։ Այսինքն՝ մենք համարակալում ենք

| V |

գագաթները 0-ից

| V | - 1

։ Ահա սոցիալական ցանցն իր 10 գագաթներով, որոնց մեջ անունների փոխարեն գրված են թվեր․

Կողերի ցուցակներ

| E |

կող ունեցող գրաֆը ներկայացնելու պարզ եղանակ է ցուցակը, որն անվանում ենք կողերի ցուցակ։ Կողը ներկայացնելու համար մենք ունենք միայն գագաթի թվերի կամ կողերի օբյեկտների զանգված։ Եթե կողերն ունեն կշիռ, կա՛մ զանգվածին ավելացրու երրորդ տարր, կա՛մ տողի օբյեկտին տուր կողի կշռի արժեքը։ Քանի որ կողն ունի միայն երկու կամ երեք թիվ, կողերի ցուցակի ընդհանուր հիշողությունը

Θ (E)

է։ Օրինակ՝ այսպես կարող ես սոցիալական ցանցերի գրաֆիկի համար ներկայացնել կողերի ցուցակը 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] ]

Կողերի ցուցակները պարզ են, բայց եթե ուզում ենք գտնել, թե արդյոք գրաֆիկն ունի ինչ-որ կող, պետք է անցնենք կողերի վրայով, որ գտնենք այն։ Եթե կողերը ցուցակում դասավորված չեն, կատարում ենք գծային որոնում

| E |

կողի վրայով։ Մտածելու հարց: Ինչպե՞ս կարող ես դասավորել կողերի ցուցակը, որպեսզի ինչ-որ կողը գտնելու ժամանակը լինի

O (\lg E)

։ Պատասխանը մի փոքր շփոթեցնող է։

Կցման մատրիցներ

| V |

գագաթներով գրաֆի համար կցման մատրիցը 0-ներով ու 1-երով

| V | \cdot | V |

մատրից է, որտեղ

i

-երորդ տողի

j

-երորդ սյան արժեքը 1 է այն դեպքում, երբ

(i, j)

կողը գրաֆում է։ Եթե ուզում ես գտնել կողի կշիռը, այն կարող ես գրել

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 է, ապա կարող ենք հարցում կատարել, թե արդյոք

(i, j)

կողը գրաֆում է, թե ոչ՝ սուգելով graph[i][j]-ը։ Ուրեմն ի՞նչն է կցման մատրիցի վատ կողմը։ Երկու վատ կողմ կա իրականում։ Առաջինը՝ այն զբաղեցնում է

Θ (V^{2})

տեղ, նույնիսկ երբ գրաֆը նոսր է․ ունի քիչ կողեր։ Այլ կերպ ասած՝ նոսր գրաֆի դեպքում ուղղակի 0-ներն են շատ, և մենք օգտագործում ենք շատ տեղ, որպեսզի ներկայացնենք քիչ կողեր։ Երկրորդը՝ եթե ուզում ես գտնել, թե որ գագաթներն են

i

գագաթին կից, պետք է անցնես

i

տողի բոլոր

| V |

վանդակների վրայով, նույնիսկ եթե քիչ քանակությամբ գագաթներ են

i

գագաթին կից։

Ուղղություն չունեցող գրաֆում կցման մատրիցը սիմետրիկ է․ եթե

i

-երորդ տողի

j

-երորդ սյան վանդակը 1 է, ապա

j

-երորդ տողի

i

-երորդ սյան վանդակը նույնպես 1\ է։ Ուղղություն ունեցող գրաֆում այն սիմետրիկ չէ։

Կցման ցուցակներ

Գրաֆը կցման ցուցակներով ներկայացնելը միավորում է կցման մատրիցները կողերի ցուցակների հետ։ Ամեն

i

գագաթի համար պահեստավորիր դրան կից գագաթների զանգվածը։ Մենք ունենք

| V |

կցման ցուցակների զանգված՝ ամեն գագաթի համար մեկ կցման ցուցակ։ Ահա սոցիալական ցանցի գրաֆիկի կցման ցուցակի տեսքը․

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] ]

Պարտադիր չէ, որ գագաթների թվերը կցման ցուցակում լինեն ինչ-որ հերթականությամբ, բայց լավ է դրանք աճման կարգով դասավորելը, ինչպես ցույց է տրված այս օրինակում։

Կարող ենք ամեն գագաթի կցման ցուցակը գտնել հաստատուն ժամանակում, քանի որ պետք է միայն գտնել ցուցիչը։ Գտնելու համար, թե արդյոք

(i, j)

գագաթը կա գրաֆիկում, հաստատուն ժամանակում գտնում ենք

i

-ի կցման ցուցակն ու փնտրում

j

-ն

i

-ի կցման ցուցակում։ Որքա՞ն կլինի սա գտնելու վատագույն ժամանակը։ Պատասխանն է՝

Θ (d)

, որտեղ

d

-ն

i

գագաթի աստիճանն է, քանի որ այդքան է

i

-ի կցման ցուցակի երկարությունը։

i

գագաթի աստիճանը կարող է լինել ընդհուպ մինչև

| V | - 1

(եթե

i

-ն կից է բոլոր մյուս

| V | - 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]);
}

Որքա՞ն տեղ են զբաղեցնում կցման ցուցակները։ Ունենք

| V |

ցուցակ, և չնայած որ յուրաքանչյուր ցուցակը կարող է ունենալ ընդհուպ մինչև

| V | - 1

գագաթ, ուղղություն չունեցող գրաֆի կցման ցուցակներն ընդհանուր պարունակում են

2 | E |

տարր։ Ինչո՞ւ

2 | E |

։ Ամեն

(i, j)

կողը կցման ցուցակներում հայտնվում է երկու անգամ՝ մեկ անգամ

i

-ի ցուցակում և մեկ անգամ

j

-ի ցուցակում, իսկ կողերի քանակը

| E |

է։ Ուղղություն ունեցող գրաֆում կցման ցուցակներն ունեն ընդհանուր

| E |

տարր՝ յուրաքանչյուր կողի համար մեկ հատ։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Մուտք գործել

Դասակարգել ըստ

Առայժմ հրապարակումներ չկան։

Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: