Graffarging
Graffarging kan beskrives som en prosess for å tildele farger til toppunktene i en graf. I dette skal ikke samme farge brukes til å fylle de to tilstøtende hjørnene. Vi kan også kalle graffarging som vertexfarging. Ved graffarging må vi passe på at en graf ikke må inneholde noen kant hvis endepunkt er farget av samme farge. Denne typen grafer er kjent som riktig farget graf.
Eksempel på graffarging
mergesort java
I denne grafen viser vi den riktig fargede grafen, som er beskrevet som følger:
Grafen ovenfor inneholder noen punkter, som er beskrevet som følger:
- Den samme fargen kan ikke brukes til å farge de to tilstøtende hjørnene.
- Derfor kan vi kalle det som en riktig farget graf.
Bruk av graffarging
Det er forskjellige bruksområder for graffarging. Noen av deres viktige applikasjoner er beskrevet som følger:
- Oppdrag
- Fargelegging av kart
- Planlegging av oppgavene
- Sudoku
- Lag timeplan
- Konfliktløsning
Kromatisk tall
Det kromatiske tallet kan beskrives som minimum antall farger som kreves for å fargelegge en graf. Med andre ord kan det kromatiske tallet beskrives som et minimum antall farger som er nødvendig for å farge en graf på en slik måte at ingen to tilstøtende hjørner av en graf vil bli tildelt samme farge.
Eksempel på kromatisk tall:
For å forstå det kromatiske tallet, vil vi vurdere en graf, som er beskrevet som følger:
Grafen ovenfor inneholder noen punkter, som er beskrevet som følger:
- Den samme fargen brukes ikke til å farge de to tilstøtende hjørnene.
- Minimumsantallet av farger i denne grafen er 3, som er nødvendig for å farge toppunktene riktig.
- Derfor, i denne grafen, er det kromatiske tallet = 3
- Hvis vi ønsker å fargelegge denne grafen riktig, i dette tilfellet, trenger vi minst 3 farger.
Typer kromatisk antall grafer:
Det finnes ulike typer kromatisk antall grafer, som er beskrevet som følger:
Syklusgraf:
En graf vil bli kjent som en syklusgraf hvis den inneholder 'n' kanter og 'n' toppunkter (n >= 3), som danner en syklus med lengden 'n'. Det kan bare være 2 eller 3 antall grader av alle toppunktene i syklusgrafen.
Kromatisk tall:
- Det kromatiske tallet i en syklusgraf vil være 2 hvis antall toppunkter i den grafen er partall.
- Det kromatiske tallet i en syklusgraf vil være 3 hvis antall toppunkter i den grafen er oddetall.
Eksempler på syklusgraf:
Det finnes ulike eksempler på syklusgrafer. Noen av dem er beskrevet som følger:
Eksempel 1: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I syklusgrafen ovenfor er det 3 forskjellige farger for tre hjørner, og ingen av de tilstøtende hjørnene er farget med samme farge. I denne grafen er antall toppunkter oddetall. Så
Kromatisk tall = 3
Eksempel 2: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I syklusgrafen ovenfor er det 2 farger for fire hjørner, og ingen av de tilstøtende hjørnene er farget med samme farge. I denne grafen er antall toppunkter partall. Så
Kromatisk tall = 2
Eksempel 3: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 4 forskjellige farger for fem hjørner, og to tilstøtende hjørner er farget med samme farge (blå). Så denne grafen er ikke en syklusgraf og inneholder ikke et kromatisk tall.
Eksempel 4: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 2 forskjellige farger for seks hjørner, og ingen av de tilstøtende hjørnene er farget med samme farge. I denne grafen er antall toppunkter partall. Så
Kromatisk tall = 2
Planleggergraf
En graf vil bli kjent som en planleggergraf hvis den er tegnet i et plan. Kantene på planleggergrafen må ikke krysse hverandre.
Kromatisk nummer:
- I en planleggergraf må det kromatiske tallet være mindre enn eller lik 4.
- Planleggergrafen kan også vises med alle syklusgrafene ovenfor bortsett fra eksempel 3.
Eksempler på planeringsgraf:
Det finnes ulike eksempler på høvelgrafer. Noen av dem er beskrevet som følger:
Eksempel 1: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 3 forskjellige farger for tre hjørner, og ingen av kantene på denne grafen krysser hverandre. Så
kall javascript-funksjon fra html
Kromatisk tall = 3
Her er det kromatiske tallet mindre enn 4, så denne grafen er en plan graf.
Eksempel 2: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 2 forskjellige farger for fire hjørner, og ingen av kantene på denne grafen krysser hverandre. Så
Kromatisk tall = 2
Her er det kromatiske tallet mindre enn 4, så denne grafen er en plan graf.
Eksempel 3: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 5 forskjellige farger for fem hjørner, og ingen av kantene på denne grafen krysser hverandre. Så
Kromatisk tall = 5
Her er det kromatiske tallet større enn 4, så denne grafen er ikke en plan graf.
Eksempel 4: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: I grafen ovenfor er det 2 forskjellige farger for seks hjørner, og ingen av kantene på denne grafen krysser hverandre. Så
Kromatisk tall = 2
Her er det kromatiske tallet mindre enn 4, så denne grafen er en plan graf.
Komplett graf
En graf vil bli kjent som en komplett graf hvis bare én kant brukes til å slå sammen hver to distinkte toppunkter. Hvert toppunkt i en komplett graf er forbundet med hvert annet toppunkt. I denne grafen vil hvert toppunkt være farget med en annen farge. Det betyr at i den komplette grafen inneholder ikke to hjørner samme farge.
Kromatisk tall
I en komplett graf vil det kromatiske tallet være lik antall toppunkter i den grafen.
Eksempler på komplett graf:
Det finnes ulike eksempler på komplette grafer. Noen av dem er beskrevet som følger:
Eksempel 1: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: Det er 4 forskjellige farger for 4 forskjellige hjørner, og ingen av fargene er like i grafen ovenfor. I følge definisjonen er et kromatisk tall antall toppunkter. Så,
Kromatisk tall = 4
Eksempel 2: I den følgende grafen må vi bestemme det kromatiske tallet.
medieoverføring
Løsning: Det er 5 forskjellige farger for 5 forskjellige hjørner, og ingen av fargene er like i grafen ovenfor. I følge definisjonen er et kromatisk tall antall toppunkter. Så,
Kromatisk tall = 5
Eksempel 3: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: Det er 3 forskjellige farger for 4 forskjellige hjørner, og en farge gjentas i to hjørner i grafen ovenfor. Så denne grafen er ikke en fullstendig graf og inneholder ikke et kromatisk tall.
Todelt graf
En graf vil bli kjent som en todelt graf hvis den inneholder to sett med toppunkter, A og B. Toppunktet til A kan bare slå seg sammen med toppunktene til B. Det betyr at kantene ikke kan forbinde toppunktene med et sett.
Kromatisk tall
I enhver todelt graf er det kromatiske tallet alltid lik 2.
Eksempler på todelt graf:
Det finnes ulike eksempler på todelte grafer. Noen av dem er beskrevet som følger:
Eksempel 1: I den følgende grafen må vi bestemme det kromatiske tallet.
Løsning: Det er 2 forskjellige sett med toppunkter i grafen ovenfor. Så det kromatiske tallet for alle todelte grafer vil alltid være 2. Så
Kromatisk tall = 2
Tre:
En tilkoblet graf vil bli kjent som et tre hvis det ikke er noen kretser i den grafen. I et tre vil det kromatiske tallet være lik 2 uansett hvor mange hjørner som er i treet. Hver todelt graf er også et tre.
Kromatisk tall
I ethvert tre er det kromatiske tallet lik 2.
lenket liste i java
Eksempler på tre:
Det er forskjellige eksempler på et tre. Noen av dem er beskrevet som følger:
Eksempel 1: I det følgende treet må vi bestemme det kromatiske tallet.
Løsning: Det er 2 forskjellige farger for fire hjørner. Et tre med et hvilket som helst antall hjørner må inneholde det kromatiske tallet som 2 i treet ovenfor. Så,
Kromatisk tall = 2
Eksempel 2: I det følgende treet må vi bestemme det kromatiske tallet.
Løsning: Det er 2 forskjellige farger for fem hjørner. Et tre med et hvilket som helst antall hjørner må inneholde det kromatiske tallet som 2 i treet ovenfor. Så,
Kromatisk tall = 2
Eksempler fra det virkelige liv på kromatisk tall
Anta at Marry er leder i Xyz Company. Selskapet ansetter noen nye medarbeidere, og hun må få en opplæringsplan for de nye ansatte. Hun må planlegge de tre møtene, og hun prøver å bruke de få tidslukene så mye som mulig til møter. Hvis det er en ansatt som må være på to forskjellige møter, må lederen bruke de forskjellige tidsplanene for disse møtene. Anta at vi ønsker å få en visuell representasjon av dette møtet.
For den visuelle representasjonen bruker Marry prikken for å indikere møtet. Hvis det er en ansatt som har to møter og krever å være med på begge møtene, vil begge møtet kobles sammen ved hjelp av en kant. De forskjellige tidslukene er representert ved hjelp av farger. Så lederen fyller prikkene med disse fargene på en slik måte at to prikker ikke inneholder samme farge som deler en kant. (Det betyr at en ansatt som må delta på de to møtene ikke må ha samme tidsluke). Den visuelle representasjonen av dette er beskrevet som følger:
