Coloració de gràfics
La coloració de gràfics es pot descriure com un procés d'assignació de colors als vèrtexs d'un gràfic. En això, no s'ha d'utilitzar el mateix color per omplir els dos vèrtexs adjacents. També podem anomenar coloració de gràfics com a coloració de vèrtex. En la coloració de gràfics, hem de tenir cura que un gràfic no ha de contenir cap aresta els vèrtexs finals de la qual estiguin acolorits amb el mateix color. Aquest tipus de gràfic es coneix com a gràfic de color correctament.
Exemple de coloració de gràfics
què és hashset java
En aquest gràfic, estem mostrant el gràfic correctament acolorit, que es descriu de la següent manera:
El gràfic anterior conté alguns punts, que es descriuen de la següent manera:
- No es pot utilitzar el mateix color per acolorir els dos vèrtexs adjacents.
- Per tant, podem anomenar-lo com un gràfic de color correctament.
Aplicacions de la coloració de gràfics
Hi ha diverses aplicacions de coloració de gràfics. Algunes de les seves aplicacions importants es descriuen a continuació:
- Encàrrec
- Mapa per pintar
- Programació de les tasques
- Sudoku
- Preparar l'horari
- La resolució de conflictes
Número cromàtic
El nombre cromàtic es pot descriure com el nombre mínim de colors necessaris per acolorir correctament qualsevol gràfic. En altres paraules, el nombre cromàtic es pot descriure com un nombre mínim de colors que es necessiten per acolorir qualsevol gràfic de manera que no s'assigni el mateix color a dos vèrtexs adjacents d'un gràfic.
Exemple de nombre cromàtic:
Per entendre el nombre cromàtic, considerarem un gràfic, que es descriu de la següent manera:
El gràfic anterior conté alguns punts, que es descriuen de la següent manera:
- No s'utilitza el mateix color per acolorir els dos vèrtexs adjacents.
- El nombre mínim de colors d'aquest gràfic és 3, que és necessari per acolorir correctament els vèrtexs.
- Per tant, en aquest gràfic, el nombre cromàtic = 3
- Si volem pintar correctament aquest gràfic, en aquest cas, ens demanen almenys 3 colors.
Tipus de nombre cromàtic de gràfics:
Hi ha diversos tipus de nombre cromàtic de gràfics, que es descriuen de la següent manera:
Gràfic de cicle:
Un gràfic es coneixerà com a gràfic de cicle si conté 'n' arestes i 'n' vèrtexs (n >= 3), que formen un cicle de longitud 'n'. Només hi pot haver 2 o 3 nombres de graus de tots els vèrtexs del gràfic del cicle.
Número cromàtic:
- El nombre cromàtic en un gràfic de cicle serà 2 si el nombre de vèrtexs en aquest gràfic és parell.
- El nombre cromàtic en un gràfic de cicle serà 3 si el nombre de vèrtexs en aquest gràfic és senar.
Exemples de gràfics de cicle:
Hi ha diversos exemples de gràfics de cicle. Alguns d'ells es descriuen de la següent manera:
Exemple 1: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic del cicle anterior, hi ha 3 colors diferents per a tres vèrtexs i cap dels vèrtexs adjacents té el mateix color. En aquest gràfic, el nombre de vèrtexs és senar. Tan
Nombre cromàtic = 3
Exemple 2: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic del cicle anterior, hi ha 2 colors per a quatre vèrtexs i cap dels vèrtexs adjacents té el mateix color. En aquest gràfic, el nombre de vèrtexs és parell. Tan
Nombre cromàtic = 2
Exemple 3: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 4 colors diferents per a cinc vèrtexs, i dos vèrtexs adjacents tenen el mateix color (blau). Per tant, aquest gràfic no és un gràfic de cicle i no conté un nombre cromàtic.
Exemple 4: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 2 colors diferents per a sis vèrtexs, i cap dels vèrtexs adjacents té el mateix color. En aquest gràfic, el nombre de vèrtexs és parell. Tan
Nombre cromàtic = 2
Gràfic del planificador
Un gràfic es coneixerà com a gràfic planificador si està dibuixat en un pla. Les vores del gràfic del planificador no s'han de creuar.
Número cromàtic:
- En un gràfic de planificació, el nombre cromàtic ha de ser inferior o igual a 4.
- El gràfic del planificador també es pot mostrar amb tots els gràfics de cicle anteriors, excepte l'exemple 3.
Exemples de gràfics Planer:
Hi ha diversos exemples de gràfics de planer. Alguns d'ells es descriuen de la següent manera:
Exemple 1: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 3 colors diferents per a tres vèrtexs, i cap de les arestes d'aquest gràfic es creua. Tan
bash comproveu si la variable d'entorn està establerta
Nombre cromàtic = 3
Aquí, el nombre cromàtic és menor que 4, de manera que aquest gràfic és un gràfic pla.
Exemple 2: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 2 colors diferents per a quatre vèrtexs, i cap de les arestes d'aquest gràfic es creua. Tan
Nombre cromàtic = 2
Aquí, el nombre cromàtic és menor que 4, de manera que aquest gràfic és un gràfic pla.
Exemple 3: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 5 colors diferents per a cinc vèrtexs, i cap de les vores d'aquest gràfic es creua. Tan
Nombre cromàtic = 5
Aquí, el nombre cromàtic és més gran que 4, de manera que aquest gràfic no és un gràfic pla.
Exemple 4: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Al gràfic anterior, hi ha 2 colors diferents per a sis vèrtexs, i cap de les arestes d'aquest gràfic es creua. Tan
jvm en java
Nombre cromàtic = 2
Aquí, el nombre cromàtic és menor que 4, de manera que aquest gràfic és un gràfic pla.
Gràfic complet
Un gràfic es coneixerà com a gràfic complet si només s'utilitza una aresta per unir cada dos vèrtexs diferents. Cada vèrtex d'un gràfic complet està connectat amb qualsevol altre vèrtex. En aquest gràfic, cada vèrtex tindrà un color diferent. Això vol dir que en el gràfic complet, dos vèrtexs no contenen el mateix color.
Número cromàtic
En un gràfic complet, el nombre cromàtic serà igual al nombre de vèrtexs d'aquest gràfic.
Exemples de gràfic complet:
Hi ha diversos exemples de gràfics complets. Alguns d'ells es descriuen de la següent manera:
Exemple 1: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 4 colors diferents per a 4 vèrtexs diferents i cap dels colors és el mateix al gràfic anterior. Segons la definició, un nombre cromàtic és el nombre de vèrtexs. Tan,
Nombre cromàtic = 4
Exemple 2: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 5 colors diferents per a 5 vèrtexs diferents i cap dels colors és el mateix al gràfic anterior. Segons la definició, un nombre cromàtic és el nombre de vèrtexs. Tan,
Nombre cromàtic = 5
Exemple 3: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 3 colors diferents per a 4 vèrtexs diferents, i un color es repeteix en dos vèrtexs al gràfic anterior. Per tant, aquest gràfic no és un gràfic complet i no conté un nombre cromàtic.
Gràfic bipartit
Un graf es coneixerà com a graf bipartit si conté dos conjunts de vèrtexs, A i B. El vèrtex d'A només es pot unir amb els vèrtexs de B. Això vol dir que les arestes no poden unir els vèrtexs amb un conjunt.
Número cromàtic
En qualsevol gràfic bipartit, el nombre cromàtic sempre és igual a 2.
Exemples de gràfics bipartits:
Hi ha diversos exemples de gràfics bipartits. Alguns d'ells es descriuen de la següent manera:
Exemple 1: En el gràfic següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 2 conjunts diferents de vèrtexs al gràfic anterior. Per tant, el nombre cromàtic de tots els gràfics bipartits serà sempre 2. Per tant
Nombre cromàtic = 2
Arbre:
Un graf connectat es coneixerà com a arbre si no hi ha circuits en aquest gràfic. En un arbre, el nombre cromàtic serà igual a 2, independentment de quants vèrtexs hi hagi a l'arbre. Tot gràfic bipartit també és un arbre.
Número cromàtic
En qualsevol arbre, el nombre cromàtic és igual a 2.
string cerca c++
Exemples d'arbre:
Hi ha diversos exemples d'arbre. Alguns d'ells es descriuen de la següent manera:
Exemple 1: En l'arbre següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 2 colors diferents per a quatre vèrtexs. Un arbre amb qualsevol nombre de vèrtexs ha de contenir el nombre cromàtic com 2 a l'arbre anterior. Tan,
Nombre cromàtic = 2
Exemple 2: En l'arbre següent, hem de determinar el nombre cromàtic.
Solució: Hi ha 2 colors diferents per a cinc vèrtexs. Un arbre amb qualsevol nombre de vèrtexs ha de contenir el nombre cromàtic com 2 a l'arbre anterior. Tan,
Nombre cromàtic = 2
Exemple real de nombre cromàtic
Suposem que Marry és un gerent de l'empresa Xyz. L'empresa contracta nous empleats i ha d'aconseguir un calendari de formació per a aquests nous empleats. Ha de programar les tres reunions i està intentant utilitzar les poques franges horàries tant com sigui possible per a les reunions. Si hi ha un empleat que ha d'estar en dues reunions diferents, el gerent ha d'utilitzar els diferents horaris per a aquestes reunions. Suposem que volem obtenir una representació visual d'aquesta reunió.
Per a la representació visual, Marry utilitza el punt per indicar la reunió. Si hi ha un empleat que té dues reunions i requereix unir-se a les dues reunions, les dues reunions es connectaran amb l'ajuda d'un avantatge. Les diferents franges horàries es representen amb l'ajuda de colors. Així, el gestor omple els punts amb aquests colors de manera que dos punts no continguin el mateix color que comparteix una vora. (Això significa que un empleat que ha d'assistir a les dues reunions no ha de tenir la mateixa franja horària). La representació visual d'això es descriu de la següent manera:
