«Գրաֆներ»–ի խմբագրումների տարբերություն

Jump to navigation Jump to search
չ
clean up, replaced: → (10), ք: → ք։ oգտվելով ԱՎԲ
չ (clean up, replaced: եւ → և oգտվելով ԱՎԲ)
չ (clean up, replaced: → (10), ք: → ք։ oգտվելով ԱՎԲ)
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ և հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են [[Դիսկրետ մաթեմատիկա]] բաժնում։
 
Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ-ուղղորդված (սիմետրիկ)։ Օրինակ, եթե որպես գրաֆի գագաթներ համարենք երեկույթին մասնակցող մարդկանց, և ասենք գագաթների միջև գոյություն ունի կող, եթե կա ձեռք-սեղմում, ապա սա ոչ-ուղղորդված գրաֆի օրինակ է, որովհետև եթե մարդկանցից մեկը սեղմեց մյուսի ձեռքը, ապա երկրորդ անձն էլ սեղմեց առաջինի ձեռքը։ Մյուս կողմից, եթե գագաթները ներկայացնող մարդկանց միջև հարաբերությունը սահմանենք որպես Ա մարդը ծանոթ է Բ անձի հետ, ապա այս ձևով սահմանված գրաֆը կլինի ուղղորդված, քանի որ երբ Ա անձը ճանաչում է Բ մարդուն, ապա այստեղից չի հետևում, որ Բ մարդն էլ է ճանաչում Ա մարդուն։
 
Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։
[[Պատկեր:SimpleGraf.jpg]]
 
Ֆորմալ գրաֆը բազմությունների զույգ է՝ (V,E), որտեղ V-ն գագաթների բազմությունն է և E-ն կողերի բազմությունն է, որոնք ձևավորվում են գագաթների զույգով։ E-ն մուլտիբազմություն է, այսինքն՝ նրա էլէմենտները կարող են հանդիպել ավելի քան մեկ անգամ։ Գրաֆի գագաթները կարող ենք նշանակել լատինական այբուբենի տառերով։ Մեր օրինակում կնշանակենք հետևյալ կերպ՝ v1,v2,...vn : Ելնելով նախորդ օրինակից մեր գրաֆը կունենա հետևյալ տեսքը՝
 
Օրինակ 2.
====Հարևանության հարաբերություն====
Գրաֆի ներկայացումը հարևանության մատրիցի միջոցով
G=(V,E) գրաֆի հարևանության մատրիցը nxn չափանի մատրից է՝ D=(dij), որտեղ n-ը G գրաֆի գագաթների քանակն է՝ V={v1,v2,....vn} և dij vi և vj գագաթների միջև կողերի քանակը։
Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։
 
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։
 
G ուղղորդված գրաֆի հարևանության մատրիցը՝ D=(dij) մատրիցն է, որտեղ dij այն ուղղորդված կողերի քանակն է, որոնք դուրս են գալիս vi գագաթից և գնում են դեպի vj գագաթը։
 
Օրինակ2՝
; [[Կցության ցուցակ]]: Կողերը ներկայացվում են մասիվով, որը պարունակում է գագաթների զույգերը , կշիռը և այլ տվյալներ։
 
; [[Կցության մատրից]]: Գրաֆը ներկայացվում է ''m'' × ''n'' մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք:դեպք։ 1 - կից է , 0 - կից չէ)։
 
==Գրաֆի լրացում գրաֆ==
1 105 242

edits

Նավարկման ցանկ