Գրաֆների ներկում

Գրաֆների տեսությունում գրաֆների ներկումը գրաֆների պիտակման հատուկ դեպք է․ այն, ըստ որոշակի սահմանափակումների, գրաֆի տարրերին պիտակների նշանակում է, որոնք ավանդաբար կոչվում են «գույներ»։ Ամենապարզ տեսքով այն գրաֆի գագաթների ներկում է այնպես, որ երկու հարևան գագաթներ նույն գույնը չունենան (կոչվում է գագաթային ներկում)։ Նմանապես կողային ներկումը գրաֆի յուրաքանչյուր կողին գույնի նշանակում է այնպես, որ երկու հարևան կողեր չունենան նույն գույնը։ Հարթ գրաֆների նիստային ներկման դեպքում գրաֆի յուրաքանչյուր նիստ ներկվում է այնպես, որ ընդհանուր կող ունեցող նիստերը տարբեր գույն ունենան։

Գրաֆի ներկման խնդիրները սովորաբար ձևակերպվում են գագաթային ներկման խնդրի տեսքով, քանի որ ներկման այլ խնդիրները կարելի է վերաձևակերպել գագաթային ներկման տեսքով։ Օրինակ՝ գրաֆի կողային ներկումը համապատասխանում է գրաֆի կողային գրաֆի գագաթային ներկմանը, հարթ գրաֆի նիստային ներկումը համապատասխանում է նույն գրաֆի երկակի գրաֆի գագաթային ներկմանը։ Սակայն, ոչգագաթային ներկման խնդիրները հաճախ ուսումնասիրվում են հենց այդպես։ Սա մասամբ մանկավարժական ընտրության պատճառով է, բացի դա, որոշ խնդիրներ ավելի հեշտ է ուսումնասիրել իրենց «ոչգագաթային» տեսքով։ 

Գույներով պիտակելու ավանդույթը կապված քարտեզում երկրների ներկման հետ։ Սրա ընդհանրացումը հարթության վրա պատկերված գրաֆների նիստերի ներկումն է։ Հարթ երկակիության միջոցով այն հնարավոր է ներկայանցել գագաթային ներկման միջոցով, ինչը հնարավորություն է տվել խնդիրը ընդհանրացնել բոլոր տեսակի գրաֆների համար։ Մաթեմատիկական և համակարգչային ներկայացումներում ընդունված է «գույները» ներկայանցել առաջին դրական կամ բացասական ամբողջ թվերի միջոցով։ Ընդհանուր առմամբ, կամայական վերջավոր բազմություն կարելի է օգտագործել որպես «գույների բազմություն»։ 

Գրաֆների ներկումը ունի ինչպես բազմաթիվ պրակտիկ կիրառություններ, այնպես էլ տեսական մարտահրավերներ։ Խնդիրների դասական տեսակներից բացի հնարավոր է տարբեր սահմանափակումներ դնել գրաֆների, գույների նշանակման կամ առհասարակ գույների վրա։ Գրաֆների ներկումը այժմ ակտիվ հետազոտությունների առարկա է։

Պատմություն 
Առաջին արդյունքները ստացվել են քարտեզների գունավորման խնդրի հարթ գրաֆների գունավորման  համար։ Փորձելով գունավորել Անգլիայի գավառների քարտեզը՝  Ֆրանցիս Գուտրին  ձևակերպել է չորս գույների թեորեմը՝  նշելով, որ չորս գույները բավարար են քարտեզը գունավորելու համար այնպես, որ հարակից ցանկացած երկու շրջաններ ունենան տարբեր գույներ։ Նրա եղբայրը հարցը փոխանցել է մաթեմատիկայի իր ուսուցչին՝ Օգաստես դե Մորգանին, որն այդ մասին նշել է 1852 թվականին Ուիլյամ Համիլտոնին ուղղված նամակում։ Արթուր Քելին այս հարցը բարձրացրել է 1878 թվականին Լոնդոնի մաթեմատիկական ընկերության ժողովում։   Նույն թվականին Թեյթն առաջարկել է այս խնդրի առաջին լուծումը։ Սկզբնական գրաֆի գագաթների գունավորումը նա հանգեցրել է երկակի գրաֆի կողերի գունավորմանը և ենթադրել, որ այս խնդիրը միշտ լուծում կունենա: 1880 թվականին Ալֆրեդ Քեմպեն հրապարակել է մի հոդված,  որում ասվում է, որ նրան հաջողվել է գտնել խնդրի լուծումը, և մել տասնամյակի ընթացքում չորս գույների խնդիրը համարվել է լուծված։ Այս նվաճման համար Քեմպեն ընտրվել է Լոնդոնի թագավորական ընկերության անդամ, իսկ ավելի ուշ՝  Լոնդոնի մաթեմատիկական ընկերության նախագահ։

1890 թվականին Հիվուդը սխալ է գտել Քեմպեի ապացույցում։  Նույն հոդվածում նա ապացուցել է հինգ գույների թեորեմը՝  ցույց տալով, որ ցանկացած հարթ քարտեզ կարելի է ներկել ոչ ավելի, քան հինգ գույներով։ Միևնույն ժամանակ, նա հենվել է Քեմպեի գաղափարների վր։ Հաջորդ դարում մշակվել են մեծ թվով թեորեմներ` փորձելով նվազեցնել գույների քանակը։ Չորս գույների թեորեմը վերջապես ապացուցվել է 1977 թվականին՝ Քենեթ Ապելի և Վոլֆգանգ Հակենի կողմից՝ օգտագործելով համակարգչային ընտրություն։ Ապացույցի գաղափարը մեծապես հիմնվել է Հիվուդի և Քեմպեի գաղափարների վրա և անտեսել միջանկյալ ուսումնասիրությունների մեծ մասը: Չորս գույների թեորեմի ապացույցն առաջին ապացույցներից մեկն է, որում օգտագործվել է համակարգիչ։

1912 թվականին Ջորջ Դեյվիդ Բիրքհոֆն առաջարկել է գունավորման խնդրի լուծման համար օգտագործել քրոմատիկ  բազմանդամ, որը կարևոր մաս է գրաֆների հանրահաշվական տեսության մեջ։ Քրոմատիկ բազմանդամը հետագայում ընդհանրացվել է Ուիլյամ Թաթթի կողմից (Թաթթի բազմանդամ)։ 1879 թվականին Քեմպեն ուշադրություն է հրավիրել այն ընդհանուր դեպքի վրա, երբ գրաֆը հարթ չէ: Ավելի բարձր կարգի մակերեսների վրա հարթ գրաֆների ներկման ընդհանրացումների բազմաթիվ արդյունքներ հայտնվել են XX դարի սկզբին։

1960 թվականին Կլոդ Բերջը ձևակերպել է կատարյալ գրաֆների վարկածը, որը հիմնավորված էր ինֆորմացիայի տեսության գաղափարից, մասնավորապես Շենոնի ներկայացրած գրաֆի տարողության զրոյական սխալից: Պնդումը մնացել է չհաստատված 40 տարի, մինչև հաստատվել է որպես կատարյալ գրաֆների մասին հայտնի կոշտ թեորեմ մաթեմատիկոսներ Չուդնովսկայա, Ռոբերտսոնի,  Սեյմուրի և Թոմասի կողմից 2002 թվականին։

Գրաֆների գունավորումը՝ որպես ալգորիթմական խնդիր, սկսել է ուսումնասիրվել 1970 թվականներից։ Քրոմատիկ համարի որոշումը ներառվում է Կարպի 21 NP-ամբողջական խնդիրների թվում (1972 թվական)։ Եվ մոտավորապես նույն ժամանակ մշակվել են տարբեր ալգորիթմներ այդ  հետադարձ որոնման և  Զիկովի հետադարձման հեռացման և հետ կանչման հիման վրա։ 1981 թվականից գրաֆների գունավորումն օգտագործվում է կոմպիլյատորներում ռեգիստրերի բաշխման համար:

Սահմանում և տերմինաբանություն

Գագաթների ներկում 

Գրաֆները ներկելու մասին խոսելիս գրեթե միշտ նկատի է առնվում նրանց գագաթների ներկումը, այսինքն՝ գրաֆի գագաթներին այնպիսի գույներ տալը, որպեսզի ընդհանուր կող ունեցող երկու գագաթներն ունենան տարբեր գույներ։ Քանի որ հանգույցներով գրաֆները չեն կարող ներկվել այս կերպ, դրանք քննարկման առարկա չեն։

Տերմինաբանությունը, որում պիտակները կոչվում են գույներ, գալիս է քաղաքական քարտեզների գունավորումից։ Կարմիր կամ կապույտ գույներն օգտագործվում են միայն այն դեպքում, երբ գույների քանակը փոքր է, սովորաբար ենթադրվում է, որ գույները ամբողջ թվեր են ։

 գւյների օգտագործմամբ ներկումը կոչվում է -ներկում։ Գրաֆը ներկելու  համար անհրաժեշտ գույների նվազագույն քանակը՝ , կոչվում է նրա քրոմատիկ թիվ և հաճախ գրանցվում է որպես  ։ Երբեմն օգտագործվում է  ,  քանի որ  նշում է Էյլերի բնութագիրը։ Մի գույնով նշված գագաթների ենթաբազմությունը կոչվում է գունային դաս, յուրաքանչյուր այդպիսի դաս կազմում է անկախ հավաքակազմ։ Այսպիսով, -ներկումը նույնն է, ինչ գագաթների բաժանումը   անկախ հավաքածուների։

Քրոմատիկ թիվը Գրոմով-Հաուսդորֆի հեռավորության տերմիններում 
Դիցուք G-ն կամայական գրաֆ է գագաթների V  բազմությամբ։ Վերցնենք երկու դրական իրական թվեր   , և  դիտարկենք  որպես մետրային տարածք, որտեղ հարակից գագաթների միջև հեռավորությունը հավասար է  , իսկ մյուս ոչ զրոյական բոլոր հեռավորությունները հավասար են  ։ Նշանակենք   մետրական տարածությունը, որը բաղկացած միմյանցից    հեռավորության վրա գտնվող  կետերից։ Վերջապես,   և  ցանկացած երկու մետրային տարածքների համար,   միջոցով   նշանակեք Գրոմով-Հաուսդորֆի հեռավորությունը  և  միջև։  Այնուհետև կստացվի  հետևյալ արդյունքը՝

 Թեորեմ (Ա. Իվանով, Ա. Տուժիլին)․ դիցուք m ամենամեծ բնական թիվն է, որի համար   (եթե նման բնական թվեր գոյություն չունեն, ապա ենթադրենք )։ Այդ դեպքում՝ ։

Դիտարկում․
  քրոմատիկ թիվը հավասար է  այն և միայն այն դեպքում, եթե   գրաֆը չի պարունակում ոչ մի կող։ Այս դեպքում  հավասարությունը հնարավոր չէ ոչ մի m-ի համար, հետևաբար, կատարված պայմանավորվածության համաձայն, , ինչը հանգեցնում էհետևյալ ճիշտ հավասարության՝  ։
 Ըստ սահմանման,  չի գերազանցում  բազմության   տարրերի քանակին։ Մյուս կողմից, դժվար չէ ցույց տալ, որ  յուրաքանչյուր -ի համար, ուստի , և նշանակում է, որ ։

Քրոմատիկ բազմանդամ 

Քրոմատիկ   բազմանդամը   ֆունկցիա է, որը հաշվում է   գրաֆի t-ներկումների քանակը։ Անունից հետևում է, որ տրված  -ն  բազմանդամ է`  կախված t-ից։ Այս փաստը հայտնաբերվել է Բիրկհոֆի և Լյուիսի կողմից՝ չորս գույների թեորեմի ապացուցման փորձի ժամանակ: 
Օրինակ աջ կողմի պատկերի գրաֆը կարելի է ներկել 3 գույներով 12 եղանակով։ Երկու գույներով   այն սկզբունքորեն չի կարելի նկարել։ Օգտագործելով 4 գույն՝ ստանում ենք 24 + 4 * 12 = 72 ներկման ընտրանքներ։ Բոլոր 4 գույներն օգտագործելիս կա 4! = 24 ճիշտ մեթոդ (4 գագաթներից ցանկացած գրաֆի համար 4 գույներից յուրաքանչյուրի վերագրումը ճիշտ է),  իսկ 4-ից յուրաքանչյուր 3 գույների համար ներկման 12 եղանակ կա։ Այդ դեպքում, օրինակի գրաֆի համար, ճիշտ ներկումների թվերի աղյուսակը կսկսվի այսպես.

Օրինակի գրաֆի համար՝ ,  և իհարկե՝ ։

Քրոմատիկ բազմանդամն առնվազն նույնքան տեղեկատվություն է պարունակում -ի ներկման ունակության մասին, որքան և քրոմատիկ թիվը։ Իրականում   ամենափոքր դրական ամբողջ թիվն է, որը քրոմատիկ բազմանդամի արմատ չէ։

Կողերի   ներկում 
Գրաֆի կողերի  ներկումը  ենթադրում  է կողերին այնպիսի գույներ տալը, որ նույն գագաթին պատկանող երկու կողեր չունենան նույն գույնը։ Այս առաջադրանքը համարժեք է կողերի բազմությունն անկախ կողերի բազմությունների բաժանելուն։   գրաֆի կողային ներկման համար պահանջվող գույների նվազագույն քանակը նրա քրոմատիկ ինդեքսն է կամ կողային քրոմատիկ թիվը՝ ։

Ընդհանուր ներկում 

Գրաֆների ընդհանուր ներկումը գագաթների և կողերի ներկման տեսակներից մեկն է։ Դա ենթադրում է նրանց տալ այնպիսի գույներ, որ ոչ հարևան կողերը, ոչ էլ գագաթներն ու նրանց միացնող կողերը չունենան նույն գույնը։  գրաֆի  քրոմատիկ ընդհանուր թիվն այն ամենափոքր թիվն է, որն անհրաժեշտ է ցանկացած ամբողջական ներկման համար։

Հատկություններ

Քրոմատիկ բազմանդամի հատկություններ 

 Եթե  -ն  դատարկ գրաֆ է, ապա․

 

 Եթե ​​   գրաֆը   և  չհատվող ենթագրաֆների միավորում է, ապա

 

 Եթե  -ում կա հանգույց, ապա

Քրոմատիկ թվի սահմանափակումները 

 Բոլոր գագաթներին տարբեր գույներ վերագրելը միշտ տալիս է ճիշտ ներկում, այնպես որ

 

 Միակ տեսակի գրաֆները, որոնք կարող են ներկվել մեկ գույնով, դրանք  զրոյական գրաֆներն են։
  ամբողջ գրաֆը, որն ունի   գագաթներ, պահանջում   գույն։
 Օպտիմալ ներկման դեպքում պետք է լինի գրաֆի  կողերից առնվազն մեկ կող յուրաքանչյուր երկու գույների դասերի միջև, այնպես որ
 

 Եթե   հանդիսանում է  և  չհատվող ենթագրաֆների միավորում, ապա
 

 Եթե  -ն պարունակում է k չափի կլիկներ, ապա անհրաժեշտ է նվազագույնը  k  թվով գույն այդ կլիկի ներկման համար, այլ կերպ ասած, քրոմատիկ թիվը ավելի մեծ է  կամ հավասար  կլիկի թվին։

 
 Միջանկյալ գրաֆների համար այս սահմանափակում  ճիշտ  է։

 Չորս գույների թեորեմի համաձայն՝ ցանկացած հարթ գրաֆ կարելի է  ներկել չորս գույներով։
 2-ներկվող գրաֆները երկակի գրաֆներ են, ներառյալ ծառերը։

 Գրաֆ -ն համարվում է երկակի միայն և միայն այդ դեպքում,  եթե այն չի պարունակում կենտ երկարությամբ ցիկլեր։

 Ագահ ներկումը ցույց է տալիս, որ ցանկացած գրաֆ կարելի է  ներկել, երբ օգտագործվում է մեկ գույն ավելին, քան դրա առավելագույն գագաթի աստիճանը։
 

 Ամբողջ գրաֆները ունեն   և , գրաֆ-ցիկլերը՝   և , ուստի նրանց համար այս սահմանափակումն ամենալավն է, մնացած բոլոր դեպքերում սահմանափակումները կարող են բարելավվել։ Բրուքսի թեորեմը պնդում է, որ

  կապակցված, պարզ գրաֆի համար, եթե այն ոչ ամբողջական գրաֆ է և ոչ էլ գրաֆ-ցիկլ։

Մեծ քրոմատիկ թվով գրաֆներ 

 Գրաֆները  ունեն մեծ քրոմատիկ թիվ, բայց հակառակ պնդումը միշտ չէ։  Գրյոչի  գրաֆը 4 գունավոր գրաֆի օրինակ է`  առանց եռանկյունիների և այս օրինակը կարելի է ընդհանրացնել Միխելսկու գծապատկերում։

 Թեորեմ (Ալեքսանդր Զիկով 1949, Յան Միխելսկի, 1955). Կան գրաֆներ, առանց եռանկյունների, կամայականորեն մեծ քրոմատիկ թվերով։

 Բրուքսի թեորեմից, մեծ քրոմատիկ համարով գրաֆները պետք է ունենան ուղղահայաց  առավելագույն աստիճան։ Տեղական մեկ այլ պայման, որի պատճառով քրոմատիկ քանակը կարող է մեծ լինել, մեծ կտավների առկայությունն է։ Բայց գրաֆի գունավորումը կախված է ոչ միայն տեղական պայմաններից. Տեղական մեծ գերեզմանով գրաֆը տեղական տեսք ունի ծառի տեսքով, ուստի բոլոր ցիկլերը երկար են, բայց դրա քրոմատիկ թիվը հավասար չէ 2-ի։

 Էրդշայի թեորեմ. Գոյություն ունեն գրաֆներ ՝ կամայականորեն մեծ գերեզմանով և քրոմատիկ համարով։

Քրոմատիկ ինդեքսի սահմանափակումները 

 Եզրերի գունավորում  —դա այն է, որ գունավորում տոպեր իր գծային գրաֆի  ։Այսինքն

 

 Ավելին,

 Կոենիգի թեորեմ: , եթե  — երկդիմի։

 Ընդհանուր դեպքում, կապը շատ ավելի ուժեղ է, քան Բրուքսի թեորեմը `ուղղահայաց գունավորումը տալիս է.

 Վիզինգի թեորեմ. վերին առավելագույն աստիճանի գրաֆը   ունի կողային քրոմատիկ թիվ   կամ .

Այլ հատկություններ 

 Գրաֆը k- քրոմատիկ է,  այն դեպքում, եթե այն ունի ացիկլային ուղղվածություն, որի համար ամենաերկար ուղու երկարությունը k է։ Դա ապացուցվեց Gallai - Hasse - Roy - Vitawer-ի թեորեմում։
 Հարթ գրաֆների համար, գագաթների գունավորում համարժեք է 0-ի։
 Անվերջ գրաֆների մասին  շատ ավելի քիչ  է հայտնի։ Ստորև բերված են անսահման գրաֆների գունազարդման երկու արդյունք։

 Եթե      անվերջ գրաֆի  բոլոր վերջնական ենթատեսակները  k- քրոմատիկ են, ապա և  -ն  նույնպես   k-քրոմատիկ է (ապացուցված է ընտրության աքսիոմի ենթադրությամբ)։ Սա Դե Բրյուենի - Էրդեշի թեորեմի սահմանումն է ։
 Եթե ​​գրաֆը ընդունում է ամբողջական n- գունավորում որևէ    համար, ապա դա ընդունում է անվերջ լիարժեք գունավորում։

Բաց հարցեր 
Օդանավի քրոմատիկ համարը, որում երկու կետերը հարակից են, եթե դրանց միջև կա միավոր հեռավորություն, անհայտ է  կարող է լինել 5, 6, կամ 7։ Գրաֆների քրոմատիկ թվաքանակի վերաբերյալ այլ բաց հարցերը ներառում են Hadwiger ենթադրությունը, որում ասվում է, որ k- ի քրոմատիկ համարով ցանկացած գրաֆի ունի k կետերի ամբողջական գրաֆը, ինչպես նշվումէ  Էրդշան-Ֆաբեր-Լովասի ենթադրությունում, որը սահմանափակում է ամբողջական գրաֆների քրոմատիկական քանակը, որոնք ունեն յուրաքանչյուր ընդհանուր զույգ գրաֆի համար ճշգրիտ մեկ ընդհանուր եզրագիծ և Ալբերտսոնի ենթադրությունը, որ k-քրոմատիկ գրաֆների շարքում լրիվ լրացված են այն խաչմերուկների ամենաքիչ քանակը։

Երբ Բիրկովն ու Լուիսը ներկայացրեցին քրոմատիկ բազմությունը՝ չորս գույնի թեորեմը լուծելու փորձի մեջ, նրանք պնդում էին, որ         գծային գրաֆների համարբազմապատկել այս միջակայքում չունի  ։ Չնայած հայտնի է, որ նման քրոմատիկ բազմամոնիան տարածաշրջանում զրո չունի , и что , նրանց հայտարարությունը մնում է չհաստատված։ Հարցը մնում է նաև բաց, թե ինչպես կարելի է տարբերակել գրաֆները նույն քրոմատիկ բազմամոլիկով և ինչպես որոշել, որ բազմամոլը քրոմատիկ է։

Գունազարդման ալգորիթմներ

Բազմահավաք ալգորիթմներ 
Երկկողմ գրաֆի համար գունազարդման առաջադրանքը հաշվարկվում է գծային ժամանակով ՝ օգտագործելով առաջին լայնության որոնումը։ Կատարյալ գրաֆների դեպքում քրոմատիկ համարը և դրա համապատասխան գունազարդումը կարելի է գտնել բազմամյա ժամանակով ՝ օգտագործելով կիսատագրված ծրագրավորում։ Քրոմատիկ համարը գտնելու ճշգրիտ բանաձևերը հայտնի են գրաֆների շատ դասերի համար (անտառներ, ցիկլեր, անիվներ, ակորդային գրաֆներ) և կարող են հաշվարկվել նաև բազմամյա ժամանակով։

Ճշգրիտ ալգորիթմներ 
K- ներկման դեպքի սպառիչ որոնման ալգորիթմը հաշվի է առնում բոլոր    համադրությունը դասավորվածության գույների վանդակում հետ n գագաթներով և ստուգում է նրանց ճշգրտությունը։ Քրոմատիկ համարը և քրոմատիկ պոլիոմը հաշվարկելու համար այս ալգորիթմը հաշվի է առնում յուրաքանչյուր k–ն  1-ից մինչև n: Գործնականում նման ալգորիթմը կարող է կիրառվել միայն փոքր գրաֆների համար։

Օգտագործելով դինամիկ ծրագրավորում և գնահատելով ամենամեծ անկախ հավաքածուի չափը, գրաֆում k- ներկման հնարավորությունը կարող է ժամանակին լուծվել ։ Հայտնի են ավելի արագ ալգորիթմներ 3-և 4-գունազարդումներ, որոնք աշխատում են     և    ընթացքում։

Ձգում 
Գագաթների ձգում — սա գործողություն է, որը գրաֆից  –ից   կազմում է գրաֆ   , նույնացնելով գագաթները  и , դրանք միացնող եզրերը հեռացնելով, և փոխարինելով    ուղղահայացով, ուղղվում են կողորը գագաթով  и ։ Այս գործողությունը կարևոր դեր է խաղում գրաֆի գունավորման վերլուծության մեջ։

Քրոմատիկ թիվը բավարարում է ռեկուրենտային հարաբերակցությանը։

,

որտեղ  –ն և  –ն  ոչ հարակից գագաթներ են ,  գրաֆ `ավելացված    կողերով Պ։ Որոշ ալգորիթմներ հիմնված են այդ համամասնության վրա ՝ արդյունքում արտադրելով ծառ, երբեմն կոչվում է նաև Զիկովի ծառ։ Կատարման ժամանակը կախված  և   է գագաթների  ընտրության մեթոդից ։

Քրոմատիկ բազմամոնիան բավարարում է կրկնվող հարաբերությունը.

,

որտեղ –ն  և –ն  հարակից գագաթներ են,    կողերի հեռացման գրաֆ ։   ներկայացնում է գրաֆի հնարավոր ճիշտ գունազարդումների թիվը , երբ  –ն և   – ն կարող են ունենալ տարբեր գույներ։ Եթե  –ն  и  –ն  ունեն տարբեր գույներ, ապա մենք կարող ենք դիտարկել գրաֆը, որտեղ  –ն  և  –ն  հարակից են։  Եթե  –ն և –ն ունեն նույն գույները, մենք կարող ենք դիտարկել գրաֆ, որտեղ –ն  և –ն  հարակից են։

Վերոհիշյալ տրված արտահայտությունները հանգեցնում են հետադարձման ընթացակարգին, որը կոչվում է հեռացման   ալգորիթմ, որը հիմք է հանդիսացել գրաֆիկական գունազարդման շատ ալգորիթմների համար։ Աշխատանքային ժամանակը բավարարում է նույն ռեկուրենտային հարաբերակցության, ինչպես նաև Ֆիբոնաչիի թվի, այնպես որ վատագույն դեպքում ալգորիթմը կաշխատի     ընթացքում  n  և  m գագաթների համար։  Գործնականում մասնաճյուղային և պարտադիր եղանակը և իզոմորֆային գրաֆները անտեսելը խուսափում են որոշակի հետադարձ զանգերից։  Գործառնական ժամանակը կախված է զույգ ուղղահայաց ընտրելու մեթոդից։

Ագահ գունավորում 
Ալգորիթմի աշխատանքի ընթացքում կա երկու արդյունք՝ գագաթների տարբեր կարգերի ընտրության ժամանակ։ Ալգորիթմը կազմակերպում է գագաթները ,…, և հաջորդականորեն վերագրում է ուղղահայաց –ին ամենափոքր հասանելի գույնը, հարև անների ներկման համար չօգտագործվող   շարքում  ,…,, կամ ավելացնում է նորը։ Արդյունքում գունազարդման որակը կախված է ընտրված կարգից։ Միշտ կա այդպիսի պատվեր, որը ալգորիթմը տանում է դեպի գույների օպտիմալ  քանակ։ Մյուս կողմից, ագահ ալգորիթմը կարող է լինել որքան վատ, օրինակ, թագը n գագաթներով կարող է նկարել 2 գույներով, բայց կա գագաթնակետների կարգը, որը հանգեցնում է ագահ գունավորում  գույներով։

Ակորդային գրաֆի համար և նրա հատուկ դեպքերի համար (օրինակ՝ ընդմիջման գրաֆ), ագահ գունազարդման ալգորիթմը կարող է օգտագործվել բազմամուսնական ժամանակում օպտիմալ գունավորում գտնելու համար՝ ընտրելով ուղղահայացների կարգը հակադարձ բացառության կատարյալ կարգին։ Այս ալգորիթմը կարող է կիրառվել գրաֆների ավելի լայն դասի (կատարյալ կարգավորված գրաֆների) վրա, այնուամենայնիվ, նման գրաֆների համար նման պատվեր գտնելը NP- բարդ խնդիր է։

Եթե ​​ուղղահայացները պատվիրված են ըստ իրենց աստիճանների, ագահ գունազարդման ալգորիթմը օգտագործում է ոչ ավելին, քան  գույներ, որ առավելագույնը 1-ով ավելի մեծ է, քան  (այստեղ  — վերին աստիճան ). Այս ​​ալգորիթմը երբեմն կոչվում է ՈՒելշա–Պաուելիի ալգորիթմ։ Մեկ այլ ալգորիթմի կարգը դինամիկ է սահմանում՝ ընտրելով մեկի հաջորդ ուղղահայացը, որն ունի տարբեր գույների հարակից ուղղահայացների ամենամեծ քանակը։ Գրաֆի գունազարդման շատ այլ ալգորիթմներ հիմնված են ագահ գունազարդման վրա և օգտագործել ստատիկ կամ դինամիկ ռազմավարություններ՝ ուղղահայացների կարգը ընտրելու համար։

Զուգահեռ և բաշխված ալգորիթմներ 
Բաշխված ալգորիթմների ոլորտում նմանատիպ խնդիր է առաջացել։ Ենթադրենք, որ գրաֆի ուղղությունները համակարգիչներ են, որոնք կարող են միմյանց հետ շփվել, եթե դրանք միացված են մի կողմով։ Խնդիրն է յուրաքանչյուր համակարգչի համար ընտրել իր համար «գույն», որպեսզի հարևան համակարգիչները ընտրեն տարբեր գույներ։ Այս խնդիրը սերտորեն կապված է սիմետրիայի կոտրման խնդրի հետ։ Առավել զարգացած հավանականական ալգորիթմները ավելի արագ են աշխատում, քան դետերմինիստական ​​ալգորիթմները ուղղանկյունների բավարար չափով մեծ առավելագույն աստիճանի գրաֆների համար ։ Հնարավոր արագ ալգորիթմներն օգտագործում են բազմակի փորձի տեխնիկան։

Սիմետրիկ գրաֆներում դետերմինիստական ​​բաշխված ալգորիթմները չեն կարողանում գտնել օպտիմալ եզրային գունավորումը։ Համաչափությունից խուսափելու համար անհրաժեշտ է ավելի շատ տեղեկատվություն։ Ստանդարտ ենթադրություն է արվում, որ ի սկզբանե յուրաքանչյուր եզրագիծ ունի յուրահատուկ նույնականացում, օրինակ ՝  այս    շարքից ։ Այլ կերպ ասած, ենթադրվում է, որ մեզ տրվում է n- երանգավորում։ Մարտահրավերն այն է, որ նվազեցնել գույների քանակը n -ից, օրինակ ՝ ։ Որքան շատ գույներ են օգտագործվում (օրինակ,   միասին  ), այնքան քիչ հաղորդագրություններ է անհրաժեշտ փոխանակել։

Բաշխված ագահ ալգորիթմի պարզ տարբերակ  -գունավորում պահանջում    գուցե հարկ լինի ցանցի մի ծայրից մյուսը անցնել։

Ամենապարզ հետաքրքիր դեպքը n- ցիկլն է։ Ռիչարդ Քոուլը և Ուզի Վիշկինը ցույց տվեցին, որ գոյություն ունի բաշխված ալգորիթմ, որը նվազեցնում է գույների քանակը n-ից մինչև  , օգտագործելով միայն մեկ անգամ հարևանների միջև հաղորդագրություններ։ Կրկնելով նույն ընթացակարգը, մենք կարող ենք ձեռք բերել n-ցիկլի 3-երանգավորում մինչև  կապի փուլեր (պայմանով, որ տրվեն եզակի հանգույցների նույնականացուցիչներ)։

Լոգարիթմական ֆունկցիա  ,Կրկնվող լոգարիթմը չափազանց դանդաղ աճող գործառույթ է ՝ «գրեթե կայուն»:Հետևաբար, Քոուլի և Վիշկինի արդյունքները բարձրացնում են այն հարցը, արդյոք կա n-ցիկլի բաշխված 3-գունավոր ալգորիթմ, որն ընթանում է անընդհատ ժամանակով։ Nathan Lineal- ը ցույց տվեց, որ դա անհնար է. Ցանկացած որոշիչ բաշխված ալգորիթմ     պահանջում է կապի փուլերը `n- ցիկլում N- գունավորումը 3-գունավորումը նվազեցնելու համար։

Քոուլի և Վիշկինի տեխնիկան կարող է կիրառվել նաև ուղղաձիգ սահմանափակ աստիճանի կամայական գրաֆի վրա, որի դեպքում գործարկման ժամանակը  է։  Այս մեթոդը ընդհանրացվել է միավորի օղակների գրաֆում Շնայդերի  և այլոց կողմից։

Կողերի գունազարդման խնդիրը նույնպես ուսումնասիրվել է բաշխված մոդելի մեջ։ Պենսոնցին և Ռիզզին հասան  -գունազարդում մինչև   մինչև այս մոդել։ Ստորին սահմանը բաշխված գունավոր գագաթների համար, որը ձեռք է բերվել գծի կողմից, նույնպես կիրառելի է բաշխված կողոսկրերի գունազարդման խնդրի համար։

Ապակենտրոնացված ալգորիթմներ 
Ապակենտրոնացված ալգորիթմները դրանք են, որոնցում ներքին հաղորդագրությունները թույլ չեն տալիս (ի տարբերություն բաշխված ալգորիթմների, որտեղ գործընթացները փոխանակում են տվյալները միմյանց հետ)։ Կան արդյունավետ ապակենտրոնացված ալգորիթմներ, որոնք հաջողությամբ հաղթահարում են գրաֆների գունավորման խնդիրը։ Այս ալգորիթմները գործում են այն ենթադրության համաձայն, որ մի եզրագիծ ունակ է «զգալ», որ իր հարևան ուղղահայաց նկարները ներկված են նույն գույնի պես։ Այլ կերպ ասած, հնարավոր է որոշել տեղական հակամարտություն։ Այս պայմանը հաճախ բավարարվում է իրական ծրագրերում. Օրինակ, անլար ալիքով տվյալներ փոխանցելիս, փոխանցող կայանը, որպես կանոն, հնարավորություն ունի հայտնաբերելու, որ մեկ այլ կայան փորձում է միաժամանակ փոխանցել նույն ալիքին։ Նման տեղեկատվություն ստանալու հնարավորությունը բավարար է, որպեսզի ալգորիթմները, որոնք հիմնված են սովորելու ավտոմատների վրա, մեկի հավանականությամբ, ճիշտ լուծում են գրաֆի գունավորման խնդիրը։

Հաշվողական բարդություն 
Գրաֆը ներկելը հաշվարկայինորեն դժվար է։ Պարզելու համար, արդյոք գրաֆը ընդունում է, որ տվյալ k- ի գունավորումը NP- ի ամբողջական խնդիր է, բացառությամբ k = 1 և k = 2. դեպքերի։ Մասնավորապես, քրոմատիկ համարը հաշվարկելու խնդիրն NP- բարդ է։ 3-երանգավորման խնդիրը NP- ամբողջական է նույնիսկ 4-րդ աստիճանի հարթ գրաֆի դեպքում։

Նաև NP դժվար խնդիր է 4 գույներով գունավոր գրաֆի ներկումը 4 գույներով և k- գունավոր գրաֆը  բավական k  մեծ արժեքների։

Քրոմատիկ բազմամյակի # P- դժվարության գործակիցների հաշվարկ։ Ապացուցված է, որ չկա որևէ FPRAS ալգորիթմ ՝ ցանկացած ռացիոնալ համարի համար քրոմատիկ բազմագույնը հաշվարկելու համար  k ≥ 1,5, բացի k = 2,եթե միայն չկատարվի, երբ NP = RP։

Դիմում

Պլանավորում 
Գունավորում Տոպեր  գունազարդման մոդելները պլանավորում են բազմաթիվ խնդիրներ։ Իր ամենապարզ ձևակերպմամբ ՝ աշխատատեղերի որոշակի շարք պետք է բաշխվեն ժամանակի ընթացքում, յուրաքանչյուր այդպիսի աշխատանք տանում է մեկ հատված։ Դրանք կարող են իրականացվել ցանկացած կարգով, բայց երկու աշխատանքները կարող են բախվել այն իմաստով, որ դրանք չեն կարող կատարվել միևնույն ժամանակ, քանի որ, օրինակ, նրանք օգտագործում են ընդհանուր ռեսուրսներ։ Համապատասխան գրաֆը պարունակում է եզրագիծ յուրաքանչյուր աշխատատեղի համար և յուրաքանչյուր հակամարտող զույգի համար եզր։ Կառուցված գրաֆի քրոմատիկական թիվը կատարման համար նվազագույն ժամանակն է առանց կոնֆլիկտի բոլոր աշխատանքների։

