Գրաֆների միջակայքային կողային ներկումներ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Պատմություն[խմբագրել | խմբագրել կոդը]

Հաջորդական կողերի ներկման հասկացությունը ներկայացվել է Ասրատյանի և Քամալյանի կողմից «միջակայքային կողային ներկումներ» տերմինաբանությամբ 1987 թվականին «Մուլտիգրաֆերի միջակայքային կողային ներկումներ»[1] հոդվածում։ Գրաֆների միջակայքային կողային գունավորումը ներմուծելուց հետո մաթեմատիկոսները ուսումնասիրում էին միջակայքային կողային ներկման գոյություն ունենալու խնդիրը տարբեր տեսակի գրաֆների համար, քանի որ ոչ բոլոր գրաֆների համար կարող է գոյություն ունենալ միջակայքային կողային ներկում։ Գրաֆների մի պարզ ընտանիք, որը թույլ է տալիս միջակայքային կողային ներկում, կենտ քանակի գագաթներ ունեցող լրիվ գրաֆն է, և հակադիր օրինակը զույգ քանակի գագաթներ ունեցող լրիվ գրաֆն է։ Ամենափոքր գրաֆը որը թույլ չի տալիս միջակայքային կողային ներկում։ Նույնիսկ կան 28 գագաթանի գրաֆներ որոնց աստիճանը առավելագույնը 21 է, և նրանք չունեն միջակայքային կողային ներկում Սևաստյանովի կողմից, չնայած որ չորսից տասներկու առավելագույն գագաթի աստիճան ունեցող գրաֆների ներկելու խնդիրը դեռ անհայտ է։

Ասրատյան & Քամալյան (1987) ապացուցել են որ եթե գրաֆը ունի միջակայքային կողային ներկում, ապա նրա կողային քրոմատիկ թիվը չի գերազանցում կողերի քանակից հանած մեկ թիվը, և նշվում է, որ եթե G-ն r-կանոնավո է, ապա G ունի միջակայքային ներկում այն և միայն այն դեպքում երբ G-ն ունի r-կողային-ներկում[1]։

Միջակայքային կողային ներկումը հետազոտվում է կանոնավոր գրաֆներում, երկկողմանի գրաֆներում, պլանար գրաֆներում և ուրիշ ընդլայնումների համար, որոնք նախաձեռնվել են միջակայքային կողային ներկումներից։

Սահմանում[խմբագրել | խմբագրել կոդը]

Թող G-ն լինի սովորական միջակայքային գրաֆ։ G գրաֆի կողային ներկումը 1, 2, . . ., t գույներով կոչվում է միջակայքային t-ներկում, եթե ցանկացած i ∈ {1, 2, . . ., t} գոյություն ունի առնվազն մեկ կող՝ G-ից ներկված i գույնով և ցանկացած գագաթի կից կողերի գույները իրարից տարբեր են՝ կազմելով ամբողջ թվերի միջակայք[2]։ Կարելի է սահմանել նաև հետևյալ կերպ. G գրաֆի կողային ներկումը 1. . . t գույներով կոչվում է միջակայքային t-ներկում, եթե բոլոր գույները օգտագործվում են, և ամեն գագաթի հարակից կողերի գույները իրարից տարբեր են՝ կազմելով ամբողջ թվերի միջակայք։ G գրաֆը "միջակայքային ներկելի է", եթե G-ն ունի ինչ-որ միջակայքային t-ներկում ինչ-որ դրական ամբողջ t թվի համար։ Թող N-ը լինի բոլոր միջակայքային ներկելի գրաֆների բազմությունը։ Եթե GN, t-ի ամենափոքր և ամենամեծ արժեքները, որոնց դեպքում G-ն ունի միջակայքային t-ներկում, նշանակվում է համապատասխանաբար w(G) և W(G)։ Միջակայքային կողային ներկումը կոչվում է արդար միջակայքային ներկում, եթե ցանկացած երկու գույների կլասները տարբերվում են առնվազն մեկով։

x գագաթին կից կողերի գույների բազմությունը կոչվում է x-ի սպեկտր։ Կասենք գագաթների R ենթաբազմությունն ունի i-հատկություն եթե գոյություն ունի G-ի կողերի t-ներկում այնպես որը R-ի վրա միջակայք է։

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

  1. 1,0 1,1 Asratyan, A. S.; Kamalyan, R. R. (1987), «Interval colorings of the edges of a multigraph», in Tonoyan, R. N. (ed.), Прикладная математика. Вып. 5. [Applied mathematics. No. 5] (Russian), Erevan: Erevan. Univ., էջեր 25–34, 130–131, MR 1003403{{citation}}: CS1 սպաս․ չճանաչված լեզու (link)
  2. Petrosyan, P. A. (2010), «Interval edge-colorings of complete graphs and n-dimensional cubes», Discrete Mathematics, 310 (10–11): 1580–1587, doi:10.1016/j.disc.2010.02.001, MR 2601268