Վիքիպեդիա

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

Դիտել պատմությունը
← Նախորդ տարբՀաջորդ տարբ →
Content deleted Content added
ՎիզուալԵլատեքստ
չ clean up, փոխարինվեց: → (2), ): → )։ (2) oգտվելով ԱՎԲ
չ Ռոբոտ․ Տեքստի ավտոմատ փոխարինում (- <ref +<ref)
Տող 18.
 
==Կիրառություններ==
[[Պատկեր:Wikipedia multilingual network graph July 2013.svg|thumb|Գագաթները [[Վիքիպեդիա]]յի լեզվական տարբերակներն են։ Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ <ref>[http://arxiv.org/abs/1312.0976 Scott Hale, Multilinguals and Wikipedia Editing, 2013]</ref>]]
 
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ։ Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային [[ալգորիթմ]]ներով։
Տող 30.
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով։ Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով։ Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ։
 
Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին։ Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է։ Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ <ref>[http://www.graphdrawing.org/ Գրաֆների պատկերում (անգլերեն)]</ref>:
 
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են [[''հարթ'' գրաֆներ|հարթ գրաֆներ]]: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի [[խաչումների թիվ]] <ref>[[Խաչումների թիվ|Խաչումների թվի]] մասին [http://mathworld.wolfram.com/GraphCrossingNumber.html Wolfram MathWorld-ում]</ref>: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի։ Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են։ Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է ''տոպոլոգիական գրաֆների տեսությունը'':
 
==Գրաֆների տեսության խնդիրներ==
Տող 49.
==== Գագաթային ներկումներ ====
''Ճիշտ գագաթային ներկման'' դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր։ Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր գույն։ Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում։ Այդ թիվը կոչվում է գրաֆի [[քրոմատիկ թիվ]]: Դրա որոշումը NP-լրիվ խնդիր է<ref>[[քրոմատիկ թիվ|Քրոմատիկ թվի]] մասին [http://mathworld.wolfram.com/ChromaticNumber.html Wolfram MathWorld-ում]</ref>, սակայն հայտնի են բազմաթիվ գնահատականներ։ Օրինակ, ըստ [[Բրուքսի թեորեմ]]ի <ref>[[Բրուքսի թեորեմ]]ը [http://mathworld.wolfram.com/BrooksTheorem.html Wolfram MathWorld-ում]</ref>, գրաֆի քրոմատիկ թիվը չի գերազանցում գրաֆի առավելագույն աստիճանը, բացառությամբ [[ցիկլ (գրաֆների տեսություն)|ցիկլերի]] և լրիվ գրաֆների։
 
[[Պատկեր:World map with four colours.svg|thumb|Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են։ [[Չորս գույների թեորեմ]]ի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում]]
Տող 62.
Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի [[կողային գրաֆ]]ի ճիշտ գագաթային ներկմանը։
 
Ինչպես գագաթային, այնպես էլ կողային ներկումների համար սահմանվում են '''ցուցակային ներկումներ''', երբ յուրաքանչյուր գագաթի (կողի) համապատասխանեցվում է գույների ցուցակ, որտեղից անհրաժեշտ է ընտրել գույներ այնպես, որ ստացված ներկումը լինի ճիշտ։ [[Կողային ցուցակային ներկման հիպոթեզ]]ի համաձայն, ցանկացած օղակ չպարունակող մուլտիգրաֆի համար կողային ցուցակային քրոմատիկ թիվը պետք է հավասար լինի գրաֆի քրոմատիկ դասին։ Այս խնդիրը ևս լուծված չէ <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>:
 
=== Շրջանցումներ ===
Տող 71.
Գրաֆների տեսության առաջացումը կապվում է [[Էյլեր]]ի 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
Ստացված է «https://hy.wikipedia.org/wiki/Գրաֆների_տեսություն» էջից