Պլանավորման խնդրի մանրամասները որոշում են գրաֆի կառուցվածքը։ Օրինակ, երբ կա օդանավերի բաշխում ըստ թռիչքների, արդյունքում առաջացող կոնֆլիկտային գրաֆը ինտերվալային գրաֆ է, որպեսզի ներկման խնդիրը հնարավոր լինի արդյունավետ լուծել։ Ռադիոհաճախականությունները բաշխելիս ձեռք է բերվում կոնֆլիկտների միավորի շրջանակների գրաֆ, և նման խնդրի համար կա 3-մոտեցման ալգորիթմ

Ռեգիստրների բաշխում 

Կոմպիլյատորը համակարգչային ծրագիր է, որը թարգմանում է մեկ համակարգչային լեզու մյուսը։ Արդյունավետ կոդի կատարման ժամանակը բարելավելու համար կոմպիլյատորի օպտիմալացման տեխնիկաներից մեկը գրանցումների բաշխումն է, որտեղ կոմպիլացվող ծրագրի առավել հաճախ օգտագործվող փոփոխականները պահվում են պրոցեսորի արագ գործող ռեգիստրներում։ Իդեալական դեպքում փոփոխականները պահվում են գրանցամատյաններում, այնպես, որ դրանք բոլորը գտնվում են գրանցամատյաններում դրանց օգտագործման ժամանակ։

Ստանդարտ մոտեցումը այս խնդրին է նկատի ունենալ, որ խնդիրը գունավորում գրաֆների. Կոմպիլյատորը կառուցում է ինտերֆերենցիոն գրաֆը, որտեղ գագաթները համապատասխանում են փոփոխականներին, իսկ եզրը կապում է դրանցից երկուսը, եթե դրանք անհրաժեշտ են ժամանակի միևնույն կետում։ Եթե այս գրաֆը k-քրոմատիկ է, ապա փոփոխականները կարող են պահվել k ռեգիստրներում։

Թվային ջրանիշներ 

Թվային ջրային նշանների տեխնոլոգիա (անգլ. ՝ ՝ digital watermarking) թույլ է տալիս տվյալների հետ միասին (լինի դա մեդիաֆայլեր, գործարկվող ֆայլեր և այլն) փոխանցել ինչ-որ թաքնված հաղորդագրություն ("ջրի մակարդակի նշագիծ", Watermark) ։ Նման թաքնված հաղորդագրությունը կարող է կիրառվել հեղինակային իրավունքի պաշտպանության բացահայտել տվյալների սեփականատիրոջը.

Սա կարևոր է, օրինակ, հաստատել աղբյուրը դրանց տարածման անօրինական ճանապարհով. Կամ հաստատել իրավունքները տվյալների, օրինակ, ծրագրային համակարգերի վրա բյուրեղյա (system-on-chi

Հաղորդագրությունը կարող է կոդավորված, այդ թվում՝  ձևով բաշխման ռեգիստրների.  Առաջարկվեց այս տեխնիկայից մեկը  Qu и Potkonjak (հետևաբար, այն երբեմն կոչվում է QP ալգորիթմ).

Այն բաղկացած է հետևյալից.թող   — (անհամատեղելիության գրաֆ)  պրոցեսորի գրանցման հատկացում  ,  որի մասին խոսվել է վերը։ Դրա գունավորումը օգտագործվում է ծրագրում - ավելին, այն օգտագործվում է այնպես, որ թույլատրելի է գրաֆի պարունակությունը փոխել իր քրոմատիկ համարի մի փոքր աճով։ Ստացվում է, որ հնարավոր է հաղորդագրություն կոդավորել ծրագրային արտադրանքի մեջ ՝ օգտագործելով գրաֆի ներկ  , այսինքն, բաշխման ռեգիստրների։

Դուք կարող եք ստանալ այս հաղորդագրությունը համեմատելով ռեգիստրների բաշխումը սկզբնական գունազարդման հետ; Կան նաև եղանակներ համոզվելու համար, թե արդյոք որևէ հաղորդագրություն կոդավորված է ծրագրում, առանց նախնական օգտագործման։

Հետագայում տարբեր հեղինակներ զարգացրել և հստակեցրել են գաղափարները Qu և Potkonjak.

Այլ ծրագրեր 

Գրաֆների գունավորման խնդիրը դրվել է կիրառման բազմաթիվ այլ ոլորտներում, ներառյալ նմուշային համադրումը։

Sudoku հանելուկ լուծումը կարող է դիտվել որպես ավարտելով գունավորում 9 գույներով սահմանված գրաֆի 81 գագաթներով։

Ծանոթագրություններ

Գրականություն 

 
 
 
 
 
 
  (= Indag. Math. 13)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 .
 
 .
 
 
 
 
 
 
 
 
 
 

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