Ուղղված ընդդեմ չուղղորդված գրաֆիկ
Գրաֆիկը մաթեմատիկական կառուցվածք է, որը կազմված է գագաթներից և եզրերից: Գրաֆիկը ներկայացնում է օբյեկտների մի շարք (ներկայացված գագաթներով), որոնք միացված են որոշ կապերի միջոցով (ներկայացված եզրերով): Օգտագործելով մաթեմատիկական նշումները՝ գրաֆիկը կարելի է ներկայացնել G-ով, որտեղ G=(V, E) և V-ը գագաթների բազմությունն է, իսկ E-ն՝ եզրերի բազմությունը։ Չուղղորդված գրաֆիկում գագաթները միացնող եզրերի հետ կապված ուղղություն չկա: Ուղղորդված գրաֆիկում կա ուղղություն, որը կապված է գագաթները միացնող եզրերի հետ:
Չուղղորդված գրաֆիկ
Ինչպես նշվեց ավելի վաղ, չուղղորդված գրաֆիկը այն գրաֆիկն է, որի եզրերում չկա ուղղություն, որը կապում է գագաթները գրաֆիկում:Նկար 1-ում պատկերված է չուղղորդված գրաֆիկ V={V1, V2, V3} գագաթներով: Վերոնշյալ գրաֆիկում եզրերի բազմությունը կարելի է գրել V={(V1, V2), (V2, V3), (V1, V3)}: Կարելի է նաև նշել, որ ոչինչ չի խանգարում եզրերի հավաքածուն գրել որպես V={(V2, V1), (V3, V2), (V3, V1)}, քանի որ եզրերը ուղղություն չունեն: Հետևաբար, չուղղորդված գրաֆիկի եզրերը դասավորված զույգեր չեն: Սա չուղղորդված գրաֆիկի հիմնական բնութագիրն է: Չուղղորդված գրաֆիկները կարող են օգտագործվել օբյեկտների միջև սիմետրիկ հարաբերությունները ներկայացնելու համար, որոնք ներկայացված են գագաթներով: Օրինակ, երկկողմանի ճանապարհային ցանցը, որը միացնում է մի շարք քաղաքներ, կարող է ներկայացվել չուղղորդված գրաֆիկի միջոցով: Քաղաքները կարող են ներկայացվել գրաֆիկի գագաթներով, իսկ ծայրերը ներկայացնում են քաղաքները միացնող երկկողմանի ճանապարհները:
Ուղղված գրաֆիկ
Ուղղորդված գրաֆիկը այն գրաֆիկն է, որում գագաթները կապող գծապատկերի եզրերն ունեն ուղղություն: Նկար 2-ում պատկերված է ուղղորդված գրաֆիկ V={V1, V2, V3} գագաթներով: Վերոնշյալ գրաֆիկում եզրերի բազմությունը կարելի է գրել V={(V1, V2), (V2, V3), (V1, V3)}: Չուղղորդված գրաֆիկի եզրերը դասավորված են զույգերով: Ձևականորեն ուղղորդված գրաֆիկում e եզրը կարող է ներկայացվել e=(x, y) դասավորված զույգով, որտեղ x գագաթն է, որը կոչվում է e եզրի սկզբնաղբյուր, աղբյուր կամ սկզբնական կետ, իսկ y գագաթը կոչվում է վերջնամաս։, վերջավոր գագաթ կամ վերջնակետ։ Օրինակ, ճանապարհային ցանցը, որը միացնում է մի շարք քաղաքներ՝ օգտագործելով միակողմանի ճանապարհները, կարող է ներկայացվել չուղղորդված գրաֆիկի միջոցով: Քաղաքները կարող են ներկայացվել գրաֆիկի գագաթներով, իսկ ուղղորդված եզրերը ներկայացնում են քաղաքները կապող ճանապարհները՝ հաշվի առնելով այն ուղղությունը, որով երթեւեկությունը հոսում է ճանապարհին:
Ո՞րն է տարբերությունը ուղղորդված գրաֆիկի և չուղղորդված գրաֆիկի միջև:
Ուղղորդված գրաֆիկում ծայրը դասավորված զույգ է, որտեղ դասավորված զույգը ներկայացնում է երկու գագաթները կապող եզրի ուղղությունը: Մյուս կողմից, չուղղորդված գրաֆիկում եզրը չդասավորված զույգ է, քանի որ եզրի հետ կապված ուղղություն չկա: Չուղղորդված գրաֆիկները կարող են օգտագործվել օբյեկտների միջև սիմետրիկ հարաբերությունները ներկայացնելու համար: Չուղղորդված գրաֆիկի յուրաքանչյուր հանգույցի ներաստիճանը և դուրս աստիճանը հավասար են, բայց դա ճիշտ չէ ուղղորդված գրաֆիկի համար: Չուղղորդված գրաֆիկը ներկայացնելու համար մատրիցա օգտագործելիս մատրիցը միշտ դառնում է սիմետրիկ գրաֆիկ, բայց դա ճիշտ չէ ուղղորդված գրաֆիկների համար: Չուղղորդված գրաֆիկը կարող է փոխակերպվել ուղղորդված գրաֆիկի՝ յուրաքանչյուր եզրը փոխարինելով հակառակ ուղղությամբ ընթացող երկու ուղղորդված եզրերով: Այնուամենայնիվ, հնարավոր չէ ուղղորդված գրաֆիկը վերածել չուղղորդված գրաֆիկի:
