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

Jump to navigation Jump to search
Ավելացվել է 5 բայտ ,  7 տարի առաջ
Առանց խմբագրման ամփոփման
չ (Bot: Migrating 43 interwiki links, now provided by Wikidata on d:q141488 (translate me))
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ եւև հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են [[Դիսկրետ մաթեմատիկա]] բաժնում։
 
Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ-ողղորդվածուղղորդված (սիմետրիկ)։ Օրինակ, եթե որպես գրաֆի գագաթներ համարենք երեկույթին մասնակցող մարդկանց, եւև ասենք գագաթների միջև գոյություն ունի կող, եթե կա ձեռք-սեղմում, ապա սա ոչ-ուղղորդված գրաֆի օրինակ է, որովհետեւ եթե մարդկանցից մեկը սեղմեց մյուսի ձեռքը, ապա երկրորդ անձն էլ սեղմեց առաջինի ձեռքը։ Մյուս կողմից, եթե գագաթները ներկայացնող մարդկանց միջև հարաբերությունը սահմանենք որպես Ա մառդըմարդը ծանոթ է Բ անձի հետ, ապա այս ձևով սահմանված գրաֆը կլինի ուղղորդված, քանի որ երբ Ա անձը ճանաչում է BԲ մարդուն, ապա այստեղից չի հետևում, որ Բ մարդն էլ է ճանաչում Ա մառդուն։մարդուն։
 
Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։
Գաղափարապես գրաֆը ձևավորվում է գագաթներով և դրանք միացնող կողերով։
 
Օրինակ 1.
Օրինակ1.
[[Պատկեր:SimpleGraf.jpg]]
 
Ֆորմալ գրաֆը բազմությունների զույգ է՝ (V,E), որտեղ V-ն գագաթների բազմությունն է և E-ն կողերի բազմությունն է, որոնք ձևավորվում են գագաթների զույգով։ E-ն մուլտիբազմություն է, այսինքն՝ նրա էլէմենտները կարող են հանդիպել ավելի քան մեկ անգամ։ Գրաֆի գագաթները կարող ենք նշանակել լատինական այբուբենի տառերով։ Մեր օրինակում կնշանակենք հետևյալ կերպ՝ v1,v2,...vn : Ելնելով նախորդ օրինակից մեր գրաֆը կունենա հետևյալ տեսքը՝
 
Օրինակ 2.
Օրինակ2․
[[Պատկեր:GrafWithVertices.jpg]]
 
Նմանակերպ մենք կարող ենք նշանակել գրաֆի կողերը լատինական այբուբենի տառերով՝ e1,e2,...en:
 
Օրինակ 3.
Օրինակ3.
[[Պատկեր:GrafWithVerticesEdges.jpg]]
 
Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։
 
Օրինակ 1՝
Օրինակ1՝
[[Պատկեր:AdjacencyMatrix.jpg]]
 
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։
 
G ուղղորդված գրաֆի հարևանության մատրիցը՝ D=(dij) մատրիցն է, որտեղ dij այն ուղղոռդվածուղղորդված կողերի քանակն է, որոնք դուրս են գալիս vi գագաթից և գնում են դեպի vj գագաթը։
 
Օրինակ2՝
 
====Կցության հարաբերություն====
; [[Կցության ցուցակ]]: Կողերը ներկաjացվումներկայացվում են մասիվով, որը պարունակում է գագաթների զույգերը , կշիռը և այլ տվյալներ։
 
; [[Կցության մատրից]]: Գրաֆը ներկայացվում է ''m'' × ''n'' մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք: 1 - կից է , 0 - կից չէ)։
Անանուն մասնակից

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