Գրաֆների տեսություն Բովանդակություն Սահմանումներ | Կիրառություններ | Գրաֆների պատկերում | Գրաֆների տեսության խնդիրներ | Ծանոթագրություններ | Հղումներ | Նավարկման ցանկScott Hale, Multilinguals and Wikipedia Editing, 2013Գրաֆների պատկերում (անգլերեն)Wolfram MathWorld-ումWolfram MathWorld: Clique NumberWolfram MathWorld-ումWolfram MathWorld-ումOpen Problem Garden-ումOpen Problem Garden-ումThe Euler Archive10.1145/800119.803884Գրաֆների տեսություն - ուսումնամեթոդական ձեռնարկPathFinding.jsGraph TeaՓոքր կապակցված գրաֆների որոնողական համակարգԳրաֆների տեսություն
Գրաֆների տեսությունԻնֆորմատիկա
Մաթեմատիկայումհամակարգչային գիտությանգրաֆներըդիսկրետ մաթեմատիկագրաֆների տեսության բառարանալգորիթմներովտվյալների հենքերհարթ գրաֆներխաչումների թիվենթագրաֆիլրիվ գրաֆNP-լրիվ խնդիրծնված ենթագրաֆներիանկախ բազմությունմինորկծկելովՎագների թեորեմըլրիվ երկկողմանի գրաֆըներկումներքրոմատիկ թիվԲրուքսի թեորեմիցիկլերիՉորս գույների թեորեմիՀադվիգերի հիպոթեզըքրոմատիկ դասՎիզինգի թեորեմիկողային գրաֆիԿողային ցուցակային ներկման հիպոթեզիտոտալ ներկման հիպոթեզնԷյլերիԿալինինգրադՌուսաստանԷյլերի թեորեմիՀամիլտոնյան ցիկլի
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003Eփակելu003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="hy" dir="ltr"u003Eu003Cp class="mw-empty-elt"u003Eu003C/pu003Eu003C/divu003Eu003C/divu003Eu003C/divu003E";());
Գրաֆների տեսություն
Jump to navigation
Jump to search
Վեց գագաթանի լրիվ գրաֆ K6displaystyle K_6
Մաթեմատիկայում և համակարգչային գիտության մեջ գրաֆների տեսությունը ուսումնասիրում է գրաֆները, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են։ Գրաֆը կազմված է գագաթներից (կամ հանգույցներից) և կողերից, որոնք միացնում են գագաթների որոշ զույգեր։
Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը։ Գրաֆները դիսկրետ մաթեմատիկա բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։
Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք գրաֆների տեսության բառարան։
Բովանդակություն
1 Սահմանումներ
2 Կիրառություններ
3 Գրաֆների պատկերում
4 Գրաֆների տեսության խնդիրներ
4.1 Ենթագրաֆներ, մինորներ
4.2 Գրաֆների ներկումներ
4.2.1 Գագաթային ներկումներ
4.2.2 Կողային ներկումներ
4.2.3 Տոտալ ներկումներ
4.3 Շրջանցումներ
5 Ծանոթագրություններ
6 Հղումներ
Սահմանումներ |
Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)
Գրաֆը սահմանվում է որպես կարգավոր զույգ G=(V,E)displaystyle G=(V,E), որտեղ V-ն գագաթների (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ կողերի (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ)։ Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են չկողմնորոշված և հասարակ գրաֆներ։
Կողին պատկանող գագաթները կոչվում են այդ գագաթի ծայրակետեր: Հաճախ u,vdisplaystyle u,v կողը կրճատ նշանակում են uvdisplaystyle uv-ով։
Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն։ Այսպես սահմանվող օբյեկտները կոչվում են մուլտիգրաֆներ: Գագաթների միևնույն զույգի միջև մեկից ավելի կողերը կոչվում են պատիկ կողեր։ Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով օղակ), այդ դեպքում ասում են, որ գործ ունենք պսևդոգրաֆի հետ։
Սովորաբար V և E բազմությունները ընդունվում են վերջավոր։ Հակառակ դեպքում գործ ունենք անվերջ գրաֆների հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն։ Գրաֆի կարգը գագաթների բազմության հզորությունն է։ Որևէ գագաթի աստիճանը այդ գագաթին միացած կողերի քանակն է։ Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ։
Կիրառություններ |
Գագաթները Վիքիպեդիայի լեզվական տարբերակներն են։ Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ[1]
Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ։ Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային ալգորիթմներով։
Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն։ Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև։ Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային տվյալների հենքեր։ Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը)։
Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը։
Գրաֆների պատկերում |
Մեծ սոցիալական գրաֆի պատկերում ուժային ալգորիթմով
Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով։ Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով։ Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ։
Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին։ Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է։ Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ[2]:
Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են հարթ գրաֆներ: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի խաչումների թիվ[3]: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի։ Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են։ Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է տոպոլոգիական գրաֆների տեսությունը:
Գրաֆների տեսության խնդիրներ |
Ենթագրաֆներ, մինորներ |
Պետերսենի գրաֆը հարթ չէ։ Այն պարունակում է ինչպես K5 մինոր (ձախից), այնպես էլ K3,3 մինոր (աջից): Պետերսենի գրաֆը պատկերված է փոքր գագաթներով և սև կողերով։ Դեղին գույնով նշված են մինորները։
Գրաֆների տեսության հետաքրքիր խնդիրներից է ենթագրաֆների իզոմորֆիզմի խնդիրը, երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի ենթագրաֆի գոյությունը։ Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) ժառանգական են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը։ Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է։ Մասնավորապես, տրված գրաֆում ամենամեծ լրիվ գրաֆ ենթագրաֆի գտնելը NP-լրիվ խնդիր է[4]:
Նման խնդիրներ դրվում են նաև ծնված ենթագրաֆների համար։ Այս խնդիրներն էլ հաճախ բարդ են։ Օրինակ, տրված գրաֆում մեծագույն անկախ բազմություն գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է։
Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը։ H գրաֆը կոչվում է G գրաֆի մինոր, եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր կծկելով: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է։ Վագների թեորեմը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում K3,3displaystyle K_3,3 լրիվ երկկողմանի գրաֆը և K5displaystyle K_5 լրիվ գրաֆը որպես մինոր։
Գրաֆների ներկումներ |
Պետերսենի գրաֆի ճիշտ գագաթային ներկում 3 գույներով։ Ավելի քիչ գույներով ճիշտ ներկում կառուցել հնարավոր չէ
Գրաֆների տեսության բազմաթիվ խնդիրներում գրաֆի տարբեր տարրերին (կող, գագաթ և այլն) համապատասխանեցվում են գույներ կամ թվեր։ Այդպիսի արտապատկերումները գրաֆի տարրերից թվերին կոչվում են ներկումներ:
Գագաթային ներկումներ |
Ճիշտ գագաթային ներկման դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր։ Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր վվգույն։ Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում։ Այդ թիվը կոչվում է գրաֆի քրոմատիկ թիվ: Դրա որոշումը NP-լրիվ խնդիր է[5], սակայն հայտնի են բազմաթիվ գնահատականներ։ Օրինակ, ըստ Բրուքսի թեորեմի[6], գրաֆի քրոմատիկ թիվը չի գերազանցում գրաֆի առավելագույն աստիճանը, բացառությամբ ցիկլերի և լրիվ գրաֆների։
Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են։ Չորս գույների թեորեմի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում
Հարթ գրաֆների դեպքում քրոմատիկ թիվը գտնելու խնդիրը հայտնի է որպես քարտեզ ներկելու խնդիր։ Եթե երկրներին (կամ ցանկացած տարածքային միավորին) համպատախասնեցվեն գագաթներ հարթության վրա, իսկ հարևան երկրները միացվեն կողերով, ապա ճիշտ գագաթների ներկումը կհամապատասխանի քարտեզի ներկմանը։ Չորս գույների թեորեմի համաձայն, հարթ գրաֆի քրոմատիկ թիվը չորսից մեծ չէ, հետևաբար ցանկացած քարտեզ ներկելու համար բավարար է օգտագործել չորս գույն։
Ճիշտ գագաթային ներկումների հայտնի չլուծված խնդիրներից է Հադվիգերի հիպոթեզը, ըստ որի k քրոմատիկ թիվ ունեցող գրաֆը պետք է պարունակի k-գագաթանի լրիվ գրաֆը որպես մինոր։ Այս հիպոթեզը չորս գույների թեորեմի ընդհանրացումն է։
Կողային ներկումներ |
Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ճիշտ կողային ներկում: Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի քրոմատիկ դաս, որը հաշվելը ևս NP-լրիվ խնդիր է։ Վիզինգի թեորեմի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով։
Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի կողային գրաֆի ճիշտ գագաթային ներկմանը։
Ինչպես գագաթային, այնպես էլ կողային ներկումների համար սահմանվում են ցուցակային ներկումներ, երբ յուրաքանչյուր գագաթի (կողի) համապատասխանեցվում է գույների ցուցակ, որտեղից անհրաժեշտ է ընտրել գույներ այնպես, որ ստացված ներկումը լինի ճիշտ։ Կողային ցուցակային ներկման հիպոթեզի համաձայն, ցանկացած օղակ չպարունակող մուլտիգրաֆի համար կողային ցուցակային քրոմատիկ թիվը պետք է հավասար լինի գրաֆի քրոմատիկ դասին։ Այս խնդիրը ևս լուծված չէ[7]:
Տոտալ ներկումներ |
Ներկումը կոչվում է տոտալ, երբ ներկվում են ինչպես գագաթները, այնպես էլ կողերը։ Այս ոլորտի ամենահայտնի խնդիրը տոտալ ներկման հիպոթեզն է, որը ձևակերպվել է Վիզինգի և Բեհզադի կողմից 1965 թ․ և մինչ այժմ լուծված չէ[8]:
Շրջանցումներ |
Քյոնիգսբերգ քաղաքի քարտեզը Էյլերի ապրած ժամանակաշրջանում, որտեղ հստակ երևում են յոթ կամուրջները
Գրաֆների տեսության առաջացումը կապվում է Էյլերի 1741 թվականին տպագրած հոդվածի հետ, որտեղ քննարկվում էր հետևյալ խնդիրը․ հնարավո՞ր է անցնել Քյոնիգսբերգ քաղաքի (այժմ՝ Կալինինգրադ, Ռուսաստան) 7 կամուրջներով, յուրաքանչյուրով ճիշտ մեկ անգամ[9]: Էյլերը ցույց տվեց, որ դա հնարավոր չէ։ Եթե քաղաքի գետերով բաժանված հատվածները դիտարկվեն որպես գրաֆի գագաթներ, իսկ կամուրջները՝ կողեր, ապա այս խնդիրը համարժեք է գրաֆում այնպիսի շղթայի գոյությանը, որն անցնում է բոլոր կողերով ճիշտ մեկ անգամ։ Այդպիսի շղթան կոչվում է Էյլերյան շղթա: Ըստ Էյլերի թեորեմի, Քյոնիգսբերգին համապատասխանող գրաֆում այդպիսի շղթա չի կարող գոյություն ունենալ։ Գրաֆում Էյլերյան շղթայի, ինչպես նաև էյլերյան ցիկլի (երբ շրջանցման սկիզբն ու վերջը համընկնում են) գոյությունը կարելի է պարզել բազմանդամային ժամանակում։
Էապես ավելի բարդ խնդիր է Համիլտոնյան ցիկլի գոյության խնդիրը։ Այս դեպքում պահանջվում է, որ ցիկլը անցնի յուրաքանչյուր գագաթով ճիշտ մեկ անգամ։ Գրաֆում համիլտոնյան ցիկլի գոյության համար հայտնի են բազմաթիվ բավարար պայմաններ։ Սակայն ընդհանուր դեպքում խնդիրը NP-լրիվ է նույնիսկ հարթ գրաֆների համար, որոնց առավելագույն աստիճանը երեք է[10]:
Ծանոթագրություններ |
↑ Scott Hale, Multilinguals and Wikipedia Editing, 2013
↑ Գրաֆների պատկերում (անգլերեն)
↑ Խաչումների թվի մասին Wolfram MathWorld-ում
↑ Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ Wolfram MathWorld: Clique Number
↑ Քրոմատիկ թվի մասին Wolfram MathWorld-ում
↑ Բրուքսի թեորեմը Wolfram MathWorld-ում
↑ Կողային ցուցակային ներկման հիպոթեզը Open Problem Garden-ում
↑ Տոտալ ներկման հիպոթեզը Open Problem Garden-ում
↑ The Euler Archive Էյլերի հոդվածի բնօրինակ տեքստը լատիներենով և մի շարք օգտակար հղումներ
↑ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi: .
Հղումներ |
- Գրաֆների տեսություն - ուսումնամեթոդական ձեռնարկ
PathFinding.js Ցանցանման գրաֆի վրա կարճագույն ճանապարհ փնտրող ալգորիթմների գրադարան ՋավաՍկրիպտ լեզվով և ալգորիթմների վիզուալիզացիա
Graph Tea գրաֆների հետ աշխատող ծրագիր- Փոքր կապակցված գրաֆների որոնողական համակարգ
 | Վիքիպահեստ նախագծում կարող եք այս նյութի վերաբերյալ հավելյալ պատկերազարդում գտնել Գրաֆների տեսություն կատեգորիայում։ |
