Գրաֆիկների նկարագրություն

Ահա սոցիալական ցանցը ներկայացնելու մի եղանակ․

Երկու մարդու միջև գիծը նշանակում է, որ նրանք իրար ճանաչում են։ Եթե երկու անունի միջև գիծ չկա, ապա նրանք անծանոթ են։ Իրար ճանաչելու կապը փոխադարձ է, այսինքն, եթե Էնդրյուն գիտի Գեյլին, ուրեմն Գեյլն էլ ճանաչում է Էնդրյուին։

Այս սոցիալական ցանցը կոչվում է գրաֆ։ Անունները գրաֆի գագաթներն են (եթե խոսում ենք միայն մեկի մասին, այն կոչվում է գագաթ)։ Յուրաքանչյուր գիծը, որ միավորում է երկու գագաթները, կոչվում է կող։ $u$u և $v$v գագաթները միավորող կողը նշանակում ենք $(u,v)$left parenthesis, u, comma, v, right parenthesis զույգով։ Քանի որ «իրար ճանաչելու» կապը փոխադարձ է, գրաֆը ուղղություն չունի։ Ուղղություն չունեցող $(u,v)$left parenthesis, u, comma, v, right parenthesis կողը նույնն է, ինչ $(v,u)$left parenthesis, v, comma, u, right parenthesis-ն։ Հետագայում կտեսնենք ուղղություն ունեցող գրաֆեր, որտեղ երկու կետի միջև հարաբերակցությունը ոչ միշտ է փոխադարձ։ Ուղղություն չունեցող գրաֆում երկու կետի միջև ընկած կողը, ինչպես, օրինակ՝ Էնդրյուի ու Գեյլի կողը, կոչվում է երկու գագաթի պատահար, և մենք ասում ենք, որ կողով միացված երկու գագաթ կից են կամ հարևան են։ Գագաթի վրա կողերի քանակը կոչվում է գագաթի աստիճան։

Էնդրյուն ու Ֆրենկը չեն ճանաչում իրար։ Պատկերացնենք՝ Ֆրենկին ուզում ենք ծանոթացնել Էնդրյուի հետ։ Ինչպե՞ս կարող ենք ծանոթացնել։ Նա գիտի Էմիլիին, ով գիտի Բիլին, ով էլ գիտի Էնդրյուին։ Մենք ասում ենք, որ Ֆրենկի ու Օդրիի միջև կա երեք կող ունեցող ճանապարհ։ Իրականում սա Ֆրենկի ու Օդրիի միջև ամենակարճ ճանապարհն է․ երեքից ավելի քիչ կող ունեցող ճանապարհ չկա նրանց միջև։ Երկու գագաթի միջև այդ ճանապարհն անվանում ենք ամենակարճ ճանապարհ։ Ահա այդ ճանապարհը՝ ընդգծված․

Երբ ճանապարհը գնում է ինչ-որ գագաթից դեպի նույն գագաթը, կոչվում է շրջան։ Սոցիալական ցանցն ունի շատ շրջաններ․ դրանցից մեկը, օրինակ, գնում է Էնդրյուից Բիլ, Բիլից Էմիլի, Էմիլիից Ջեֆ, Ջեֆից Հարրի, Հարրիից Իլանա, և Իլանայից հետ դեպի Էնդրյու։ Կա ավելի կարճ Էնդրյուի շրջան, որը ցույց է տրված ներքևում․ Էնդրյուից Բիլ, Բիլից Գեյլ, Գեյլից Էնդրյու։ Ի՞նչ շրջաններ կարող ես գտնել դու։

Երբեմն կողերի վրա թվեր ենք գրում։ Օրինակ՝ սոցիալական ցանցի օրինակում կարող ենք գրել, թե որքան լավ են ճանաչում երկու հոգին միմյանց։ Այլ օրինակ է քաղաքների քարտեզի գրաֆը։ Քանի որ քաղաքներն իրար փոխադարձաբար են կից, քարտեզն ուղղություն չունեցող գրաֆ է, որտեղ քաղաքները գագաթներն են, իսկ նրանց միավորող ճանապարհները՝ կողերը, որոնք ցույց են տալիս մի քաղաքից մյուսը հեռավորությունը։ Ահա այդպիսի մի օրինակ, որ ցույց է տալիս ԱՄՆ-ի հյուսիսարևելյան քաղաքներն ու դրանց կապող մայրուղիները, որոնց վրա գրված է հեռավորությունը․

