Գրաֆներ

Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ եւ հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են Դիսկրետ մաթեմատիկա բաժնում։

Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ-ողղորդված (սիմետրիկ)։ Օրինակ, եթե որպես գրաֆի գագաթներ համարենք երեկույթին մասնակցող մարդկանց, եւ ասենք գագաթների միջև գոյություն ունի կող, եթե կա ձեռք-սեղմում, ապա սա ոչ-ուղղորդված գրաֆի օրինակ է, որովհետեւ եթե մարդկանցից մեկը սեղմեց մյուսի ձեռքը, ապա երկրորդ անձն էլ սեղմեց առաջինի ձեռքը։ Մյուս կողմից, եթե գագաթները ներկայացնող մարդկանց միջև հարաբերությունը սահմանենք որպես Ա մառդը ծանոթ է Բ անձի հետ, ապա այս ձևով սահմանված գրաֆը կլինի ուղղորդված, քանի որ երբ Ա անձը ճանաչում է B մարդուն, ապա այստեղից չի հետևում, որ Բ մարդն էլ է ճանաչում Ա մառդուն։

Գրաֆը Գրաֆների տեսություն բաժնի հիմնական ուսումնասիրվող թեման է։

Սահմանումներ

Գրաֆ

Գաղափարապես գրաֆը ձևավորվում է գագաթներով և դրանք միացնող կողերով։

Օրինակ1.

Ֆորմալ գրաֆը բազմությունների զույգ է՝ (V,E), որտեղ V-ն գագաթների բազմությունն է և E-ն կողերի բազմությունն է, որոնք ձևավորվում են գագաթների զույգով։ E-ն մուլտիբազմություն է, այսինքն՝ նրա էլէմենտները կարող են հանդիպել ավելի քան մեկ անգամ։ Գրաֆի գագաթները կարող ենք նշանակել լատինական այբուբենի տառերով։ Մեր օրինակում կնշանակենք հետևյալ կերպ՝ v1,v2,...vn : Ելնելով նախորդ օրինակից մեր գրաֆը կունենա հետևյալ տեսքը՝

Օրինակ2․

Նմանակերպ մենք կարող ենք նշանակել գրաֆի կողերը լատինական այբուբենի տառերով՝ e1,e2,...en:

Օրինակ3.

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

Հարևանության հարաբերություն

Գրաֆի ներկայացումը հարևանության մատրիցի միջոցով G=(V,E) գրաֆի հարևանության մատրիցը nxn չափանի մատրից է՝ D=(dij), որտեղ n-ը G գրաֆի գագաթների քանակն է՝ V={v1,v2,....vn} և dij vi և vj գագաթների միջև կողերի քանակը։ Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։

Օրինակ1՝

Ոչ ուղղորդված գրաֆի D մատրիցը սիմետրիկ է այսինքն՝ DT = D: Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։

G ուղղորդված գրաֆի հարևանության մատրիցը՝ D=(dij) մատրիցն է, որտեղ dij այն ուղղոռդված կողերի քանակն է, որոնք դուրս են գալիս vi գագաթից և գնում են դեպի vj գագաթը։

Օրինակ2՝

Կցության հարաբերություն

Կցության ցուցակ

Կողերը ներկաjացվում են մասիվով, որը պարունակում է գագաթների զույգերը , կշիռը և այլ տվյալներ։

Կցության մատրից

Գրաֆը ներկայացվում է m × n մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք: 1 - կից է , 0 - կից չէ)։