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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Content deleted Content added
չ Ռոբոտը ավելացնում է․: lv:Grafs
-կես տարուց ավել չլրացված ենթավերնագրեր
Տող 34. Տող 34.
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։


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


Օրինակ2՝
Օրինակ2՝
Տող 51. Տող 51.
[[Պատկեր:Complementgraf.jpg|Complementgraf.jpg]]
[[Պատկեր:Complementgraf.jpg|Complementgraf.jpg]]


==Գրաֆների տիպերը==
[[Կատեգորիա:Գրաֆների տեսություն| ]]
{{անավարտ բաժին}}

==Գրաֆային գործողություններ==
{{անավարտ բաժին}}

[[Կատեգորիա:Գրաֆների տեսություն]]


[[ar:رسم بياني]]
[[ar:رسم بياني]]

13:16, 18 Նոյեմբերի 2012-ի տարբերակ

Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ եւ հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (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՝ AdjacencyMatrixDirected.jpg

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

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

Գրաֆի լրացում գրաֆ

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

Օրինակ 1.

Complementgraf.jpg