Graficul de colorare
Puteți colora atât marginile graficului, cât și vârfurile. Mai întâi atingem problema vârfurilor de colorare. presupunem că graficul nu este orientat și nu este un multigraf.
Sarcina. Colorați vârfurile graficului astfel încât oricare dintre cele două vârfuri adiacente să fie vopsite în culori diferite, iar numărul de culori folosite trebuie să fie cel mai mic. Acest număr este numit numărul culorilor (culoarea) graficului, îl desemnează cu a = a (G) (dacă G este un grafic dat). Dacă numărul k i a. atunci graficul este numit k-colorabil.
Funcția Grundy este o funcție pe vârfurile unui grafic care hărți nodurile la un set, iar dacă vertexul xi este colorat cu numărul k. atunci funcția Grandi h (xi) = k.
Este clar că pentru un anumit grafic numărul cromatic este unic, dar pot exista multe funcții Grandi. Desigur, găsirea a cel puțin o funcție a Grandi înseamnă găsirea uneia dintre cele mai bune colorări "cele mai bune" (pot exista multe astfel de coloranți).
Rețineți că, dacă graficul este completă, adică oricare două noduri sunt adiacente, numărul cromatic al graficului este egal cu n unde n -... Numărul de noduri.
Pentru viitor avem nevoie de următoarea definiție.
Un set de noduri se numește un set independent maxim (MNS), în cazul în care oricare două noduri ale acestui set nu sunt contigue și nu pot fi incluse în acest set un alt vârf la această condiție este păstrată. Rețineți că prezența MNF în grafic este destul de simplu: să ia un nod arbitrar, apoi găsiți orice top, nu adiacente acesteia, și apoi găsi în partea de sus, care nu este adiacent la nodurile selectate, etc. Desigur, MHC în această coloană pot fi multe și ele sunt .. poate conține un număr diferit de vârfuri.
Acum vom descrie un algoritm pentru a găsi cel mai bun colorarea nodurilor. Să presupunem că avem un grafic G. găsi în ea orice MHC, care este notat cu S1. și toate nodurile care sunt in MHC, vopsite în culoarea № 1. Mai mult, eliminat din acest grafic toate nodurile care sunt in MHC (cu aripioare), și din nou pentru a găsi noi grafic MHC, notată S2. Aceste noi vârfuri evidențiate în culori № 2, apoi îndepărtați vertex din grafic, împreună cu nervuri corespunzătoare și din nou găsi MHC, care este evidențiată în culoare № 3, și așa mai departe. E. Se poate demonstra că ajunge la cea mai bună colorare pentru orice metodă a acestei proceduri, și găsiți o funcție Grundy și numărul cromatic al graficului dat.
Un exemplu. Graficul (Figura 9) are 3 sisteme maximale independente de vârfuri: și. Este clar că pentru orice procedură pentru găsirea numărului cromatic în acest grafic, obținem numărul 3.
Teorema. Dacă gradul maxim de vârfuri dintr-un grafic este r. atunci numărul cromatic al acestui grafic nu depășește r + 1. În acest caz, numărul cromatic al graficului este egal cu r + 1 numai în două cazuri: în primul rând, dacă graficul este complet și, în al doilea rând, dacă r = 2 și graficul conține conturul lungimea nui (astfel grafic este prezentat în Figura 10, gradul maxim de nodurile sale -. 2 și numărul cromatic - 3). În toate celelalte cazuri, numărul cromatic al graficului nu depășește gradul maxim de vârfuri.
Notă. Estimarea numărului cromatic dat de această teoremă este destul de brută. Acest lucru este evident mai ales în cazul unui copac (secțiunea 14), pentru care gradul de vârfuri poate fi arbitrar mare, iar numărul cromatic este de 2.
Problemele avute în vedere sunt legate de problema cunoscută de patru culori. Pentru a formula acest lucru, avem nevoie de mai multe definiții.
Se spune că un grafic este plat dacă este desenat pe un plan, iar cele 2 margini se pot intersecta numai la vârf.
Se spune că graficele sunt izomorfe. dacă există o astfel de numerotare a nodurilor în aceste grafice, aceștia au aceeași matrice de apropiere (de fapt, graficele izomorfice sunt aceleași grafice care diferă doar în altă imagine).
Un grafic este numit planar. dacă este izomorf cu un grafic plan. Astfel, graficul planar poate fi reprezentat pe plan drept plat. În Fig. Figura 11 prezintă două grafice izomorfe (identice), prima dintre ele fiind plană, iar cea de-a doua este plană.
Observăm cea mai cunoscută interpretare a problemei a patru culori. Să fie o hartă geografică. Este posibil, folosind numai 4 culori, să reprezinte această hartă astfel încât țările vecine (având o frontieră comună) să fie pictate în culori diferite? Este clar că în graficul corespunzător vârfurile sunt țările, iar țările vecine sunt vârfuri adiacente. Este clar că graficul obținut este planar, iar după 1976 răspunsul la această întrebare este pozitiv.
Rețineți că, în teoria grafurilor de multe ori pus întrebarea privind colorarea marginea grafice. Care este numărul minim de culori (acest număr este uneori menționată ca o margine-cromatica) trebuie să pictați marginile graficului, astfel încât oricare două muchii adiacente (de ex. E. 2 margini cu un vârf comun) ar fi vopsit într-o culoare diferită? Pentru numărul de vârf cromatică a unui grafic de evaluare are mult mai precise decât pur și simplu numărul cromatic, și anume, următorul text este adevărat, într-o oarecare măsură surprinzătoare, teorema.
Teorema lui Vizing. Dacă în grafic grafic gradul maxim de vârfuri este r. atunci numărul cromatic margine este egal fie cu r. sau r + 1.
Rețineți că nu există încă criterii "bune" pentru grafice, când exact numărul cromatic de margine este egal cu r. și când r + 1.
Evident, cel mai simplu algoritm pentru a găsi numărul de vârf cromatice (și marginile corespunzătoare ale colorația) este următoarea: pe grafic construirea unui grafic așa-numita dublă: marginile graficului corespund nodurilor unui nou (dublă) a graficului, iar în cazul în care cele două nervuri au un nod comun, ei Acestea sunt adiacente și în graficul dublu sunt conectate printr-o margine. După aceea culoarea cea mai de sus a graficului dublu și, merge la „vechi“ Count, obținem (un posibil) cele mai bune coaste de grafice coloranti.
În concluzie, observăm că colorarea de margine este adesea folosită în proiectarea diverselor dispozitive, în cazul în care firele care se conectează la un vârf ar trebui (pentru comoditate) să aibă culori diferite.
Articole similare
Trimiteți-le prietenilor: