Colorarea graficului
Colorarea graficului poate fi descrisă ca un proces de atribuire a culorilor vârfurilor unui grafic. În aceasta, aceeași culoare nu trebuie folosită pentru a umple cele două vârfuri adiacente. De asemenea, putem numi colorarea graficelor ca Colorare a vârfurilor. În colorarea graficelor, trebuie să avem grijă ca un grafic să nu conțină nicio muchie ale cărei vârfuri de capăt sunt colorate cu aceeași culoare. Acest tip de grafic este cunoscut sub numele de graficul colorat corect.
Exemplu de colorare a graficului
cheia ins
În acest grafic, arătăm graficul colorat corespunzător, care este descris după cum urmează:
Graficul de mai sus conține câteva puncte, care sunt descrise după cum urmează:
- Aceeași culoare nu poate fi folosită pentru a colora cele două vârfuri adiacente.
- Prin urmare, îl putem numi ca un grafic colorat corespunzător.
Aplicații ale colorării grafice
Există diverse aplicații ale colorării graficelor. Unele dintre aplicațiile lor importante sunt descrise după cum urmează:
- Misiune
- Colorarea hărții
- Programarea sarcinilor
- Sudoku
- Pregătiți orarul
- Rezolvarea conflictului
Număr cromatic
Numărul cromatic poate fi descris ca numărul minim de culori necesare pentru a colora corect orice grafic. Cu alte cuvinte, numărul cromatic poate fi descris ca un număr minim de culori care sunt necesare pentru a colora orice grafic în așa fel încât să nu i se atribuie aceeași culoare două vârfuri adiacente ale unui grafic.
Exemplu de număr cromatic:
Pentru a înțelege numărul cromatic, vom lua în considerare un grafic, care este descris după cum urmează:
Graficul de mai sus conține câteva puncte, care sunt descrise după cum urmează:
- Nu se folosește aceeași culoare pentru a colora cele două vârfuri adiacente.
- Numărul minim de culori ale acestui grafic este 3, care este necesar pentru a colora corect vârfurile.
- Prin urmare, în acest grafic, numărul cromatic = 3
- Dacă dorim să colorăm corect acest grafic, în acest caz, ni se cer cel puțin 3 culori.
Tipuri de număr cromatic de grafice:
Există diferite tipuri de număr cromatic de grafice, care sunt descrise după cum urmează:
Graficul ciclului:
Un grafic va fi cunoscut ca un grafic de ciclu dacă conține „n” muchii și „n” vârfuri (n >= 3), care formează un ciclu de lungime „n”. Pot exista doar 2 sau 3 număr de grade din toate vârfurile din graficul ciclului.
Număr cromatic:
- Numărul cromatic dintr-un grafic de ciclu va fi 2 dacă numărul de vârfuri din acel grafic este par.
- Numărul cromatic dintr-un grafic de ciclu va fi 3 dacă numărul de vârfuri din acel grafic este impar.
Exemple de graficul ciclului:
Există diverse exemple de grafice de ciclu. Unele dintre ele sunt descrise după cum urmează:
Exemplul 1: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul ciclului de mai sus, există 3 culori diferite pentru trei vârfuri și niciunul dintre vârfurile adiacente nu este colorat cu aceeași culoare. În acest grafic, numărul de vârfuri este impar. Asa de
Număr cromatic = 3
Exemplul 2: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul ciclului de mai sus, există 2 culori pentru patru vârfuri și niciunul dintre vârfurile adiacente nu este colorat cu aceeași culoare. În acest grafic, numărul de vârfuri este par. Asa de
Număr cromatic = 2
Exemplul 3: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 4 culori diferite pentru cinci vârfuri, iar două vârfuri adiacente sunt colorate cu aceeași culoare (albastru). Deci, acest grafic nu este un grafic de ciclu și nu conține un număr cromatic.
Exemplul 4: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 2 culori diferite pentru șase vârfuri și niciunul dintre vârfurile adiacente nu este colorat cu aceeași culoare. În acest grafic, numărul de vârfuri este par. Asa de
Număr cromatic = 2
Graficul planificatorului
Un grafic va fi cunoscut sub numele de grafic planificator dacă este desenat într-un plan. Marginile graficului planificatorului nu trebuie să se încrucișeze.
Număr cromatic:
- Într-un grafic planificator, numărul cromatic trebuie să fie mai mic sau egal cu 4.
- Graficul planificatorului poate fi afișat și de toate graficele ciclului de mai sus, cu excepția exemplului 3.
Exemple de grafic Planer:
Există diverse exemple de grafice planer. Unele dintre ele sunt descrise după cum urmează:
Exemplul 1: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 3 culori diferite pentru trei vârfuri și niciuna dintre marginile acestui grafic nu se intersectează. Asa de
conversia șirului în dată
Număr cromatic = 3
Aici, numărul cromatic este mai mic decât 4, deci acest grafic este un grafic plan.
Exemplul 2: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 2 culori diferite pentru patru vârfuri și niciuna dintre marginile acestui grafic nu se intersectează. Asa de
Număr cromatic = 2
Aici, numărul cromatic este mai mic decât 4, deci acest grafic este un grafic plan.
Exemplul 3: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 5 culori diferite pentru cinci vârfuri și niciuna dintre marginile acestui grafic nu se intersectează. Asa de
Număr cromatic = 5
Aici, numărul cromatic este mai mare decât 4, deci acest grafic nu este un grafic plan.
Exemplul 4: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: În graficul de mai sus, există 2 culori diferite pentru șase vârfuri și niciuna dintre marginile acestui grafic nu se intersectează. Asa de
Număr cromatic = 2
Aici, numărul cromatic este mai mic decât 4, deci acest grafic este un grafic plan.
Graficul complet
Un grafic va fi cunoscut ca un grafic complet dacă este folosită o singură muchie pentru a uni fiecare două vârfuri distincte. Fiecare vârf dintr-un grafic complet este conectat cu orice alt vârf. În acest grafic, fiecare vârf va fi colorat cu o culoare diferită. Asta înseamnă că în graficul complet, două vârfuri nu conțin aceeași culoare.
Număr cromatic
formatator de șiruri
Într-un grafic complet, numărul cromatic va fi egal cu numărul de vârfuri din acel grafic.
Exemple de grafic complet:
Există diverse exemple de grafice complete. Unele dintre ele sunt descrise după cum urmează:
Exemplul 1: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 4 culori diferite pentru 4 vârfuri diferite și niciuna dintre culori nu este aceeași în graficul de mai sus. Conform definiției, un număr cromatic este numărul de vârfuri. Asa de,
Număr cromatic = 4
Exemplul 2: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 5 culori diferite pentru 5 vârfuri diferite și niciuna dintre culori nu este aceeași în graficul de mai sus. Conform definiției, un număr cromatic este numărul de vârfuri. Asa de,
Număr cromatic = 5
Exemplul 3: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 3 culori diferite pentru 4 vârfuri diferite și o culoare se repetă în două vârfuri în graficul de mai sus. Deci acest grafic nu este un grafic complet și nu conține un număr cromatic.
Graficul bipartit
Un graf va fi cunoscut ca graf bipartit dacă conține două seturi de vârfuri, A și B. Vârful lui A se poate uni doar cu vârfurile lui B. Asta înseamnă că muchiile nu pot uni vârfurile cu o mulțime.
Număr cromatic
În orice grafic bipartit, numărul cromatic este întotdeauna egal cu 2.
Exemple de grafice bipartite:
Există diverse exemple de grafice bipartite. Unele dintre ele sunt descrise după cum urmează:
Exemplul 1: În graficul următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 2 seturi diferite de vârfuri în graficul de mai sus. Deci numărul cromatic al tuturor graficelor bipartite va fi întotdeauna 2. Deci
Număr cromatic = 2
Copac:
Un graf conectat va fi cunoscut ca arbore dacă nu există circuite în acel graf. Într-un arbore, numărul cromatic va fi egal cu 2, indiferent câte vârfuri sunt în arbore. Fiecare graf bipartit este, de asemenea, un arbore.
Număr cromatic
În orice arbore, numărul cromatic este egal cu 2.
important
Exemple de arbore:
Există diverse exemple de copac. Unele dintre ele sunt descrise după cum urmează:
Exemplul 1: În arborele următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 2 culori diferite pentru patru vârfuri. Un arbore cu orice număr de vârfuri trebuie să conțină numărul cromatic ca 2 în arborele de mai sus. Asa de,
Număr cromatic = 2
Exemplul 2: În arborele următor, trebuie să determinăm numărul cromatic.
Soluţie: Există 2 culori diferite pentru cinci vârfuri. Un arbore cu orice număr de vârfuri trebuie să conțină numărul cromatic ca 2 în arborele de mai sus. Asa de,
Număr cromatic = 2
Exemplu real de număr cromatic
Să presupunem că Marry este manager în compania Xyz. Compania angajează câțiva angajați noi, iar ea trebuie să obțină un program de pregătire pentru acești noi angajați. Ea trebuie să programeze cele trei întâlniri și încearcă să folosească cât mai mult posibil cele câteva intervale de timp pentru întâlniri. Dacă există un angajat care trebuie să participe la două întâlniri diferite, atunci managerul trebuie să folosească orare diferite pentru acele întâlniri. Să presupunem că vrem să obținem o reprezentare vizuală a acestei întâlniri.
Pentru reprezentarea vizuală, Marry folosește punctul pentru a indica întâlnirea. Dacă există un angajat care are două întâlniri și necesită să se alăture ambelor întâlniri, atunci ambele întâlniri vor fi conectate cu ajutorul unei margini. Diferitele intervale orare sunt reprezentate cu ajutorul culorilor. Deci, managerul umple punctele cu aceste culori în așa fel încât două puncte să nu conțină aceeași culoare care împarte o margine. (Asta înseamnă că un angajat care trebuie să participe la cele două întâlniri nu trebuie să aibă același interval orar). Reprezentarea vizuală a acesteia este descrisă după cum urmează:
