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

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

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

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

Հաջորդական կողերի ներկման հասկացությունը ներկայացվել է Ասրատյանի և Քամալյանի կողմից «միջակայքային կողային ներկումներ» տերմինաբանությամբ 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. (russian), Прикладная математика. Вып. 5., Erevan: Erevan. Univ., pp. 25–34, 130–131 
  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