Կողի վրա գրված թիվն անվանում ենք կշիռ, հետևաբար այդ գրաֆերը կոչվում են կշիռ ունեցող գրաֆեր։ Քարտեզի օրինակում մի կետից մյուսն ամենակարճ հեռավորությունը գտնելու համար գումարում ենք դրանց միացնող կողերի կշիռները, ոչ թե կողերի քանակը։ Կշիռ ունեցող գրաֆերում այն անվանում ենք ամենակարճ ճանապարհ։ Օրինակ՝ այս գրաֆում Նյու Յորքից Քոնքորդ ամենակարճ ճանապարհը ձգվում է Նյու Յորքից դեպի Նյու Հեյվն, հետո՝ Հարթֆորդ, հետո՝ Սթարբրիջ, Ուեսթոն, Ռեդինգ, հետո նոր Քոնքորդ՝ ընդհանուր կազմելով 289 մղոն ճանապարհ։

Երկու գագաթի միջև կապը միշտ չէ, որ փոխադարձ է։ Օրինակ՝ քարտեզի գրաֆում կարող են լինել միակողմանի փողոցներ։ Կամ ահա գրաֆ, որը ցույց է տալիս, թե ինչ հերթականությամբ է հոկեյի դարպասապահը հագնում իր համազգեստը․

Այստեղի կողերը, որոնք սլաքներ են, ունեն ուղղություն, և մենք ունենք ուղղություն ունեցող գրաֆ։ Այստեղ ուղղությունները ցույց են տալիս, թե ինչից հետո ինչ պետք է հագնել։ Օրինակ՝ կրծքավանդակի պահոցից (chest pad) սվիտեր (sweater) սլաքը ցույց է տալիս, որ դարպասապահը պահոցն է հագնում, հետո սվիտերը։ Գագաթների վրա գրված թվերը ցույց են տալիս հագնելու հերթականությունը, այսինքն՝ դարպասապահը վարտիքը հագնում է սկզբում, հետո՝ գուլպաները, հետո սեղմող գուլպաները, և այսպես շարունակ, մինչև ամենավերջում՝ արգելափակիչը։ Գուցե արդեն նկատել ես, որ այս գրաֆը չունի շրջաններ․ այսպիսի գրաֆերն անվանում ենք ուղղություն ունեցող անշրջան գրաֆեր։ Իհարկե, կարող ենք ունենալ նաև կշիռ և ուղղություն ունեցող գրաֆեր, օրինակ՝ քաղաքի քարտեզի գրաֆ միակողմանի ճանապարհներով ու հեռավորություններով։

Ուղղություն ունեցող կողերի համարուրիշ տերմիններ ենք օգտագործում։ Ասում ենք, որ կողը լքում է մի գագաթն ու մտնում է մեկ ուրիշը։ Օրինակ՝ կողը լքում է կրծքավանդակի պահոցի գագաթն ու մտնում է սվիտերի գագաթը։ Եթե ուղղություն ունեցող կողը լքում է $u$u գագաթն ու մտնում է $v$v գագաթ, այն նշանակում ենք $(u,v)$left parenthesis, u, comma, v, right parenthesis-ով, և գագաթների հերթականությունն այստեղ արդեն կարևոր է։ Գագաթը լքող կողերի քանակն անվանում ենք լքելու աստիճան, իսկ գագաթ մտնող կողերի քանակը՝ մտնելու աստիճան։

Ինչպես տեսնում ես, գրաֆերը՝ և՛ ուղղություն ունեցող, և՛ չունեցող, իրական աշխարհում հարաբերակցություններ մոդելավորելու բազում կիրառումներ ունեն։

Երբ աշխատում ենք գրաֆերի հետ, օգտակար է իմանալ գագաթների ու կողերի քանակն ու կշիռը։ Սովորաբար գագաթը նշանակում ենք $V$V-ով, իսկ կողը՝ $E$E-ով։ Երբ ներկայացնում ենք գրաֆը կամ դրա վրա ալգորիթմ ենք աշխատեցնում, հաճախ հարկավոր է լինում գագաթների ու կողերի չափսերն օգտագործել ասիմպտոտային նշագրման մեջ։ Օրինակ՝ պատկերացրու, թե ուզում ենք խոսել աշխատելու ժամանակի մասին, որը գծային է որոշ գագաթների համար։ Կոպիտ ասած՝ պետք է ասենք, որ այն $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis է՝ օգտագործելով $|\cdot|$vertical bar, dot, vertical bar նշագրումը։ Բայց չափսերը հաշվելու համար ասիմպտոտային նշագրումն օգտագործելը ծանրաբեռնված գործ է, հետևաբար մենք կիրառում ենք այն օրենքը, որ միայն ու միայն ասիմպտոտային նշագրման մեջ կարող ենք անտեսել չափսի նշագրումը։ Հետևաբար, $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis գրելու փոխարեն ուղղակի գրում ենք $\Theta(V)$\Theta, left parenthesis, V, right parenthesis։ Նույն կերպ $\Theta(\lg |E|)$\Theta, left parenthesis, \lg, vertical bar, E, vertical bar, right parenthesis գրելու փոխարեն գրում ենք $\Theta(\lg E)$\Theta, left parenthesis, \lg, E, right parenthesis։

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