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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Content deleted Content added
չ Bot: Migrating 43 interwiki links, now provided by Wikidata on d:q141488 (translate me)
No edit summary
Տող 1. Տող 1.
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ եւ հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են [[Դիսկրետ մաթեմատիկա]] բաժնում։
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ և հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են [[Դիսկրետ մաթեմատիկա]] բաժնում։


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


Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։
Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։
Տող 8. Տող 8.
Գաղափարապես գրաֆը ձևավորվում է գագաթներով և դրանք միացնող կողերով։
Գաղափարապես գրաֆը ձևավորվում է գագաթներով և դրանք միացնող կողերով։


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


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


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


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


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


Տող 28. Տող 28.
Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։
Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։


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


Տող 34. Տող 34.
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։
Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։


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


Օրինակ2՝
Օրինակ2՝
Տող 40. Տող 40.


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


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

13:08, 12 Հունիսի 2013-ի տարբերակ

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

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

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

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

Գրաֆ

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

Օրինակ 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

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

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

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

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

Օրինակ 1.

Complementgraf.jpg