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

չ
փոխարինվեց: [[File: → [[Պատկեր: (8)
չ (վերջակետների ուղղում, փոխարինվեց: ն: → ն։ (65) oգտվելով ԱՎԲ)
չ (փոխարինվեց: [[File: → [[Պատկեր: (8))
[[FileՊատկեր:Complete graph K6.svg|thumb|Վեց գագաթանի [[լրիվ գրաֆ]] <math>K_6</math>]]
[[Մաթեմատիկա]]յում և [[Ինֆորմատիկա|համակարգչային գիտության]] մեջ '''գրաֆների տեսությունը''' ուսումնասիրում է [[գրաֆներ]]ը, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են։ Գրաֆը կազմված է ''գագաթներից'' (կամ ''հանգույցներից'') և ''կողերից'', որոնք միացնում են գագաթների որոշ զույգեր։
 
 
==Սահմանումներ==
[[FileՊատկեր:Multi-pseudograph.svg|thumb|Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)]]
 
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ <math>G=(V,E)</math>, որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ։
 
==Կիրառություններ==
[[FileՊատկեր:Wikipedia multilingual network graph July 2013.svg|thumb|Գագաթները [[Վիքիպեդիա]]յի լեզվական տարբերակներն են։ Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ <ref>[http://arxiv.org/abs/1312.0976 Scott Hale, Multilinguals and Wikipedia Editing, 2013]</ref>]]
 
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ։ Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով։
 
==Գրաֆների պատկերում==
[[FileՊատկեր:Social Network Analysis Visualization.png|thumb|Մեծ սոցիալական գրաֆի պատկերում ուժային ալգորիթմով]]
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով։ Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով։ Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ։
 
==Գրաֆների տեսության խնդիրներ==
===Ենթագրաֆներ, մինորներ===
[[FileՊատկեր:Petersen Wagner minors.svg|thumb|360px| [[Պետերսենի գրաֆ]]ը հարթ չէ։ Այն պարունակում է ինչպես ''K''<sub>5</sub> մինոր (ձախից), այնպես էլ ''K''<sub>3,3</sub> մինոր (աջից): Պետերսենի գրաֆը պատկերված է փոքր գագաթներով և սև կողերով։ Դեղին գույնով նշված են մինորները։]]
 
Գրաֆների տեսության հետաքրքիր խնդիրներից է ''ենթագրաֆների իզոմորֆիզմի խնդիրը'', երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի [[ենթագրաֆ]]ի գոյությունը։ Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) ''ժառանգական'' են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը։ Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է։ Մասնավորապես, տրված գրաֆում ամենամեծ [[լրիվ|լրիվ գրաֆ]] ենթագրաֆի գտնելը [[NP-լրիվ խնդիր]] է<ref>Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ [http://mathworld.wolfram.com/CliqueNumber.html Wolfram MathWorld: Clique Number]</ref>:
 
=== Գրաֆների ներկումներ ===
[[ImageՊատկեր:Petersen graph 3-coloring.svg|thumb|right|[[Պետերսենի գրաֆ]]ի ճիշտ գագաթային ներկում 3 գույներով։ Ավելի քիչ գույներով ճիշտ ներկում կառուցել հնարավոր չէ]]
Գրաֆների տեսության բազմաթիվ խնդիրներում գրաֆի տարբեր տարրերին (կող, գագաթ և այլն) համապատասխանեցվում են ''գույներ'' կամ թվեր։ Այդպիսի արտապատկերումները գրաֆի տարրերից թվերին կոչվում են [[գրաֆների ներկումներ|'''ներկումներ''']]:
''Ճիշտ գագաթային ներկման'' դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր։ Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր գույն։ Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում։ Այդ թիվը կոչվում է գրաֆի [[քրոմատիկ թիվ]]: Դրա որոշումը NP-լրիվ խնդիր է<ref>[[քրոմատիկ թիվ|Քրոմատիկ թվի]] մասին [http://mathworld.wolfram.com/ChromaticNumber.html Wolfram MathWorld-ում]</ref>, սակայն հայտնի են բազմաթիվ գնահատականներ։ Օրինակ, ըստ [[Բրուքսի թեորեմ]]ի <ref>[[Բրուքսի թեորեմ]]ը [http://mathworld.wolfram.com/BrooksTheorem.html Wolfram MathWorld-ում]</ref>, գրաֆի քրոմատիկ թիվը չի գերազանցում գրաֆի առավելագույն աստիճանը, բացառությամբ [[ցիկլ (գրաֆների տեսություն)|ցիկլերի]] և լրիվ գրաֆների։
 
[[FileՊատկեր:World map with four colours.svg|thumb|Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են։ [[Չորս գույների թեորեմ]]ի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում]]
 
Հարթ գրաֆների դեպքում քրոմատիկ թիվը գտնելու խնդիրը հայտնի է որպես քարտեզ ներկելու խնդիր։ Եթե երկրներին (կամ ցանկացած տարածքային միավորին) համպատախասնեցվեն գագաթներ հարթության վրա, իսկ հարևան երկրները միացվեն կողերով, ապա ճիշտ գագաթների ներկումը կհամապատասխանի քարտեզի ներկմանը։ [[Չորս գույների թեորեմ]]ի համաձայն, հարթ գրաֆի քրոմատիկ թիվը չորսից մեծ չէ, հետևաբար ցանկացած քարտեզ ներկելու համար բավարար է օգտագործել չորս գույն։
 
=== Շրջանցումներ ===
[[FileՊատկեր:Konigsberg bridges.png|thumb|Քյոնիգսբերգ քաղաքի քարտեզը Էյլերի ապրած ժամանակաշրջանում, որտեղ հստակ երևում են յոթ կամուրջները]]
Գրաֆների տեսության առաջացումը կապվում է [[Էյլեր]]ի 1741 թվականին տպագրած հոդվածի հետ, որտեղ քննարկվում էր հետևյալ խնդիրը․ հնարավո՞ր է անցնել Քյոնիգսբերգ քաղաքի (այժմ՝ [[Կալինինգրադ]], [[Ռուսաստան]]) 7 կամուրջներով, յուրաքանչյուրով ճիշտ մեկ անգամ<ref>[http://www.math.dartmouth.edu/~euler/pages/E053.html The Euler Archive] Էյլերի հոդվածի բնօրինակ տեքստը [[լատիներեն]]ով և մի շարք օգտակար հղումներ</ref>: Էյլերը ցույց տվեց, որ դա հնարավոր չէ։ Եթե քաղաքի գետերով բաժանված հատվածները դիտարկվեն որպես գրաֆի գագաթներ, իսկ կամուրջները՝ կողեր, ապա այս խնդիրը համարժեք է գրաֆում այնպիսի շղթայի գոյությանը, որն անցնում է բոլոր կողերով ճիշտ մեկ անգամ։ Այդպիսի շղթան կոչվում է '''Էյլերյան շղթա''': Ըստ [[Էյլերի թեորեմ]]ի, Քյոնիգսբերգին համապատասխանող գրաֆում այդպիսի շղթա չի կարող գոյություն ունենալ։ Գրաֆում Էյլերյան շղթայի, ինչպես նաև էյլերյան ցիկլի (երբ շրջանցման սկիզբն ու վերջը համընկնում են) գոյությունը կարելի է պարզել բազմանդամային ժամանակում։