«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն
տերմինների հստակեցում |
փաստերի ավելացում, սահմանումներ |
||
| Տող 19. | Տող 19. | ||
| colspan="8" align="center" | Մեկից ութ գագաթանի լրիվ գրաֆները․ <math>K_1...K_8</math>: |
| colspan="8" align="center" | Մեկից ութ գագաթանի լրիվ գրաֆները․ <math>K_1...K_8</math>: |
||
|} |
|} |
||
==Սահմանումներ== |
|||
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ G=(V,E), որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ: |
|||
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ''ծայրակետեր'': Հաճախ ''{u, v}'' կողը կրճատ նշանակում են ''uv''-ով: |
|||
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն: Այսպես սահմանվող օբյեկտները կոչվում են '''մուլտիգրաֆներ''': Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով ''օղակ''), այդ դեպքում ասում են, որ գործ ունենք '''պսևդոգրաֆի''' հետ: |
|||
Սովորաբար V և E բազմությունները ընդունվում են վերջավոր: Հակառակ դեպքում գործ ունենք '''անվերջ գրաֆների''' հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն: Գրաֆի '''կարգը''' գագաթների բազմության հզորությունն է: Որևէ գագաթի '''աստիճանը''' այդ գագաթին միացած կողերի քանակն է: Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ: |
|||
{{ՎՊԵ|Graph theory}} |
{{ՎՊԵ|Graph theory}} |
||
19:51, 26 Նոյեմբերի 2014-ի տարբերակ
Մաթեմատիկայում և համակարգչային գիտության մեջ գրաֆների տեսությունը ուսումնասիրում է գրաֆները, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են: Գրաֆը կազմված է «գագաթներից» (կամ «հանգույցներից») և «կողերից», որոնք միացնում են գագաթների որոշ զույգեր:
Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը: Տես գրաֆներ հոդվածը ավելի մանրամասն սահմանումների համար։ Գրաֆները Դիսկրետ մաթեմատիկա բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։
Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք Գրաֆների տեսության բառարան։
|
|
|
|
|
|
|
|
| Մեկից ութ գագաթանի լրիվ գրաֆները․ : | |||||||
Սահմանումներ
Գրաֆը սահմանվում է որպես կարգավոր զույգ G=(V,E), որտեղ V-ն գագաթների (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ կողերի (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են չկողմնորոշված և հասարակ գրաֆներ:
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ծայրակետեր: Հաճախ {u, v} կողը կրճատ նշանակում են uv-ով:
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն: Այսպես սահմանվող օբյեկտները կոչվում են մուլտիգրաֆներ: Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով օղակ), այդ դեպքում ասում են, որ գործ ունենք պսևդոգրաֆի հետ:
Սովորաբար V և E բազմությունները ընդունվում են վերջավոր: Հակառակ դեպքում գործ ունենք անվերջ գրաֆների հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն: Գրաֆի կարգը գագաթների բազմության հզորությունն է: Որևէ գագաթի աստիճանը այդ գագաթին միացած կողերի քանակն է: Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ:
|
Վիքիպահեստ նախագծում կարող եք այս նյութի վերաբերյալ հավելյալ պատկերազարդում գտնել Գրաֆների տեսություն կատեգորիայում։ |