Ақаулы бояу - Defective coloring

Жылы графтар теориясы, математикалық пән, бояу графтың шыңдарына, шеттеріне және беттеріне түстерді немесе белгілерді тағайындауды білдіреді. Ақаулы бояу - бұл шыңдарды дұрыс бояудың нұсқасы. Тиісті шыңды бояғанда, төбелер бір-біріне жақын төбелердің түсіне ие болмайтындай етіп боялған. Ақаулы бояуларда, керісінше, шыңдарда белгілі бір мөлшерде бірдей түсті көршілер болуға рұқсат етіледі. (Мұнда қараңыз Графтар теориясының сөздігі )

Тарих

Ақаулы бояуды Берр мен Джейкобсон, Харари мен Джонс және Коуэн, Коуэн және Вудолл бір мезгілде енгізді.^[1] Осы және соған байланысты бояуларды зерттеуді Мариетджи Фрик береді.^[2] Коуэн, Коуэн және Вудолл ^[1] беттерге салынған графиктерге бағытталған және бәріне толық сипаттама берген к және г. әрбір жазықтық (к, г.) -түсті Атап айтқанда, жоқ г. әрбір жазықтық графигі (1, г.) - немесе (2, г.) -түсті; (3, 1) -түсінбейтін жазықтық графиктер бар, бірақ әр жазықтық графика (3, 2) -түсінікті. (4, 0) түсімен бірге төрт түсті теорема, бұл жазықтық үшін ақаулы хроматикалық санды шешеді. Пох ^[3] және Goddard ^[4] кез-келген жазықтық графикада әр түсті класы сызықтық орман болатын арнайы (3,2) түске ие болатынын және оны Вудоллдың жалпы нәтижесінен алуға болатындығын көрсетті, жалпы беттер үшін әр тұқым үшін ${ displaystyle g geq 0}$, бар a ${ displaystyle k = k (g)}$ осылайша тұқымның бетіндегі әр график ${ displaystyle g}$ болып табылады (4, к) -түсті^[1] Бұл (3, к) арқылы Дэн Архдекон.^[5]Жалпы графиктер үшін Ласло Ловаш көптеген рет қайта ашылған 1960 жж ^[6][7][8] қамтамасыз етеді O (∆E)- максималды дәрежедегі ақаулы бояу графиктері үшін уақыт алгоритмі.

Анықтамалар мен терминология

Ақаулы бояу

A (к, г.) - графикті бояу G - оның төбелерінің бояуы к түстер әрбір шыңға арналған v ең көп дегенде г. түсі бірдей болатын көршілер v. Біз қарастырамыз к оң бүтін сан болуы керек (жағдайды қарастыру маңызды емес к = 0) және г. теріс емес бүтін сан болу керек. Демек, (к, 0) -түсіру шыңның дұрыс боялуына сәйкес келеді.^[9]

г.- ақаулы хроматикалық сан

Түстердің минималды саны к ол үшін қажет G бұл (к, г.) -түсті деп аталады г.- ақаулы хроматикалық сан, ${ displaystyle chi _ {d} (G)}$.^[10]

Граф класы үшін G, ақаулы хроматикалық нөмір туралы G минималды бүтін сан к сондықтан кейбір бүтін сан үшін г., әрбір график G бұл (к,г.) -түсті Мысалы, жазық графиктер класының ақаулы хроматикалық саны 4-ке тең, өйткені әрбір жазықтық графигі (4,0) -түсті және әрбір бүтін сан үшін г. жазықтық сызбасы жоқ (3,г.) -түсті

Шыңның орынсыздығы

Келіңіздер c графиктің шыңы-бояуы болуы керек G. Шыңның орынсыздығы v туралы G бояуға қатысты c - көршілерінің саны v бірдей түске ие v. Егер орынсыз болса v 0 болса, онда v дұрыс боялған дейді.^[1]

Шыңды бояудың орынсыздығы

Келіңіздер c графиктің шыңы-бояуы болуы керек G. Орынсыздығы c - бұл барлық шыңдардың сәйкессіздіктерінің максимумы G. Демек, тиісті шыңды бояудың орынсыздығы 0-ге тең.^[1]

Мысал

D = 0, 1, 2 болған кезде бес шыңдағы циклдің ақаулы бояуларының мысалы

Бес шыңдағы циклдің ақаулы бояуларының мысалы, ${ displaystyle C_ {5}}$, суретте көрсетілгендей. Бірінші ішкі пішін - шыңдарды дұрыс бояудың мысалы немесек, 0) -түсіру. Екінші субфигура (к, 1) -түсіну және үшінші кіші пішін ((к, 2) -түсіру. Ескертіп қой,

${ displaystyle chi _ {0} (C_ {5}) = chi (C_ {5}) = 3}$

${ displaystyle chi _ {1} (C_ {5}) = 3}$

${ displaystyle chi _ {2} (C_ {n}) = 1; forall n in mathbb {N}}$

Қасиеттері

• Байланысты графиктерді график ретінде қарастыру жеткілікті G бұл (к, г.) - егер олар әрқайсысы болса ғана түсті жалғанған компонент туралы G бұл (к, г.) -түсті^[1]
• Графикалық теориялық шарттарда шыңның тиісті бояуындағы әр түсті класс an тәуелсіз жиынтық, ақаулы бояғыштағы әр түсті класс ең көп дегенде дәреже подографиясын құрайды г..^[11]
• Егер график (к, г.) -түсті, онда ол (k ′, d ′) - әр жұп үшін түсті (k ′, d ′) солай k ′ ≥ к және d ′≥ г..^[1]

Кейбір нәтижелер

Әрқайсысы сыртқы жоспарлау сызбасы (2,2) -түсті

Дәлел: Келіңіздер ${ displaystyle G}$ қосылған сыртқы жоспарлы график болу. Келіңіздер ${ displaystyle v_ {0}}$ -ның ерікті шыңы болуы ${ displaystyle G}$. Келіңіздер ${ displaystyle V_ {i}}$ шыңдарының жиынтығы болыңыз ${ displaystyle G}$ қашықтықта орналасқан ${ displaystyle i}$ бастап ${ displaystyle v_ {0}}$. Келіңіздер ${ displaystyle G_ {i}}$ болуы ${ displaystyle langle V_ {i} rangle}$, подграфия индукцияланған ${ displaystyle V_ {i}}$.Мақсат ${ displaystyle G_ {i}}$ құрамында 3 немесе одан жоғары дәрежелі шыңдар бар, содан кейін оларда болады ${ displaystyle K_ {1,3}}$ подограф ретінде. Содан кейін біз барлық жиектерді қысқартамыз ${ displaystyle V_ {0} cup V_ {1} cup ... cup V_ {i-1}}$ жаңа график алу үшін ${ displaystyle G '}$. Айта кету керек ${ displaystyle langle V_ {0} cup V_ {1} cup ... cup V_ {i-1} rangle}$ туралы ${ displaystyle G '}$ әрбір шыңы сияқты байланысты ${ displaystyle V_ {i}}$ in шыңына іргелес ${ displaystyle V_ {i-1}}$. Демек, келісім-шарт жоғарыда аталған барлық шеттерін аламыз ${ displaystyle G '}$ подграф сияқты ${ displaystyle langle V_ {0} cup V_ {1} cup ... cup V_ {i-1} rangle}$ туралы ${ displaystyle G '}$ in-нің әрбір шыңына жақын орналасқан жалғыз шыңмен ауыстырылады ${ displaystyle V_ {i}}$. Осылайша ${ displaystyle G '}$ қамтиды ${ displaystyle K_ {2,3}}$ подограф ретінде. Бірақ сыртқы жазықтық графиктің әрбір подографиясы сыртқы жазықтық, ал сыртқы жоспарлау графигінің жиектерін жиыру арқылы алынған әрбір график сыртқы жазықтық болып табылады. Бұл мұны білдіреді ${ displaystyle K_ {2,3}}$ сыртқы жазықтық, қайшылық. Демек график жоқ ${ displaystyle G_ {i}}$ 3 немесе одан жоғары дәрежелі шыңдарды қамтиды, мұны білдіреді ${ displaystyle G}$ бұл (к, 2) -түсті. Шыңдары жоқ ${ displaystyle V_ {i}}$ кез келген шыңына іргелес ${ displaystyle V_ {i-1}}$ немесе ${ displaystyle V_ {i + 1}, i geqslant 1}$, демек, шыңдары ${ displaystyle V_ {i}}$ егер көк түске боялған болса ${ displaystyle i}$ тақ және қызыл болса, егер жұп болса. Демек, біз (2,2) -түсті шығардық ${ displaystyle G}$.^[1]

Қорытынды: Әр жазықтық графигі (4,2) -түсті.Бұл келесідей болады ${ displaystyle G}$ жазықтықта орналасқан ${ displaystyle G_ {i}}$ (жоғарыдағыдай) сыртқы жазықтық. Сондықтан әрқайсысы ${ displaystyle G_ {i}}$ (2,2) -түсті. Сондықтан, әрбір шыңы ${ displaystyle V_ {i}}$ егер көк немесе қызыл түске боялған болса ${ displaystyle i}$ біркелкі, егер жасыл немесе сары болса ${ displaystyle i}$ тақ болады, демек (4,2) -түсін шығарады ${ displaystyle G}$.

Толық кәмелетке толмағанды ​​қоспағанда, графиктер

Әрбір бүтін сан үшін ${ displaystyle t}$ бүтін сан бар ${ displaystyle N}$ әрбір график ${ displaystyle G}$ жоқ ${ displaystyle K_ {t}}$ кіші болып табылады ${ displaystyle (t-1, N)}$-түсті^[12]

Есептеудің күрделілігі

Ақаулы бояу есептеу қиын. Берілген график туралы шешім қабылдау NP аяқталды ${ displaystyle G}$ (3,1) -түсінікті, тіпті жағдайда да қабылдайды ${ displaystyle G}$ максималды шың-6 дәрежесі немесе максимум шың-7 дәрежесі бойынша жазықтық.^[13]

Қолданбалар

Ақаулы бояуды қолдануға мысал ретінде жоспарлау мәселесі келтіруге болады, мұнда шыңдар жұмысты бейнелейді (компьютерлік жүйеде пайдаланушыларды айтамыз), ал шеттер қақтығыстарды білдіреді (бір немесе бірнеше файлға қол жеткізуді қажет етеді). Ақаулыққа жол беру қақтығыстың қандай да бір шегіне жол беруді білдіреді: әр пайдаланушы жүйеде екі қарама-қайшы басқа пайдаланушылармен деректерді алу кезінде туындаған максималды бәсеңдеуді қолайлы, ал екеуден көп қолайсыз деп санайды.^[14]

Ескертулер

Әдебиеттер тізімі