Colorazione del grafico
La colorazione del grafico può essere descritta come un processo di assegnazione dei colori ai vertici di un grafico. In questo, lo stesso colore non dovrebbe essere usato per riempire i due vertici adiacenti. Possiamo anche chiamare la colorazione del grafico come colorazione dei vertici. Nella colorazione dei grafi dobbiamo fare attenzione che un grafo non contenga alcun bordo i cui vertici finali siano colorati dello stesso colore. Questo tipo di grafico è noto come grafico colorato correttamente.
Esempio di colorazione del grafico
25 di 100
In questo grafico, mostriamo il grafico opportunamente colorato, che è descritto come segue:
Il grafico sopra contiene alcuni punti, che sono descritti come segue:
- Non è possibile utilizzare lo stesso colore per colorare i due vertici adiacenti.
- Quindi, possiamo chiamarlo come un grafico propriamente colorato.
Applicazioni della colorazione dei grafici
Esistono varie applicazioni della colorazione dei grafici. Alcune delle loro importanti applicazioni sono descritte come segue:
- Incarico
- Colorazione della mappa
- Pianificazione dei compiti
- Sudoku
- Preparare l'orario
- Risoluzione del conflitto
Numero cromatico
Il numero cromatico può essere descritto come il numero minimo di colori richiesti per colorare correttamente qualsiasi grafico. In altre parole, il numero cromatico può essere descritto come il numero minimo di colori necessari per colorare qualsiasi grafico in modo tale che a due vertici adiacenti di un grafico non venga assegnato lo stesso colore.
Esempio di numero cromatico:
Per comprendere il numero cromatico considereremo un grafico, che è descritto come segue:
Il grafico sopra contiene alcuni punti, che sono descritti come segue:
- Lo stesso colore non viene utilizzato per colorare i due vertici adiacenti.
- Il numero minimo di colori di questo grafico è 3, necessario per colorare correttamente i vertici.
- Quindi, in questo grafico, il numero cromatico = 3
- Se vogliamo colorare correttamente questo grafico, in questo caso ci servono almeno 3 colori.
Tipi di numero cromatico di grafici:
Esistono vari tipi di numeri cromatici dei grafici, descritti di seguito:
Grafico del ciclo:
Un grafo sarà detto grafo ciclo se contiene 'n' archi e 'n' vertici (n >= 3), che formano un ciclo di lunghezza 'n'. Ci possono essere solo 2 o 3 gradi di tutti i vertici nel grafico del ciclo.
Numero cromatico:
- Il numero cromatico in un grafico ciclico sarà 2 se il numero di vertici in quel grafico è pari.
- Il numero cromatico in un grafico ciclico sarà 3 se il numero di vertici in quel grafico è dispari.
Esempi di grafico del ciclo:
Esistono vari esempi di grafici ciclici. Alcuni di essi sono descritti come segue:
Esempio 1: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico del ciclo sopra, ci sono 3 colori diversi per tre vertici e nessuno dei vertici adiacenti è colorato con lo stesso colore. In questo grafico, il numero di vertici è dispari. COSÌ
Numero cromatico = 3
Esempio 2: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico del ciclo sopra, ci sono 2 colori per quattro vertici e nessuno dei vertici adiacenti è colorato con lo stesso colore. In questo grafico, il numero di vertici è pari. COSÌ
Numero cromatico = 2
Esempio 3: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 4 colori diversi per cinque vertici e due vertici adiacenti sono colorati con lo stesso colore (blu). Quindi questo grafico non è un grafico ciclico e non contiene un numero cromatico.
Esempio 4: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 2 colori diversi per sei vertici e nessuno dei vertici adiacenti è colorato con lo stesso colore. In questo grafico, il numero di vertici è pari. COSÌ
Numero cromatico = 2
Grafico del pianificatore
Un grafico sarà detto grafico pianificatore se è disegnato su un piano. I bordi del grafico del pianificatore non devono incrociarsi.
Numero cromatico:
- In un grafico pianificatore, il Numero cromatico deve essere inferiore o uguale a 4.
- Il grafico del pianificatore può anche essere mostrato da tutti i grafici del ciclo sopra tranne l'esempio 3.
Esempi di grafico Planer:
Esistono vari esempi di grafici planari. Alcuni di essi sono descritti come segue:
Esempio 1: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 3 colori diversi per tre vertici e nessuno dei bordi di questo grafico si incrocia. COSÌ
conversione della stringa in data
Numero cromatico = 3
Qui, il numero cromatico è inferiore a 4, quindi questo grafico è un grafico piano.
Esempio 2: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 2 colori diversi per quattro vertici e nessuno dei bordi di questo grafico si incrocia. COSÌ
Numero cromatico = 2
Qui, il numero cromatico è inferiore a 4, quindi questo grafico è un grafico piano.
Esempio 3: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 5 colori diversi per cinque vertici e nessuno dei bordi di questo grafico si incrocia. COSÌ
Numero cromatico = 5
Qui il numero cromatico è maggiore di 4, quindi questo grafico non è un grafico piano.
Esempio 4: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Nel grafico sopra, ci sono 2 colori diversi per sei vertici e nessuno dei bordi di questo grafico si incrocia. COSÌ
Numero cromatico = 2
Qui, il numero cromatico è inferiore a 4, quindi questo grafico è un grafico piano.
Grafico completo
Un grafo sarà noto come grafo completo se viene utilizzato un solo spigolo per unire ogni due vertici distinti. Ogni vertice in un grafo completo è connesso con ogni altro vertice. In questo grafico ogni vertice sarà colorato con un colore diverso. Ciò significa che nel grafico completo due vertici non contengono lo stesso colore.
Numero cromatico
In un grafico completo, il numero cromatico sarà uguale al numero di vertici in quel grafico.
Esempi di grafico completo:
algoritmo per rsa
Esistono vari esempi di grafici completi. Alcuni di essi sono descritti come segue:
Esempio 1: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Esistono 4 colori diversi per 4 vertici diversi e nessuno dei colori è uguale nel grafico sopra. Secondo la definizione, un numero cromatico è il numero di vertici. COSÌ,
Numero cromatico = 4
Esempio 2: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Esistono 5 colori diversi per 5 vertici diversi e nessuno dei colori è uguale nel grafico sopra. Secondo la definizione, un numero cromatico è il numero di vertici. COSÌ,
Numero cromatico = 5
Esempio 3: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Esistono 3 colori diversi per 4 vertici diversi e un colore viene ripetuto in due vertici nel grafico sopra. Quindi questo grafico non è un grafico completo e non contiene un numero cromatico.
Grafico bipartito
Un grafo sarà noto come grafo bipartito se contiene due insiemi di vertici, A e B. Il vertice di A può unirsi solo ai vertici di B. Ciò significa che gli spigoli non possono unire i vertici con un insieme.
Numero cromatico
In ogni grafo bipartito il numero cromatico è sempre uguale a 2.
Esempi di grafico bipartito:
Esistono vari esempi di grafi bipartiti. Alcuni di essi sono descritti come segue:
Esempio 1: Nel grafico seguente dobbiamo determinare il numero cromatico.
Soluzione: Ci sono 2 diversi insiemi di vertici nel grafico sopra. Quindi il numero cromatico di tutti i grafi bipartiti sarà sempre 2. Quindi
Numero cromatico = 2
Albero:
Un grafo connesso sarà detto albero se in quel grafo non sono presenti circuiti. In un albero, il numero cromatico sarà uguale a 2 indipendentemente dal numero di vertici presenti nell'albero. Ogni grafo bipartito è anche un albero.
Numero cromatico
In ogni albero il numero cromatico è uguale a 2.
decodifica base64 in js
Esempi di albero:
Esistono vari esempi di albero. Alcuni di essi sono descritti come segue:
Esempio 1: Nell'albero seguente dobbiamo determinare il numero cromatico.
Soluzione: Ci sono 2 colori diversi per quattro vertici. Un albero con un numero qualsiasi di vertici deve contenere il numero cromatico pari a 2 nell'albero sopra. COSÌ,
Numero cromatico = 2
Esempio 2: Nell'albero seguente dobbiamo determinare il numero cromatico.
Soluzione: Ci sono 2 colori diversi per cinque vertici. Un albero con un numero qualsiasi di vertici deve contenere il numero cromatico pari a 2 nell'albero sopra. COSÌ,
Numero cromatico = 2
Esempio di vita reale di numero cromatico
Supponiamo che Marry sia un manager della Xyz Company. L'azienda assume alcuni nuovi dipendenti e deve elaborare un programma di formazione per questi nuovi dipendenti. Deve programmare i tre incontri e cerca di sfruttare il più possibile le poche fasce orarie per le riunioni. Se un dipendente deve essere presente a due riunioni diverse, il manager deve utilizzare orari diversi per tali riunioni. Supponiamo di voler ottenere una rappresentazione visiva di questo incontro.
Per la rappresentazione visiva, Marry utilizza il punto per indicare l'incontro. Se c'è un dipendente che ha due riunioni e richiede di partecipare a entrambe le riunioni, entrambe le riunioni saranno collegate con l'aiuto di un edge. Le diverse fasce orarie sono rappresentate con l'aiuto dei colori. Quindi il gestore riempie i punti con questi colori in modo tale che due punti non contengano lo stesso colore che condivide un bordo. (Ciò significa che un dipendente che deve presenziare alle due riunioni non deve avere la stessa fascia oraria). La rappresentazione visiva di ciò è descritta come segue:
