Գրաֆների ինտերվալային ներկումներ

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

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

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

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

Սահմանում 

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

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

Կիրառություններ 

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

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

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