Ro'yxatni bo'yash - List coloring

Yilda grafik nazariyasi, filiali matematika, ro'yxatni bo'yash ning bir turi grafik rang berish bu erda har bir tepalik ruxsat berilgan ranglar ro'yxati bilan cheklanishi mumkin. Birinchi marta 1970-yillarda mustaqil maqolalarida o'rganilgan Vizing va tomonidan Erdős, Rubin va Teylor.[1]

Ta'rif

Grafik berilgan G va to'plam berilgan L(v) har bir tepalik uchun ranglar v (a deb nomlangan ro'yxat), a ro'yxatni bo'yash a tanlov funktsiyasi har bir tepalikni xaritada aks ettiradi v ro'yxatdagi rangga L(v). Grafikni bo'yashda bo'lgani kabi, ro'yxat ranglanishi odatda qabul qilinadi to'g'ri, ikkitasi yo'q degani qo'shni tepaliklar bir xil rangni olish. Grafik k- tanlash mumkin (yoki k- ro'yxat rangli) ro'yxatini qanday tayinlashidan qat'i nazar, agar u tegishli ro'yxat rangiga ega bo'lsa k har bir tepalikka ranglar. The tanlash imkoniyati (yoki ro'yxat rangliligi yoki ro'yxati xromatik raqam) (G) grafik G eng kam son k shu kabi G bu k- tanlash mumkin.

Umuman olganda, funktsiya uchun f musbat tamsayı berish f(v) har bir tepaga v, grafik G bu f- tanlash mumkin (yoki f- ro'yxat rangli) agar u qanday qilib ro'yxatni tayinlasa ham, ranglarning ro'yxati bo'lsa f(v) har bir tepalikka ranglar v. Xususan, agar barcha tepaliklar uchun v, f-choosability mos keladi k-choosability.

Misollar

To'liqligini ko'rib chiqing ikki tomonlama grafik G = K2,4oltita tepalikka ega A, B, V, X, Y, Z shu kabi A va B har birining barchasi bilan bog'liq V, X, Yva Zva boshqa tepaliklar bog'lanmagan. Ikki tomonlama grafik sifatida, G odatdagi 2-xromatik raqamga ega: biri rangga ega bo'lishi mumkin A va B bitta rangda va V, X, Y, Z boshqasida va ikkita qo'shni tepalik bir xil rangga ega bo'lmaydi. Boshqa tarafdan, G 2-dan katta ro'yxat-xromatik raqamga ega, chunki quyidagi qurilish ko'rsatmoqda: ga belgilang A va B {qizil, ko'k} va {yashil, qora} ro'yxatlar. Boshqa to'rtta vertikalga {qizil, yashil}, {qizil, qora}, {ko'k, yashil} va {ko'k, qora} ro'yxatlarni belgilang. Qaysi tanlovdan qat'iy nazar ro'yxatdagi rangni tanlash kerak A va ro'yxatidan rang B, boshqa vertex ham bo'ladi, chunki uning ikkala tanlovi ham qo'shnilarini ranglash uchun ishlatilgan. Shunday qilib, G 2 marta tanlanmaydi.

Boshqa tomondan, buni ko'rish oson G 3 ta tanlov: tepaliklar uchun ixtiyoriy ranglarni tanlash A va B qolgan har bir tepalik uchun kamida bitta mavjud rangni qoldiradi va bu ranglar o'zboshimchalik bilan tanlanishi mumkin.

Ro'yxatni bo'yash misoli to'liq ikki tomonlama grafik K3,27 uchiga uchta rang bilan. Uchta markaziy tepalik uchun qaysi ranglar tanlanishidan qat'i nazar, tashqi 27 ta tepaliklardan biri rangsiz bo'lib, ro'yxatning xromatik soni K3,27 kamida to'rtta.

Umuman olganda, ruxsat bering q musbat tamsayı bo'lsin va bo'lsin G bo'lishi to'liq ikki tomonlama grafik Kq,qq. Mavjud ranglarni q2 har xil ikki xonali raqamlar radix qIkki qismning bir tomonida q tepaliklarga ranglar to'plami berilgan {men0, men1, men2, ...} unda birinchi raqamlar bir-biriga teng, har biri uchun q birinchi raqamning mumkin bo'lgan tanlovlarimenIkki qismning boshqa tomonida qq tepaliklarga ranglar to'plami berilgan {0a, 1b, 2v, ...} har birida birinchi raqamlar bir-biridan farq qiladi qq ning mumkin bo'lgan tanlovlari q- juftlik (a, b, v, ...).Rasmda xuddi shu qurilishning kattaroq namunasi ko'rsatilgan q = 3.

Keyin, G uchun ranglarning ro'yxati yo'q L: Ikki qismning kichik tomonidagi tepaliklar uchun qanday ranglar to'plami tanlangan bo'lishidan qat'i nazar, bu tanlov ikkala qismning boshqa tomonidagi vertikallardan biri uchun barcha ranglarga zid keladi. Masalan, {00,01} rang to'plamli tepalik 01 rangga, {10,11} ranglar to'plamli vertex 10 rangga ega bo'lsa, u holda {01,10} ranglar to'plamli vertexni ranglash mumkin emas. ro'yxati xromatik soni G hech bo'lmaganda q + 1.[2]

Xuddi shunday, agar , keyin to'liq ikki tomonlama grafik Kn, n emas k- tanlash mumkin. Masalan, bu 2k - Jami 1 ta rang mavjud va bu ikkala qismning bir tomonida har bir tepalik unga har xil bo'lishi mumkin k- bu ranglarning bir-biriga nisbatan vertexidan. Keyin, ikkala qismning har bir tomoni kamida foydalanishi kerak k ranglar, chunki har bir to'plam k - bitta vertex ro'yxatidan 1 ta rang ajralib chiqadi. Hech bo'lmaganda k ranglar bir tomonda va hech bo'lmaganda ishlatiladi k ikkinchisida ishlatiladi, ikkala tomonda ham bitta rang bo'lishi kerak, lekin bu ikkita qo'shni tepaliklarning bir xil rangga ega ekanligini anglatadi. Xususan, yordam dasturi K3,3 kamida uchta ro'yxat-xromatik raqam va grafik mavjud K10,10 kamida to'rtta ro'yxat-xromatik raqamga ega.[3]

Xususiyatlari

Grafik uchun G, ruxsat bering χ (G) ni belgilang xromatik raqam va Δ (G) maksimal daraja ning G. Ro'yxat rang raqami ch (G) quyidagi xususiyatlarni qondiradi.

  1. ch (G≥ χ (G). A k- har bir tepaga bir xil ro'yxat berilganida, xususan, rang-barang grafikada ro'yxat ranglanishi kerak k ranglar, bu odatdagiga to'g'ri keladi k- rang berish.
  2. ch (G) umuman xromatik son jihatidan chegaralanib bo'lmaydi, ya'ni funktsiya yo'q f shunday ch (G) ≤ f(χ (G)) har bir grafik uchun amal qiladi G. Xususan, to'liq ikki tomonlama grafik misollari ko'rsatilgandek, χ (G) = 2 lekin ch bilanG) o'zboshimchalik bilan katta.[2]
  3. ch (G≤ χ (Gln (n) qayerda n tepaliklar soni G.[4][5]
  4. ch (G≤ Δ (G) + 1.[3][6]
  5. ch (GIf 5 agar G a planar grafik.[7]
  6. ch (G≤ 3 agar G a ikki tomonlama planar grafik.[8]

Hisoblashni tanlash imkoniyati va (a, b) tanlash imkoniyati

Adabiyotda ikkita algoritmik muammo ko'rib chiqilgan:

  1. k-tanlash imkoniyati: berilgan grafik ekanligiga qaror qiling k- berilgan uchun tanlanadi kva
  2. (a, b)-tanlash imkoniyati: berilgan grafik ekanligiga qaror qiling f- berilgan funktsiya uchun tanlanadi .

Ma'lumki k-kipartitli grafikalarda tanlovlilik bu - har qanday kishi uchun to'liq k ≥ 3, xuddi shu narsa planar grafikalardagi 4-tanlanadigan, tekislikdagi 3-tanlanuvchanlik uchun ham amal qiladi uchburchaklarsiz grafikalar, va (2, 3) -da tanlash imkoniyati ikki tomonlama planar grafikalar.[9][10] P uchun5-free grafikalar, ya'ni grafikalar bundan mustasno 5-vertex yo'l grafigi, k- tanlov imkoniyati belgilangan parametrlarni boshqarish mumkin.[11]

Grafikning 2 tanlanadiganligini tekshirib ko'rish mumkin chiziqli vaqt nol darajagacha yoki bitta darajadagi tepaliklarni qayta-qayta o'chirish orqali 2 yadroli grafigi, bundan keyin bunday o'chirish mumkin emas. Dastlabki grafika, agar uning 2 yadrosi juft tsikl yoki a bo'lsa, faqat 2 marta tanlanadi teta grafigi umumiy uzunlikdagi ikkita yo'l va har qanday uzunlikka ega bo'lgan uchinchi yo'l bilan umumiy uchlari bo'lgan uchta yo'l tomonidan hosil qilingan.[3]

Ilovalar

Ro'yxatni bo'yash kanal / chastotani tayinlash bilan bog'liq amaliy muammolarda paydo bo'ladi.[12][13]

Shuningdek qarang

Adabiyotlar

  1. ^ Jensen, Tommi R.; Toft, Bjarne (1995), "1.9 ro'yxatni bo'yash", Grafikni bo'yash muammolari, Nyu-York: Wiley-Interscience, 18-21 betlar, ISBN  0-471-02865-7
  2. ^ a b Gravier, Silvain (1996), "Ro'yxatni bo'yash uchun Xajosga o'xshash teorema", Diskret matematika, 152 (1–3): 299–302, doi:10.1016 / 0012-365X (95) 00350-6, JANOB  1388650.
  3. ^ a b v Erdos, P.; Rubin, A. L.; Teylor, H. (1979), "Grafiklarda tanlanuvchanlik", Proc. G'arbiy sohilda kombinatoriya, grafik nazariyasi va hisoblash bo'yicha konferentsiya, Arcata (PDF), Congressus Numerantium, 26, 125-157 betlar, arxivlangan asl nusxasi (PDF) 2016-03-09, olingan 2008-11-10
  4. ^ Eaton, Nensi (2003), "Ro'yxatni bo'yash to'g'risida ikkita qisqa dalil - 1-qism" (PDF), Gapir, dan arxivlangan asl nusxasi (PDF) 2017 yil 29 avgustda, olingan 29 may, 2010
  5. ^ Eaton, Nensi (2003), "Ro'yxatni bo'yash to'g'risida ikkita qisqa dalil - 2-qism" (PDF), Gapir, dan arxivlangan asl nusxasi (PDF) 2017 yil 30 avgustda, olingan 29 may, 2010
  6. ^ Vizing, V. G. (1976), "Vertex ranglari berilgan ranglar", Metody Diskret. Analiz. (rus tilida), 29: 3–10
  7. ^ Tomassen, Karsten (1994), "Har bir tekislik grafigi 5 ta tanlanadi", Kombinatoriya nazariyasi jurnali, B seriyasi, 62: 180–181, doi:10.1006 / jctb.1994.1062
  8. ^ Alon, Noga; Tarsi, Maykl (1992), "Graflarning ranglanishi va yo'nalishlari", Kombinatorika, 12: 125–134, doi:10.1007 / BF01204715
  9. ^ Gutner, Shai (1996), "Planar grafikani tanlashning murakkabligi", Diskret matematika, 159 (1): 119–130, arXiv:0802.2668, doi:10.1016 / 0012-365X (95) 00104-5.
  10. ^ Gutner, Shai; Tarsi, Maykl (2009), "Ba'zi natijalar (a:b) tanlash imkoniyati ", Diskret matematika, 309 (8): 2260–2270, doi:10.1016 / j.disc.2008.04.061
  11. ^ Heggernes, Pinar; Golovach, Petr (2009), "P-ni tanlash imkoniyati5- bepul grafikalar " (PDF), Kompyuter fanining matematik asoslari, Kompyuter fanlari bo'yicha ma'ruzalar, 5734, Springer-Verlag, 382-391 betlar
  12. ^ Vang, Vey; Liu, Xin (2005), "Ochiq spektrli simsiz tarmoqlar uchun kanallarni ro'yxatini bo'yash asosida taqsimlash", 2005 yil IEEE 62-chi transport texnologiyalari konferentsiyasi (VTC 2005-kuz), 1, 690-694 betlar, doi:10.1109 / VETECF.2005.1558001.
  13. ^ Garg, N .; Papatriantafilu, M.; Tsigas, P. (1996), "Tarqatilgan ro'yxatning ranglanishi: mobil bazaviy stantsiyalarga chastotalarni dinamik ravishda taqsimlash", Parallel va taqsimlangan ishlov berish bo'yicha IEEE sakkizinchi simpoziumi, 18-25 betlar, doi:10.1109 / SPDP.1996.570312, hdl:21.11116 / 0000-0001-1AE6-F.

Qo'shimcha o'qish