Գրաֆներ

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

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

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

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

Օրինակ 1.
Պատկեր:SimpleGraf.jpg

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

Օրինակ 2.
Պատկեր:GrafWithVertices.jpg

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

Օրինակ 3.
Պատկեր:GrafWithVerticesEdges.jpg

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

Օրինակ 1՝
Պատկեր:AdjacencyMatrix.jpg

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

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

Օրինակ2՝
AdjacencyMatrixDirected.jpg

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

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

 Գրաֆի լրացում գրաֆ 
G=(V,E) գրաֆի լրացում կանվանենք ┌G(V,┌E), որտեղ ┌E-ն այն կողերի բազմությունն է, որոնք առկա չեն G գրաֆում։

 Ծանոթագրություններ