Գրաֆների տեսություն

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Վեց գագաթանի լրիվ գրաֆ K_6

Մաթեմատիկայում և համակարգչային գիտության մեջ գրաֆների տեսությունը ուսումնասիրում է գրաֆները, որոնք օբյեկտների միջև զույգ առ զույգ կապերը մոդելավորող մաթեմատիկական օբյեկտներ են: Գրաֆը կազմված է գագաթներից (կամ հանգույցներից) և կողերից, որոնք միացնում են գագաթների որոշ զույգեր:

Գրաֆը կարող է լինել չուղղորդված (չկողմնորոշված), երբ յուրաքանչյուր կողի երկու ծայրակետերը համարժեք են, կամ կողերը կարող են ուղղորդված (կողմնորոշված) լինել մի ծայրակետից մյուսը: Գրաֆները դիսկրետ մաթեմատիկա բաժնում ուսումնասիրվող պարզագույն օբյեկտներից են։

Գրաֆների տեսության հիմնական հասկացությունների համար այցելեք գրաֆների տեսության բառարան։

Սահմանումներ[խմբագրել]

Սա չկողմնորոշված պսևդոգրաֆ է, քանի որ պարունակում է ինչպես պատիկ կողեր (կարմիր), այնպես էլ օղակներ (կապույտ)

Գրաֆը սահմանվում է որպես կարգավոր զույգ G=(V,E), որտեղ V-ն գագաթների (կամ հանգույցների) բազմությունն է, իսկ E-ն՝ կողերի (գծերի), որոնք V բազմության երկու տարրանոց ենթաբազմություններ են (այսինքն, կողը բնութագրվում է որպես երկու տարբեր գագաթների չկարգավորված զույգ): Գրականությունում հանդիպող այլ սահմանումներից տարբերելու համար այսպես սահմանվող գրաֆները երբեմն կոչում են չկողմնորոշված և հասարակ գրաֆներ:

Կողին պատկանող գագաթները կոչվում են այդ գագաթի ծայրակետեր: Հաճախ \{u, v\} կողը կրճատ նշանակում են uv-ով:

Երբեմն E բազմությունը սահմանվում է որպես (իրարից տարբեր) գագաթների չկարգավորված զույգերի մուլտիբազմություն: Այսպես սահմանվող օբյեկտները կոչվում են մուլտիգրաֆներ: Գագաթների միևնույն զույգի միջև մեկից ավելի կողերը կոչվում են պատիկ կողեր: Եթե թույլատրվում են նաև այնպիսի կողեր, որոնց երկու ծայրերն էլ միանում են միևնույն գագաթին (առաջացնելով օղակ), այդ դեպքում ասում են, որ գործ ունենք պսևդոգրաֆի հետ:

Սովորաբար V և E բազմությունները ընդունվում են վերջավոր: Հակառակ դեպքում գործ ունենք անվերջ գրաֆների հետ, որոնց համար վերջավոր գրաֆների բազմաթիվ հատկություններ տեղի չունեն: Գրաֆի կարգը գագաթների բազմության հզորությունն է: Որևէ գագաթի աստիճանը այդ գագաթին միացած կողերի քանակն է: Պսևդոգրաֆների դեպքում, երբ որևէ կողի երկու ծայրերն էլ միացած են միևնույն գագաթին, այդպիսի կողերը (օղակները) հաշվվում են երկու անգամ:

Կիրառություններ[խմբագրել]

Գագաթները Վիքիպեդիայի լեզվական տարբերակներն են: Կողերով միացված են այն տարբերակները, որոնցում խմբագրումներ կատարել է միևնույն մասնակիցը 2013-ի ամռանը կատարված հետազոտության ժամանակ [1]

Գրաֆները կիրառվում են ֆիզիկայի, քիմիայի, կենսաբանության, սոցիալական և ինֆորմացիոն համակարգերի մոդելավորման մեջ: Այս և այլ ոլորտներում ծագող բազմաթիվ խնդիրներ արդյունավետ կերպով լուծվում են գրաֆային ալգորիթմներով:

Համակարգչային գիտություններում գրաֆներով մոդելավորում են համակարգչային ցանցերը, տվյալների կառուցվածքները, հաշվարկի ընթացքը և այլն: Օրինակ, որպես գագաթների բազմություն կարելի է ընտրել ինտերնետային կայքերը, իսկ կայքերի միջև հղումները կդառնան ուղղորդված կողեր գագաթների միջև: Գրաֆների միջոցով ներկայացվող տվյալները արդյունավետ պահելու և կառավարելու համար գոյություն ունեն գրաֆային տվյալների հենքեր: Գրաֆների տեսությամբ են մոդելավորվում գերմեծ ինտեգրալ սխեմաների նախագծման ժամանակ առաջացող բազմաթիվ խնդիրներ (օրինակ՝ routing-ի խնդիրը):

Քիմիայում և պինդ մարմնի ֆիզիկայում գրաֆների միջոցով մոդելավորում են ատոմները և նրանց միջև կապերը:

Գրաֆների պատկերում[խմբագրել]

Մեծ սոցիալական գրաֆի պատկերում ուժային ալգորիթմով

Գրաֆները հաճախ ներկայացվում են հարթության վրա պատկերի միջոցով: Յուրաքանչյուր գագաթի համար պատկերվում է կետ կամ շրջան, իսկ կողերը ներկայացվում են գագաթները միացնող կորերով: Ուղղորդված գրաֆների դեպքում կորերի մի ծայրում պատկերվում են սլաքներ:

Ակնհայտորեն, միևնույն գրաֆը կարելի է պատկերել տարբեր ձևերով, և ընդհանուր դեպքում դժվար է ճանաչել, թե երբ են տարբեր պատկերները համապատասխանում միևնույն գրաֆին: Գրաֆների գեղեցիկ կամ հարմար պատկերումը գրաֆների տեսության բարդագույն խնդիրներից է: Մշակված են մի շարք որակի չափանիշներ (կողերի հատումների թիվը, համաչափությունը, գագաթների հեռավորությունը իրենցով չանցնող կողերից և այլն), ինչպես նաև բազմաթիվ պատկերման ալգորիթմներ [2]:

Այն գրաֆները, որոնք հնարավոր է պատկերել հարթության վրա այնպես, որ կողերը չհատվեն, կոչվում են հարթ գրաֆներ: Ընդհանուր դեպքում, կողերի հատումների նվազագույն քանակը, որին կարելի է հասնել գրաֆը հարթության վրա պատկերելիս, կոչվում է գրաֆի խաչումների թիվ [3]: Հարթ գրաֆների խաչումների թիվը հավասար է զրոյի: Հարթ գրաֆների հետազոտությունը, ինչպես տրված գրաֆի խաչումների թիվը հաշվելը գրաֆների տեսության հայտնի խնդիրներից են: Գրաֆների պատկերման խնդիրները այլ մակերևույթների վրա (օրինակ՝ տոռերի) ուսումնասիրում է տոպոլոգիական գրաֆների տեսությունը:

Գրաֆների տեսության խնդիրներ[խմբագրել]

Ենթագրաֆներ, մինորներ[խմբագրել]

Պետերսենի գրաֆը հարթ չէ: Այն պարունակում է ինչպես K5 մինոր (ձախից), այնպես էլ K3,3 մինոր (աջից): Պետերսենի գրաֆը պատկերված է փոքր գագաթներով և սև կողերով: Դեղին գույնով նշված են մինորները:

Գրաֆների տեսության հետաքրքիր խնդիրներից է ենթագրաֆների իզոմորֆիզմի խնդիրը, երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի ենթագրաֆի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) ժառանգական են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ լրիվ գրաֆ ենթագրաֆի գտնելը NP-լրիվ խնդիր է[4]:

Նման խնդիրներ դրվում են նաև ծնված ենթագրաֆների համար: Այս խնդիրներն էլ հաճախ բարդ են: Օրինակ, տրված գրաֆում մեծագույն անկախ բազմություն գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է:

Հայտնի խնդիր է տրված գրաֆում որոշակի մինորների գոյության հարցը: H գրաֆը կոչվում է G գրաֆի մինոր, եթե այն ստացվում է G-ից գագաթներ և կողեր հեռացնելով, ինչպես նաև կողեր կծկելով: Գրաֆների շատ հատկանիշներ ժառանգական են մինորների նկատմամբ, որոնցից թերևս ամենահայտնին գրաֆի հարթ լինելու պայմանն է: Վագների թեորեմը պնդում է, որ գրաֆը հարթ է այն և միայն դեպքում, երբ այն չի պարունակում K_{3,3} լրիվ երկկողմանի գրաֆը և K_5 լրիվ գրաֆը որպես մինոր:

Գրաֆների ներկումներ[խմբագրել]

Պետերսենի գրաֆի ճիշտ գագաթային ներկում 3 գույներով: Ավելի քիչ գույներով ճիշտ ներկում կառուցել հնարավոր չէ

Գրաֆների տեսության բազմաթիվ խնդիրներում գրաֆի տարբեր տարրերին (կող, գագաթ և այլն) համապատասխանեցվում են գույներ կամ թվեր: Այդպիսի արտապատկերումները գրաֆի տարրերից թվերին կոչվում են ներկումներ:

Գագաթային ներկումներ[խմբագրել]

Ճիշտ գագաթային ներկման դեպքում գագաթներին համապատասխանեցվում են գույներ (թվեր) այնպես, որ հարևան գագաթների գույները լինեն տարբեր: Ակնհայտորեն, բոլոր գրաֆները ունեն այդպիսի ներկումներ, քանի որ կարելի է ամեն գագաթին համապատասխանեցնել մի նոր գույն: Սակայն խնդիր է առաջանում գտնել գույների ամենափոքր թիվը, որոնցով կարելի է ապահովել ճիշտ գագաթային ներկում: Այդ թիվը կոչվում է գրաֆի քրոմատիկ թիվ: Դրա որոշումը NP-լրիվ խնդիր է[5], սակայն հայտնի են բազմաթիվ գնահատականներ: Օրինակ, ըստ Բրուքսի թեորեմի [6], գրաֆի քրոմատիկ թիվը չի գերազանցում գրաֆի առավելագույն աստիճանը, բացառությամբ ցիկլերի և լրիվ գրաֆների:

Աշխարհի քարտեզը ներկված չորս գույներով․ հարևան երկրները տարբեր գույներով են: Չորս գույների թեորեմի համաձայն, ցանկացած քարտեզ ունի այսպիսի ներկում

Հարթ գրաֆների դեպքում քրոմատիկ թիվը գտնելու խնդիրը հայտնի է որպես քարտեզ ներկելու խնդիր: Եթե երկրներին (կամ ցանկացած տարածքային միավորին) համպատախասնեցվեն գագաթներ հարթության վրա, իսկ հարևան երկրները միացվեն կողերով, ապա ճիշտ գագաթների ներկումը կհամապատասխանի քարտեզի ներկմանը: Չորս գույների թեորեմի համաձայն, հարթ գրաֆի քրոմատիկ թիվը չորսից մեծ չէ, հետևաբար ցանկացած քարտեզ ներկելու համար բավարար է օգտագործել չորս գույն:

Ճիշտ գագաթային ներկումների հայտնի չլուծված խնդիրներից է Հադվիգերի հիպոթեզը, ըստ որի k քրոմատիկ թիվ ունեցող գրաֆը պետք է պարունակի k-գագաթանի լրիվ գրաֆը որպես մինոր: Այս հիպոթեզը չորս գույների թեորեմի ընդհանրացումն է:

Կողային ներկումներ[խմբագրել]

Երբ գագաթների փոխարեն ներկվում են կողերը և պահանջ է դրվում, որ կից կողերը ունենան տարբեր գույներ, այդպիսի ներկումը կոչվում է ճիշտ կողային ներկում: Ճիշտ կողային ներկման դեպքում նվազագույն գույների քանակը կոչվում է գրաֆի քրոմատիկ դաս, որը հաշվելը ևս NP-լրիվ խնդիր է: Վիզինգի թեորեմի համաձայն, քրոմատիկ դասը կարող է հավասար լինել գրաֆի առավելագույն աստիճանին, կամ դրանից մեծ լինել ճիշտ մեկով:

Գրաֆի ճիշտ կողային ներկումը համարժեք է գրաֆի կողային գրաֆի ճիշտ գագաթային ներկմանը:

Ինչպես գագաթային, այնպես էլ կողային ներկումների համար սահմանվում են ցուցակային ներկումներ, երբ յուրաքանչյուր գագաթի (կողի) համապատասխանեցվում է գույների ցուցակ, որտեղից անհրաժեշտ է ընտրել գույներ այնպես, որ ստացված ներկումը լինի ճիշտ: Կողային ցուցակային ներկման հիպոթեզի համաձայն, ցանկացած օղակ չպարունակող մուլտիգրաֆի համար կողային ցուցակային քրոմատիկ թիվը պետք է հավասար լինի գրաֆի քրոմատիկ դասին: Այս խնդիրը ևս լուծված չէ [7]:

Տոտալ ներկումներ[խմբագրել]

Ներկումը կոչվում է տոտալ, երբ ներկվում են ինչպես գագաթները, այնպես էլ կողերը: Այս ոլորտի ամենահայտնի խնդիրը տոտալ ներկման հիպոթեզն է, որը ձևակերպվել է Վիզինգի և Բեհզադի կողմից 1965թ․ և մինչ այժմ լուծված չէ [8]:

Շրջանցումներ[խմբագրել]

Քյոնիգսբերգ քաղաքի քարտեզը Էյլերի ապրած ժամանակաշրջանում, որտեղ հստակ երևում են յոթ կամուրջները

Գրաֆների տեսության առաջացումը կապվում է Էյլերի 1741 թվականին տպագրած հոդվածի հետ, որտեղ քննարկվում էր հետևյալ խնդիրը․ հնարավո՞ր է անցնել Քյոնիգսբերգ քաղաքի (այժմ՝ Կալինինգրադ, Ռուսաստան) 7 կամուրջներով, յուրաքանչյուրով ճիշտ մեկ անգամ[9]: Էյլերը ցույց տվեց, որ դա հնարավոր չէ: Եթե քաղաքի գետերով բաժանված հատվածները դիտարկվեն որպես գրաֆի գագաթներ, իսկ կամուրջները՝ կողեր, ապա այս խնդիրը համարժեք է գրաֆում այնպիսի շղթայի գոյությանը, որն անցնում է բոլոր կողերով ճիշտ մեկ անգամ: Այդպիսի շղթան կոչվում է Էյլերյան շղթա: Ըստ Էյլերի թեորեմի, Քյոնիգսբերգին համապատասխանող գրաֆում այդպիսի շղթա չի կարող գոյություն ունենալ: Գրաֆում Էյլերյան շղթայի, ինչպես նաև էյլերյան ցիկլի (երբ շրջանցման սկիզբն ու վերջը համընկնում են) գոյությունը կարելի է պարզել բազմանդամային ժամանակում:

Էապես ավելի բարդ խնդիր է Համիլտոնյան ցիկլի գոյության խնդիրը: Այս դեպքում պահանջվում է, որ ցիկլը անցնի յուրաքանչյուր գագաթով ճիշտ մեկ անգամ: Գրաֆում համիլտոնյան ցիկլի գոյության համար հայտնի են բազմաթիվ բավարար պայմաններ: Սակայն ընդհանուր դեպքում խնդիրը NP-լրիվ է նույնիսկ հարթ գրաֆների համար, որոնց առավելագույն աստիճանը երեք է [10]:

Ծանոթագրություններ[խմբագրել]

  1. Scott Hale, Multilinguals and Wikipedia Editing, 2013 [1]
  2. Գրաֆների պատկերում (անգլերեն)
  3. Խաչումների թվի մասին Wolfram MathWorld-ում
  4. Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ Wolfram MathWorld: Clique Number
  5. Քրոմատիկ թվի մասին Wolfram MathWorld-ում
  6. Բրուքսի թեորեմը Wolfram MathWorld-ում
  7. Կողային ցուցակային ներկման հիպոթեզը Open Problem Garden-ում
  8. Տոտալ ներկման հիպոթեզը Open Problem Garden-ում
  9. The Euler Archive Էյլերի հոդվածի բնօրինակ տեքստը լատիներենով և մի շարք օգտակար հղումներ
  10. Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proc. 6th ACM Symposium on Theory of Computing (STOC '74), doi:10.1145/800119.803884 .

Հղումներ[խմբագրել]