«Գրաֆներ»–ի խմբագրումների տարբերություն
չ Bot: Migrating 43 interwiki links, now provided by Wikidata on d:q141488 (translate me) |
No edit summary |
||
Տող 1. | Տող 1. | ||
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ |
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ և հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են [[Դիսկրետ մաթեմատիկա]] բաժնում։ |
||
Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ- |
Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ-ուղղորդված (սիմետրիկ)։ Օրինակ, եթե որպես գրաֆի գագաթներ համարենք երեկույթին մասնակցող մարդկանց, և ասենք գագաթների միջև գոյություն ունի կող, եթե կա ձեռք-սեղմում, ապա սա ոչ-ուղղորդված գրաֆի օրինակ է, որովհետեւ եթե մարդկանցից մեկը սեղմեց մյուսի ձեռքը, ապա երկրորդ անձն էլ սեղմեց առաջինի ձեռքը։ Մյուս կողմից, եթե գագաթները ներկայացնող մարդկանց միջև հարաբերությունը սահմանենք որպես Ա մարդը ծանոթ է Բ անձի հետ, ապա այս ձևով սահմանված գրաֆը կլինի ուղղորդված, քանի որ երբ Ա անձը ճանաչում է Բ մարդուն, ապա այստեղից չի հետևում, որ Բ մարդն էլ է ճանաչում Ա մարդուն։ |
||
Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։ |
Գրաֆը [[Գրաֆների տեսություն]] բաժնի հիմնական ուսումնասիրվող թեման է։ |
||
Տող 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 այն |
G ուղղորդված գրաֆի հարևանության մատրիցը՝ D=(dij) մատրիցն է, որտեղ dij այն ուղղորդված կողերի քանակն է, որոնք դուրս են գալիս vi գագաթից և գնում են դեպի vj գագաթը։ |
||
Օրինակ2՝ |
Օրինակ2՝ |
||
Տող 40. | Տող 40. | ||
====Կցության հարաբերություն==== |
====Կցության հարաբերություն==== |
||
; [[Կցության ցուցակ]]: Կողերը |
; [[Կցության ցուցակ]]: Կողերը ներկայացվում են մասիվով, որը պարունակում է գագաթների զույգերը , կշիռը և այլ տվյալներ։ |
||
; [[Կցության մատրից]]: Գրաֆը ներկայացվում է ''m'' × ''n'' մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք: 1 - կից է , 0 - կից չէ)։ |
; [[Կցության մատրից]]: Գրաֆը ներկայացվում է ''m'' × ''n'' մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք: 1 - կից է , 0 - կից չէ)։ |
13:08, 12 Հունիսի 2013-ի տարբերակ
Մաթեմատիկայում գրաֆը մի շարք օբյեկտների վերացական ներկայացումն է, որտեղ մի քանի զույգ օբյեկտներ կապված են հղումներով։ Փոխկապակցված օբյեկտները ներկայացվում են մաթեմատիկական աբստրակցիաների միջոցով, որոնք կոչվում են գագաթներ և հղումներ, որ կապում են զույգ եզրեր։ Սխեմատիկ տեսքով գրաֆը կարելի է պատկերել որպես մի շարք կետերի (dots) և դրանք միացնող գծերի կամ կորեր միջոցով։ Գրաֆերն մեկն են այն օբյեկտներից, որոնք ուսումնասիրվում են Դիսկրետ մաթեմատիկա բաժնում։
Գրաֆի կողերը կարող են լինել ուղղորդված (ասիմետրիկ) կամ ոչ-ուղղորդված (սիմետրիկ)։ Օրինակ, եթե որպես գրաֆի գագաթներ համարենք երեկույթին մասնակցող մարդկանց, և ասենք գագաթների միջև գոյություն ունի կող, եթե կա ձեռք-սեղմում, ապա սա ոչ-ուղղորդված գրաֆի օրինակ է, որովհետեւ եթե մարդկանցից մեկը սեղմեց մյուսի ձեռքը, ապա երկրորդ անձն էլ սեղմեց առաջինի ձեռքը։ Մյուս կողմից, եթե գագաթները ներկայացնող մարդկանց միջև հարաբերությունը սահմանենք որպես Ա մարդը ծանոթ է Բ անձի հետ, ապա այս ձևով սահմանված գրաֆը կլինի ուղղորդված, քանի որ երբ Ա անձը ճանաչում է Բ մարդուն, ապա այստեղից չի հետևում, որ Բ մարդն էլ է ճանաչում Ա մարդուն։
Գրաֆը Գրաֆների տեսություն բաժնի հիմնական ուսումնասիրվող թեման է։
Սահմանումներ
Գրաֆ
Գաղափարապես գրաֆը ձևավորվում է գագաթներով և դրանք միացնող կողերով։
Ֆորմալ գրաֆը բազմությունների զույգ է՝ (V,E), որտեղ V-ն գագաթների բազմությունն է և E-ն կողերի բազմությունն է, որոնք ձևավորվում են գագաթների զույգով։ E-ն մուլտիբազմություն է, այսինքն՝ նրա էլէմենտները կարող են հանդիպել ավելի քան մեկ անգամ։ Գրաֆի գագաթները կարող ենք նշանակել լատինական այբուբենի տառերով։ Մեր օրինակում կնշանակենք հետևյալ կերպ՝ v1,v2,...vn : Ելնելով նախորդ օրինակից մեր գրաֆը կունենա հետևյալ տեսքը՝
Նմանակերպ մենք կարող ենք նշանակել գրաֆի կողերը լատինական այբուբենի տառերով՝ e1,e2,...en:
Գրաֆների ներկայացումը
Հարևանության հարաբերություն
Գրաֆի ներկայացումը հարևանության մատրիցի միջոցով G=(V,E) գրաֆի հարևանության մատրիցը nxn չափանի մատրից է՝ D=(dij), որտեղ n-ը G գրաֆի գագաթների քանակն է՝ V={v1,v2,....vn} և dij vi և vj գագաթների միջև կողերի քանակը։ Մասնավորապես dij=0, երբ vi և vj գագաթների միջև կող գոյություն չունի։
Ոչ ուղղորդված գրաֆի D մատրիցը սիմետրիկ է այսինքն՝ DT = D: Ակնհայտ է, որ հարևանության մատրիցը որոշում է գրաֆն ամբողջությամբ։
G ուղղորդված գրաֆի հարևանության մատրիցը՝ D=(dij) մատրիցն է, որտեղ dij այն ուղղորդված կողերի քանակն է, որոնք դուրս են գալիս vi գագաթից և գնում են դեպի vj գագաթը։
Կցության հարաբերություն
- Կցության ցուցակ
- Կողերը ներկայացվում են մասիվով, որը պարունակում է գագաթների զույգերը , կշիռը և այլ տվյալներ։
- Կցության մատրից
- Գրաֆը ներկայացվում է m × n մատրիցով, որտեղ m-ը գագաթների քանակն է, n-ը կողերի։ Մատրիցի տարրը [գագաթ, կող] պարունակում է կողի վերջնական տվյալը (պարզագույն դեպք: 1 - կից է , 0 - կից չէ)։
Գրաֆի լրացում գրաֆ
G=(V,E) գրաֆի լրացում կանվանենք ┌G(V,┌E), որտեղ ┌E-ն այն կողերի բազմությունն է, որոնք առկա չեն G գրաֆում։
Օրինակ 1.