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

չ
math mode
չ (math mode)
[[Մաթեմատիկա]]յում և [[Ինֆորմատիկա|համակարգչային գիտության]] մեջ '''գրաֆների տեսությունը''' ուսումնասիրում է [[գրաֆներ]]ը, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են: Գրաֆը կազմված է ''գագաթներից'' (կամ ''հանգույցներից'') և ''կողերից'', որոնք միացնում են գագաթների որոշ զույգեր:
 
Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը: Տես [[գրաֆներ]] հոդվածը ավելի մանրամասն սահմանումների համար։ Գրաֆները [[դիսկրետ մաթեմատիկա]] բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։
 
Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք [[գրաֆների տեսության բառարան]]։
[[File:Multi-pseudograph.svg|thumb|Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)]]
 
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ <math>G=(V,E)</math>, որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ:
 
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ''ծայրակետեր'': Հաճախ ''<math>\{u, v\}''</math> կողը կրճատ նշանակում են ''<math>uv''</math>-ով:
 
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն: Այսպես սահմանվող օբյեկտները կոչվում են '''մուլտիգրաֆներ''': Գագաթների միևնույն զույգի միջև մեկից ավելի կողերը կոչվում են '''պատիկ''' կողեր: Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով ''օղակ''), այդ դեպքում ասում են, որ գործ ունենք '''պսևդոգրաֆի''' հետ:
Նման խնդիրներ դրվում են նաև [[ծնված ենթագրաֆ]]ների համար: Այս խնդիրներն էլ հաճախ բարդ են: Օրինակ, տրված գրաֆում մեծագույն [[անկախ բազմություն]] գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է:
 
Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը: H գրաֆը կոչվում է G գրաֆի [[մինոր (գրաֆների տեսություն)|'''մինոր''']], եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր [[կծկելով]]: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է: [[Վագների թեորեմ]]ը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում ''K''<submath>K_{3,3}</submath> [[լրիվ երկկողմանի գրաֆ]]ը և ''K''<submath>5K_5</submath> լրիվ գրաֆը որպես մինոր:
 
=== Գրաֆների ներկումներ ===