Կատեգորիաներ:
- Գրաֆների տեսություն
- Ինֆորմատիկա
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.144","walltime":"0.276","ppvisitednodes":"value":1026,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":8507,"limit":2097152,"templateargumentsize":"value":1509,"limit":2097152,"expansiondepth":"value":13,"limit":40,"expensivefunctioncount":"value":1,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":5199,"limit":5000000,"entityaccesscount":"value":2,"limit":400,"timingprofile":["100.00% 111.477 1 -total"," 63.83% 71.159 1 Կաղապար:ՎՊԵ"," 57.18% 63.743 2 Կաղապար:Wikidata"," 36.07% 40.207 1 Կաղապար:Ծանցանկ"," 26.42% 29.452 1 Կաղապար:Citation"," 18.76% 20.915 1 Կաղապար:Citation/core"," 2.89% 3.221 2 Կաղապար:Citation/make_link"," 1.83% 2.045 1 Կաղապար:InterProject"],"scribunto":"limitreport-timeusage":"value":"0.031","limit":"10.000","limitreport-memusage":"value":1198909,"limit":52428800,"cachereport":"origin":"mw1250","timestamp":"20190419060633","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"u0533u0580u0561u0586u0576u0565u0580u056b u057fu0565u057du0578u0582u0569u0575u0578u0582u0576","url":"https://hy.wikipedia.org/wiki/%D4%B3%D6%80%D5%A1%D6%86%D5%B6%D5%A5%D6%80%D5%AB_%D5%BF%D5%A5%D5%BD%D5%B8%D6%82%D5%A9%D5%B5%D5%B8%D6%82%D5%B6","sameAs":"http://www.wikidata.org/entity/Q131476","mainEntity":"http://www.wikidata.org/entity/Q131476","author":"@type":"Organization","name":"Contributors to Wikimedia projects","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2012-04-23T13:37:27Z","dateModified":"2019-03-19T09:10:10Z","image":"https://upload.wikimedia.org/wikipedia/commons/7/75/Complete_graph_K6.svg"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":148,"wgHostname":"mw1267"););
