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

չ
վերջակետների ուղղում, փոխարինվեց: ն: → ն։ (65) oգտվելով ԱՎԲ
(SVG)
չ (վերջակետների ուղղում, փոխարինվեց: ն: → ն։ (65) oգտվելով ԱՎԲ)
[[File:Complete graph K6.svg|thumb|Վեց գագաթանի [[լրիվ գրաֆ]] <math>K_6</math>]]
[[Մաթեմատիկա]]յում և [[Ինֆորմատիկա|համակարգչային գիտության]] մեջ '''գրաֆների տեսությունը''' ուսումնասիրում է [[գրաֆներ]]ը, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են:են։ Գրաֆը կազմված է ''գագաթներից'' (կամ ''հանգույցներից'') և ''կողերից'', որոնք միացնում են գագաթների որոշ զույգեր:զույգեր։
 
Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը:մյուսը։ Գրաֆները [[դիսկրետ մաթեմատիկա]] բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։
 
Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք [[գրաֆների տեսության բառարան]]։
[[File:Multi-pseudograph.svg|thumb|Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)]]
 
'''Գրաֆը''' սահմանվում է որպես կարգավոր զույգ <math>G=(V,E)</math>, որտեղ V-ն '''գագաթների''' (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ '''կողերի''' (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են ''չկողմնորոշված'' և ''հասարակ'' գրաֆներ:գրաֆներ։
 
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ''ծայրակետեր'': Հաճախ <math>\{u, v\}</math> կողը կրճատ նշանակում են <math>uv</math>-ով:ով։
 
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն:մուլտիբազմություն։ Այսպես սահմանվող օբյեկտները կոչվում են '''մուլտիգրաֆներ''': Գագաթների միևնույն զույգի միջև մեկից ավելի կողերը կոչվում են '''պատիկ''' կողեր:կողեր։ Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով ''օղակ''), այդ դեպքում ասում են, որ գործ ունենք '''պսևդոգրաֆի''' հետ:հետ։
 
Սովորաբար V և E բազմությունները ընդունվում են վերջավոր:վերջավոր։ Հակառակ դեպքում գործ ունենք '''անվերջ գրաֆների''' հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն:չունեն։ Գրաֆի '''կարգը''' գագաթների բազմության հզորությունն է:է։ Որևէ գագաթի '''աստիճանը''' այդ գագաթին միացած կողերի քանակն է:է։ Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ:անգամ։
 
==Կիրառություններ==
[[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>]]
 
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ:մեջ։ Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով:ներով։
 
Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն:այլն։ Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև:միջև։ Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային [[տվյալների հենք]]եր:եր։ Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը):
 
Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը:կապերը։
 
==Գրաֆների պատկերում==
[[File:Social Network Analysis Visualization.png|thumb|Մեծ սոցիալական գրաֆի պատկերում ուժային ալգորիթմով]]
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով:միջոցով։ Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով:կորերով։ Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ:սլաքներ։
 
Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին:գրաֆին։ Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է:է։ Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ <ref>[http://www.graphdrawing.org/ Գրաֆների պատկերում (անգլերեն)]</ref>:
 
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի [[խաչումների թիվ]] <ref>[[Խաչումների թիվ|Խաչումների թվի]] մասին [http://mathworld.wolfram.com/GraphCrossingNumber.html Wolfram MathWorld-ում]</ref>: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի:զրոյի։ Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են:են։ Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է ''տոպոլոգիական գրաֆների տեսությունը'':
 
==Գրաֆների տեսության խնդիրներ==
===Ենթագրաֆներ, մինորներ===
[[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>:
 
Նման խնդիրներ դրվում են նաև [[ծնված ենթագրաֆ]]ների համար:համար։ Այս խնդիրներն էլ հաճախ բարդ են:են։ Օրինակ, տրված գրաֆում մեծագույն [[անկախ բազմություն]] գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է:է։
 
Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը:հարցը։ H գրաֆը կոչվում է G գրաֆի [[մինոր (գրաֆների տեսություն)|'''մինոր''']], եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր [[կծկելով]]: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է:է։ [[Վագների թեորեմ]]ը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում <math>K_{3,3}</math> [[լրիվ երկկողմանի գրաֆ]]ը և <math>K_5</math> լրիվ գրաֆը որպես մինոր:մինոր։
 
=== Գրաֆների ներկումներ ===
[[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|Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են:են։ [[Չորս գույների թեորեմ]]ի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում]]
 
Հարթ գրաֆների դեպքում քրոմատիկ թիվը գտնելու խնդիրը հայտնի է որպես քարտեզ ներկելու խնդիր:խնդիր։ Եթե երկրներին (կամ ցանկացած տարածքային միավորին) համպատախասնեցվեն գագաթներ հարթության վրա, իսկ հարևան երկրները միացվեն կողերով, ապա ճիշտ գագաթների ներկումը կհամապատասխանի քարտեզի ներկմանը:ներկմանը։ [[Չորս գույների թեորեմ]]ի համաձայն, հարթ գրաֆի քրոմատիկ թիվը չորսից մեծ չէ, հետևաբար ցանկացած քարտեզ ներկելու համար բավարար է օգտագործել չորս գույն:գույն։
 
Ճիշտ գագաթային ներկումների հայտնի չլուծված խնդիրներից է [[Հադվիգերի հիպոթեզ]]ը, ըստ որի ''k'' քրոմատիկ թիվ ունեցող գրաֆը պետք է պարունակի ''k''-գագաթանի լրիվ գրաֆը որպես մինոր:մինոր։ Այս հիպոթեզը չորս գույների թեորեմի ընդհանրացումն է:է։
 
==== Կողային ներկումներ ====
Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ''ճիշտ կողային ներկում'': Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի [[քրոմատիկ դաս]], որը հաշվելը ևս NP-լրիվ խնդիր է:է։ [[Վիզինգի թեորեմ]]ի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով:մեկով։
 
Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի [[կողային գրաֆ]]ի ճիշտ գագաթային ներկմանը:ներկմանը։
 
Ինչպես գագաթային, այնպես էլ կողային ներկումների համար սահմանվում են '''ցուցակային ներկումներ''', երբ յուրաքանչյուր գագաթի (կողի) համապատասխանեցվում է գույների ցուցակ, որտեղից անհրաժեշտ է ընտրել գույներ այնպես, որ ստացված ներկումը լինի ճիշտ:ճիշտ։ [[Կողային ցուցակային ներկման հիպոթեզ]]ի համաձայն, ցանկացած օղակ չպարունակող մուլտիգրաֆի համար կողային ցուցակային քրոմատիկ թիվը պետք է հավասար լինի գրաֆի քրոմատիկ դասին:դասին։ Այս խնդիրը ևս լուծված չէ <ref>[[Կողային ցուցակային ներկման հիպոթեզ]]ը [http://www.openproblemgarden.org/?q=node/2110 Open Problem Garden-ում]</ref>:
 
==== Տոտալ ներկումներ ====
Ներկումը կոչվում է ''տոտալ'', երբ ներկվում են ինչպես գագաթները, այնպես էլ կողերը:կողերը։ Այս ոլորտի ամենահայտնի խնդիրը [[տոտալ ներկման հիպոթեզ]]ն է, որը ձևակերպվել է Վիզինգի և Բեհզադի կողմից 1965թ․ և մինչ այժմ լուծված չէ <ref>[[Տոտալ ներկման հիպոթեզ]]ը [http://www.openproblemgarden.org/op/behzads_conjecture Open Problem Garden-ում]</ref>:
 
=== Շրջանցումներ ===
[[File:Konigsberg bridges.png|thumb|Քյոնիգսբերգ քաղաքի քարտեզը Էյլերի ապրած ժամանակաշրջանում, որտեղ հստակ երևում են յոթ կամուրջները]]
Գրաֆների տեսության առաջացումը կապվում է [[Էյլեր]]ի 1741 թվականին տպագրած հոդվածի հետ, որտեղ քննարկվում էր հետևյալ խնդիրը․ հնարավո՞ր է անցնել Քյոնիգսբերգ քաղաքի (այժմ՝ [[Կալինինգրադ]], [[Ռուսաստան]]) 7 կամուրջներով, յուրաքանչյուրով ճիշտ մեկ անգամ<ref>[http://www.math.dartmouth.edu/~euler/pages/E053.html The Euler Archive] Էյլերի հոդվածի բնօրինակ տեքստը [[լատիներեն]]ով և մի շարք օգտակար հղումներ</ref>: Էյլերը ցույց տվեց, որ դա հնարավոր չէ:չէ։ Եթե քաղաքի գետերով բաժանված հատվածները դիտարկվեն որպես գրաֆի գագաթներ, իսկ կամուրջները՝ կողեր, ապա այս խնդիրը համարժեք է գրաֆում այնպիսի շղթայի գոյությանը, որն անցնում է բոլոր կողերով ճիշտ մեկ անգամ:անգամ։ Այդպիսի շղթան կոչվում է '''Էյլերյան շղթա''': Ըստ [[Էյլերի թեորեմ]]ի, Քյոնիգսբերգին համապատասխանող գրաֆում այդպիսի շղթա չի կարող գոյություն ունենալ:ունենալ։ Գրաֆում Էյլերյան շղթայի, ինչպես նաև էյլերյան ցիկլի (երբ շրջանցման սկիզբն ու վերջը համընկնում են) գոյությունը կարելի է պարզել բազմանդամային ժամանակում:ժամանակում։
 
Էապես ավելի բարդ խնդիր է [[Համիլտոնյան ցիկլ]]ի գոյության խնդիրը:խնդիրը։ Այս դեպքում պահանջվում է, որ ցիկլը անցնի յուրաքանչյուր գագաթով ճիշտ մեկ անգամ:անգամ։ Գրաֆում համիլտոնյան ցիկլի գոյության համար հայտնի են բազմաթիվ բավարար պայմաններ:պայմաններ։ Սակայն ընդհանուր դեպքում խնդիրը NP-լրիվ է նույնիսկ հարթ գրաֆների համար, որոնց առավելագույն աստիճանը երեք է <ref>{{citation
| last1 = Garey | first1 = M. R. | author1-link = Michael Garey
| last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
144 973

edits