📖 Lecția 07 · Grafuri

Colorarea Hărții

Teorema celor 4 culori: orice hartă plană poate fi colorată cu cel mult 4 culori astfel încât nicio două regiuni vecine să nu aibă aceeași culoare.

Teorie

🗺️ Problema

Avem o hartă formată din regiuni poligonale. Două regiuni sunt vecine dacă împart o porțiune de graniță comună (nu doar un punct). Vrem să colorăm fiecare regiune cu una din 4 culori astfel încât nicio regiune să nu fie adiacentă cu alta de aceeași culoare.

Această problemă este echivalentă cu colorarea unui graf: regiunile → noduri, granițele comune → muchii.

🔁 Abordarea BKT

Algoritmul încearcă pe rând toate cele 4 culori pentru fiecare regiune. Dacă o culoare este validă (nu există vecin cu aceeași culoare), o atribuim și trecem la următoarea regiune. Dacă nicio culoare nu funcționează — dăm înapoi și schimbăm culoarea regiunii precedente.

Teorema celor 4 culori: mereu există o soluție cu ≤ 4 culori

💻 Cod C++ — Colorare Hartă BKT

💻 Cod C++
#include <iostream> using namespace std; int n, m, x[20], sol = 0; int a[20][20]; // matricea de adiacenta void INIT(int k) { x[k] = 0; } int EXISTA(int k) { if(x[k] < m) return 1; else return 0; } int VALID(int k) { for(int i = 1; i <= n; i++) if(a[k][i] && x[i] == x[k]) return 0; return 1; } int SOLUTIE(int k) { if(k == n) return 1; else return 0; } void TIPAR(int k) { int i; sol++; cout << "Solutia " << sol << ": "; for(i = 1; i <= k; i++) cout << x[i] << " "; cout << endl; } void BCK() { int k = 1; INIT(k); while(k > 0) if(EXISTA(k)) { x[k]++; if(VALID(k)) { if(SOLUTIE(k)) TIPAR(k); else { k++; INIT(k); } } } else k--; } int main() { cout << "Numar noduri: "; cin >> n; cout << "Numar culori: "; cin >> m; cout << "Matricea de adiacenta:" << endl; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; BCK(); cout << "S-au generat " << sol << " solutii." << endl; return 0; }
Demonstrație interactivă
Viteza:
Mod:
Nordvest Nord Nordest Vest Centru Est Sudvest Sud Sudest
Încercări
0
total colorări testate
Reveniri
0
backtrack-uri
Soluții
0
colorări complete
Apasă ▶ Play pentru a porni
Culori disponibile
Indigo
Verde
Chihlimbar
Roșu
Progres
Regiune: — Culoare: —
Soluții găsite