Graffarvning
Graffarvning kan beskrives som en proces med at tildele farver til hjørnerne af en graf. I denne bør den samme farve ikke bruges til at fylde de to tilstødende hjørner. Vi kan også kalde graffarvning som vertexfarvning. Ved graffarvning skal vi passe på, at en graf ikke må indeholde nogen kant, hvis endespidser er farvet af samme farve. Denne type graf er kendt som den korrekt farvede graf.
Eksempel på graffarvning
js indlæst
I denne graf viser vi den korrekt farvede graf, som er beskrevet som følger:
Ovenstående graf indeholder nogle punkter, som er beskrevet som følger:
- Den samme farve kan ikke bruges til at farve de to tilstødende hjørner.
- Derfor kan vi kalde det som en korrekt farvet graf.
Anvendelser af graffarvning
Der er forskellige anvendelser af graffarvning. Nogle af deres vigtige applikationer er beskrevet som følger:
- Opgave
- Farvelægning af kort
- Planlægning af opgaverne
- Sudoku
- Forbered tidsplan
- Konfliktløsning
Kromatisk nummer
Det kromatiske tal kan beskrives som det mindste antal farver, der kræves for at farve enhver graf korrekt. Med andre ord kan det kromatiske tal beskrives som et minimumsantal af farver, der er nødvendige for at farve enhver graf på en sådan måde, at ikke to tilstødende hjørner af en graf vil blive tildelt den samme farve.
Eksempel på kromatisk tal:
For at forstå det kromatiske tal vil vi overveje en graf, som er beskrevet som følger:
Ovenstående graf indeholder nogle punkter, som er beskrevet som følger:
- Den samme farve bruges ikke til at farve de to tilstødende hjørner.
- Minimumsantallet af farver i denne graf er 3, hvilket er nødvendigt for at farve toppunkterne korrekt.
- Derfor, i denne graf, er det kromatiske tal = 3
- Hvis vi ønsker at farve denne graf korrekt, skal vi i dette tilfælde have mindst 3 farver.
Typer af kromatisk antal grafer:
Der er forskellige typer kromatiske antal grafer, som er beskrevet som følger:
Cyklusgraf:
En graf vil blive kendt som en cyklusgraf, hvis den indeholder 'n' kanter og 'n' hjørner (n >= 3), som danner en cyklus med længden 'n'. Der kan kun være 2 eller 3 antal grader af alle hjørnerne i cyklusgrafen.
Kromatisk tal:
- Det kromatiske tal i en cyklusgraf vil være 2, hvis antallet af hjørner i denne graf er lige.
- Det kromatiske tal i en cyklusgraf vil være 3, hvis antallet af hjørner i denne graf er ulige.
Eksempler på cyklusgraf:
Der er forskellige eksempler på cyklusgrafer. Nogle af dem er beskrevet som følger:
Eksempel 1: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående cyklusgraf er der 3 forskellige farver for tre hjørner, og ingen af de tilstødende hjørner er farvet med samme farve. I denne graf er antallet af hjørner ulige. Så
Kromatisk tal = 3
Eksempel 2: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående cyklusgraf er der 2 farver for fire hjørner, og ingen af de tilstødende hjørner er farvet med samme farve. I denne graf er antallet af hjørner lige. Så
Kromatisk tal = 2
Eksempel 3: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 4 forskellige farver for fem hjørner, og to tilstødende hjørner er farvet med samme farve (blå). Så denne graf er ikke en cyklusgraf og indeholder ikke et kromatisk tal.
Eksempel 4: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 2 forskellige farver til seks hjørner, og ingen af de tilstødende hjørner er farvet med samme farve. I denne graf er antallet af hjørner lige. Så
Kromatisk tal = 2
Planlægger graf
En graf vil være kendt som en planlægningsgraf, hvis den er tegnet i et plan. Plannergrafens kanter må ikke krydse hinanden.
Kromatisk tal:
- I en planlægningsgraf skal det kromatiske tal være mindre end eller lig med 4.
- Planlæggergrafen kan også vises med alle ovenstående cyklusgrafer undtagen eksempel 3.
Eksempler på Planer-graf:
Der er forskellige eksempler på høvlegrafer. Nogle af dem er beskrevet som følger:
Eksempel 1: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 3 forskellige farver for tre hjørner, og ingen af kanterne på denne graf krydser hinanden. Så
forskel på ræv og ulv
Kromatisk tal = 3
Her er det kromatiske tal mindre end 4, så denne graf er en plan graf.
Eksempel 2: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 2 forskellige farver for fire hjørner, og ingen af kanterne på denne graf krydser hinanden. Så
Kromatisk tal = 2
Her er det kromatiske tal mindre end 4, så denne graf er en plan graf.
Eksempel 3: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 5 forskellige farver for fem hjørner, og ingen af kanterne på denne graf krydser hinanden. Så
Kromatisk tal = 5
Her er det kromatiske tal større end 4, så denne graf er ikke en plan graf.
Eksempel 4: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: I ovenstående graf er der 2 forskellige farver for seks hjørner, og ingen af kanterne på denne graf krydser hinanden. Så
Kromatisk tal = 2
Her er det kromatiske tal mindre end 4, så denne graf er en plan graf.
Komplet graf
En graf vil blive kendt som en komplet graf, hvis kun én kant bruges til at forbinde hver to distinkte hjørner. Hvert toppunkt i en komplet graf er forbundet med hvert andet toppunkt. I denne graf vil hvert toppunkt være farvet med en anden farve. Det betyder i den komplette graf, at to hjørner ikke indeholder den samme farve.
Kromatisk tal
I en komplet graf vil det kromatiske tal være lig med antallet af hjørner i denne graf.
Eksempler på komplet graf:
Der er forskellige eksempler på komplette grafer. Nogle af dem er beskrevet som følger:
Eksempel 1: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: Der er 4 forskellige farver til 4 forskellige hjørner, og ingen af farverne er ens i ovenstående graf. Ifølge definitionen er et kromatisk tal antallet af hjørner. Så,
Kromatisk tal = 4
Eksempel 2: I den følgende graf skal vi bestemme det kromatiske tal.
linux vært
Løsning: Der er 5 forskellige farver til 5 forskellige hjørner, og ingen af farverne er ens i ovenstående graf. Ifølge definitionen er et kromatisk tal antallet af hjørner. Så,
Kromatisk tal = 5
Eksempel 3: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: Der er 3 forskellige farver til 4 forskellige hjørner, og en farve gentages i to hjørner i ovenstående graf. Så denne graf er ikke en komplet graf og indeholder ikke et kromatisk tal.
Todelt graf
En graf vil blive kendt som en todelt graf, hvis den indeholder to sæt toppunkter, A og B. Toppunktet af A kan kun forbindes med toppunkterne på B. Det betyder, at kanterne ikke kan forbinde toppunkterne med et sæt.
Kromatisk nummer
I enhver todelt graf er det kromatiske tal altid lig med 2.
Eksempler på todelt graf:
Der er forskellige eksempler på todelte grafer. Nogle af dem er beskrevet som følger:
Eksempel 1: I den følgende graf skal vi bestemme det kromatiske tal.
Løsning: Der er 2 forskellige sæt toppunkter i ovenstående graf. Så det kromatiske antal af alle todelte grafer vil altid være 2. Altså
Kromatisk tal = 2
Træ:
En forbundet graf vil blive kendt som et træ, hvis der ikke er nogen kredsløb i den graf. I et træ vil det kromatiske tal være lig med 2, uanset hvor mange hjørner der er i træet. Hver todelt graf er også et træ.
Kromatisk nummer
I ethvert træ er det kromatiske tal lig med 2.
java streng concat
Eksempler på træer:
Der er forskellige eksempler på et træ. Nogle af dem er beskrevet som følger:
Eksempel 1: I det følgende træ skal vi bestemme det kromatiske tal.
Løsning: Der er 2 forskellige farver til fire hjørner. Et træ med et hvilket som helst antal hjørner skal indeholde det kromatiske tal som 2 i ovenstående træ. Så,
Kromatisk tal = 2
Eksempel 2: I det følgende træ skal vi bestemme det kromatiske tal.
Løsning: Der er 2 forskellige farver til fem hjørner. Et træ med et hvilket som helst antal hjørner skal indeholde det kromatiske tal som 2 i ovenstående træ. Så,
Kromatisk tal = 2
Eksempler fra det virkelige liv på kromatisk tal
Antag, at Marry er leder i Xyz Company. Virksomheden ansætter nogle nye medarbejdere, og hun skal have et træningsprogram for de nye medarbejdere. Hun skal planlægge de tre møder, og hun forsøger at bruge de få tider så meget som muligt til møder. Hvis der er en medarbejder, der skal til to forskellige møder, så skal lederen bruge de forskellige tidsplaner for de møder. Antag, at vi ønsker at få en visuel repræsentation af dette møde.
Til den visuelle repræsentation bruger Marry prikken til at angive mødet. Hvis der er en medarbejder, der har to møder og kræver at deltage i begge møder, så vil begge møde blive forbundet ved hjælp af en kant. De forskellige tidsvinduer er repræsenteret ved hjælp af farver. Så lederen fylder prikkerne med disse farver på en sådan måde, at to prikker ikke indeholder den samme farve, der deler en kant. (Det betyder, at en medarbejder, der skal deltage i de to møder, ikke må have samme tid). Den visuelle repræsentation af dette er beskrevet som følger:
