Graffärgning
Graffärgning kan beskrivas som en process för att tilldela färger till toppen av en graf. I detta bör inte samma färg användas för att fylla de två angränsande hörnen. Vi kan också kalla graffärgning som Vertex Coloring. Vid graffärgning måste vi se till att en graf inte får innehålla någon kant vars ändpunkt är färgad av samma färg. Denna typ av graf är känd som en korrekt färgad graf.
Exempel på graffärgning
python spara json till fil
I den här grafen visar vi den korrekt färgade grafen, som beskrivs enligt följande:
Grafen ovan innehåller några punkter, som beskrivs enligt följande:
- Samma färg kan inte användas för att färga de två angränsande hörnen.
- Därför kan vi kalla det som en korrekt färgad graf.
Tillämpningar av graffärgning
Det finns olika tillämpningar av graffärgning. Några av deras viktiga tillämpningar beskrivs enligt följande:
- Uppdrag
- Karta färgläggning
- Schemaläggning av uppgifterna
- Sudoku
- Förbered tidtabell
- Konfliktlösning
Kromatiskt nummer
Det kromatiska antalet kan beskrivas som det minsta antal färger som krävs för att färga en graf på rätt sätt. Med andra ord kan det kromatiska talet beskrivas som ett minsta antal färger som behövs för att färga en graf på ett sådant sätt att inga två närliggande hörn av en graf kommer att tilldelas samma färg.
Exempel på kromatiskt tal:
För att förstå det kromatiska numret kommer vi att överväga en graf som beskrivs på följande sätt:
Grafen ovan innehåller några punkter, som beskrivs enligt följande:
- Samma färg används inte för att färga de två angränsande hörnen.
- Det minsta antalet färger i denna graf är 3, vilket behövs för att färga hörnen korrekt.
- Därför, i denna graf, är det kromatiska talet = 3
- Om vi vill färga denna graf på rätt sätt, i det här fallet, krävs minst 3 färger.
Typer av kromatiskt antal grafer:
Det finns olika typer av kromatiska antal grafer, som beskrivs enligt följande:
Cykeldiagram:
En graf kommer att kallas en cykelgraf om den innehåller 'n' kanter och 'n' hörn (n >= 3), som bildar en cykel med längden 'n'. Det kan bara finnas 2 eller 3 antal grader av alla hörn i cykeldiagrammet.
Kromatiskt nummer:
- Det kromatiska talet i en cykelgraf blir 2 om antalet hörn i den grafen är jämnt.
- Det kromatiska talet i en cykelgraf blir 3 om antalet hörn i den grafen är udda.
Exempel på cykeldiagram:
Det finns olika exempel på cykeldiagram. Några av dem beskrivs på följande sätt:
Exempel 1: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I ovanstående cykeldiagram finns det 3 olika färger för tre hörn, och ingen av de intilliggande hörnen är färgade med samma färg. I den här grafen är antalet hörn udda. Så
Kromatiskt tal = 3
Exempel 2: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I ovanstående cykeldiagram finns det 2 färger för fyra hörn, och ingen av de intilliggande hörnen är färgade med samma färg. I denna graf är antalet hörn jämnt. Så
Kromatiskt tal = 2
Exempel 3: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I grafen ovan finns det 4 olika färger för fem hörn, och två intilliggande hörn är färgade med samma färg (blå). Så denna graf är inte en cykelgraf och innehåller inte ett kromatiskt tal.
Exempel 4: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I diagrammet ovan finns det två olika färger för sex hörn, och ingen av de intilliggande hörnen är färgade med samma färg. I denna graf är antalet hörn jämnt. Så
Kromatiskt tal = 2
Planerare graf
En graf kommer att kallas en planerargraf om den ritas i ett plan. Kanterna på planeringsdiagrammet får inte korsa varandra.
Kromatiskt nummer:
- I en planeringsgraf måste det kromatiska talet vara mindre än eller lika med 4.
- Planer-grafen kan också visas av alla ovanstående cykeldiagram utom exempel 3.
Exempel på hyveldiagram:
Det finns olika exempel på hyveldiagram. Några av dem beskrivs på följande sätt:
Exempel 1: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I grafen ovan finns det 3 olika färger för tre hörn, och ingen av kanterna på denna graf korsar varandra. Så
var är infogningsnyckeln på laptopens tangentbord
Kromatiskt tal = 3
Här är det kromatiska talet mindre än 4, så denna graf är en plan graf.
Exempel 2: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I grafen ovan finns det 2 olika färger för fyra hörn, och ingen av kanterna på denna graf korsar varandra. Så
Kromatiskt tal = 2
Här är det kromatiska talet mindre än 4, så denna graf är en plan graf.
Exempel 3: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I ovanstående graf finns det 5 olika färger för fem hörn, och ingen av kanterna på denna graf korsar varandra. Så
Kromatiskt tal = 5
Här är det kromatiska talet större än 4, så denna graf är inte en plan graf.
Exempel 4: I följande graf måste vi bestämma det kromatiska talet.
Lösning: I grafen ovan finns det två olika färger för sex hörn, och ingen av kanterna på denna graf korsar varandra. Så
Kromatiskt tal = 2
Här är det kromatiska talet mindre än 4, så denna graf är en plan graf.
Komplett graf
En graf kommer att kallas en komplett graf om endast en kant används för att sammanfoga varannan distinkta hörn. Varje vertex i en komplett graf är ansluten till varannan vertex. I denna graf kommer varje vertex att färgas med en annan färg. Det betyder att i hela grafen innehåller två hörn inte samma färg.
Kromatiskt nummer
I en komplett graf kommer det kromatiska talet att vara lika med antalet hörn i den grafen.
Exempel på komplett graf:
Det finns olika exempel på kompletta grafer. Några av dem beskrivs på följande sätt:
Exempel 1: I följande graf måste vi bestämma det kromatiska talet.
Lösning: Det finns 4 olika färger för 4 olika hörn, och ingen av färgerna är densamma i diagrammet ovan. Enligt definitionen är ett kromatiskt tal antalet hörn. Så,
Kromatiskt tal = 4
Exempel 2: I följande graf måste vi bestämma det kromatiska talet.
Lösning: Det finns 5 olika färger för 5 olika hörn, och ingen av färgerna är densamma i grafen ovan. Enligt definitionen är ett kromatiskt tal antalet hörn. Så,
Kromatiskt tal = 5
Exempel 3: I följande graf måste vi bestämma det kromatiska talet.
byta namn på katalogen linux
Lösning: Det finns 3 olika färger för 4 olika hörn, och en färg upprepas i två hörn i grafen ovan. Så denna graf är inte en komplett graf och innehåller inte ett kromatiskt tal.
Tvådelad graf
En graf kommer att kallas en tvådelad graf om den innehåller två uppsättningar av hörn, A och B. A:s hörn kan bara förenas med B:s hörn. Det betyder att kanterna inte kan sammanfoga hörnen med en uppsättning.
Kromatiskt nummer
I alla tvådelade grafer är det kromatiska talet alltid lika med 2.
Exempel på tvådelade grafer:
Det finns olika exempel på tvådelade grafer. Några av dem beskrivs på följande sätt:
Exempel 1: I följande graf måste vi bestämma det kromatiska talet.
Lösning: Det finns 2 olika uppsättningar av hörn i grafen ovan. Så det kromatiska antalet för alla tvådelade grafer kommer alltid att vara 2. Så
Kromatiskt tal = 2
Träd:
En ansluten graf kommer att kallas ett träd om det inte finns några kretsar i den grafen. I ett träd kommer det kromatiska talet att vara lika med 2 oavsett hur många hörn som finns i trädet. Varje tvådelad graf är också ett träd.
Kromatiskt nummer
I vilket träd som helst är det kromatiska talet lika med 2.
skådespelare ranbir kapoor ålder
Exempel på träd:
Det finns olika exempel på ett träd. Några av dem beskrivs på följande sätt:
Exempel 1: I följande träd måste vi bestämma det kromatiska talet.
Lösning: Det finns 2 olika färger för fyra hörn. Ett träd med valfritt antal hörn måste innehålla det kromatiska talet som 2 i ovanstående träd. Så,
Kromatiskt tal = 2
Exempel 2: I följande träd måste vi bestämma det kromatiska talet.
Lösning: Det finns 2 olika färger för fem hörn. Ett träd med valfritt antal hörn måste innehålla det kromatiska talet som 2 i ovanstående träd. Så,
Kromatiskt tal = 2
Verkligt exempel på kromatiskt tal
Anta att Marry är chef i Xyz Company. Företaget anställer några nya medarbetare, och hon måste få ett utbildningsschema för de nya anställda. Hon måste schemalägga de tre mötena, och hon försöker använda de få tiderna så mycket som möjligt för möten. Om det är en anställd som måste vara på två olika möten, så behöver chefen använda de olika tidsplanerna för dessa möten. Anta att vi vill få en visuell representation av detta möte.
För den visuella representationen använder Marry pricken för att indikera mötet. Om det finns en anställd som har två möten och kräver att gå med i båda mötena, så kommer båda mötet att kopplas ihop med hjälp av en kant. De olika tidsluckorna representeras med hjälp av färger. Så chefen fyller prickarna med dessa färger på ett sådant sätt att två prickar inte innehåller samma färg som delar en kant. (Det betyder att en anställd som behöver närvara vid de två mötena inte får ha samma tid). Den visuella representationen av detta beskrivs enligt följande:
