Grafiek kleuren
Grafiekkleuring kan worden omschreven als een proces waarbij kleuren worden toegewezen aan de hoekpunten van een grafiek. Hierbij mag niet dezelfde kleur worden gebruikt om de twee aangrenzende hoekpunten te vullen. We kunnen grafiekkleuring ook Vertex Coloring noemen. Bij het inkleuren van grafieken moeten we ervoor zorgen dat een grafiek geen randen bevat waarvan de eindhoekpunten met dezelfde kleur gekleurd zijn. Dit type grafiek staat bekend als de correct gekleurde grafiek.
Voorbeeld van grafiekkleuring
converteer een int naar string c++
In deze grafiek tonen we de correct gekleurde grafiek, die als volgt wordt beschreven:
In de bovenstaande grafiek zijn enkele punten opgenomen, die als volgt worden beschreven:
- Dezelfde kleur kan niet worden gebruikt om de twee aangrenzende hoekpunten te kleuren.
- Daarom kunnen we het een correct gekleurde grafiek noemen.
Toepassingen van grafiekkleuring
Er zijn verschillende toepassingen van grafiekkleuring. Enkele van hun belangrijke toepassingen worden als volgt beschreven:
- Opdracht
- Kaart kleuren
- Het plannen van de taken
- Sudoku
- Tijdschema voorbereiden
- Conflictoplossing
Chromatisch nummer
Het chromatische getal kan worden omschreven als het minimumaantal kleuren dat nodig is om een grafiek correct te kleuren. Met andere woorden, het chromatische getal kan worden omschreven als het minimumaantal kleuren dat nodig is om een grafiek zo te kleuren dat geen twee aangrenzende hoekpunten van een grafiek dezelfde kleur krijgen.
Voorbeeld van chromatisch nummer:
Om het chromatische getal te begrijpen, zullen we een grafiek beschouwen, die als volgt wordt beschreven:
In de bovenstaande grafiek zijn enkele punten opgenomen, die als volgt worden beschreven:
- Dezelfde kleur wordt niet gebruikt om de twee aangrenzende hoekpunten te kleuren.
- Het minimum aantal kleuren van deze grafiek is 3, wat nodig is om de hoekpunten goed te kleuren.
- Daarom is in deze grafiek het chromatische getal = 3
- Als we deze grafiek goed willen kleuren, hebben we in dit geval minimaal 3 kleuren nodig.
Soorten chromatisch aantal grafieken:
Er zijn verschillende soorten chromatische aantalgrafieken, die als volgt worden beschreven:
Cyclusgrafiek:
Een grafiek wordt een cyclusgrafiek genoemd als deze 'n' randen en 'n' hoekpunten (n >= 3) bevat, die een cyclus met lengte 'n' vormen. Er kunnen slechts 2 of 3 graden van alle hoekpunten in de cyclusgrafiek zijn.
Chromatisch nummer:
- Het chromatische getal in een cyclusgrafiek is 2 als het aantal hoekpunten in die grafiek even is.
- Het chromatische getal in een cyclusgrafiek is 3 als het aantal hoekpunten in die grafiek oneven is.
Voorbeelden van cyclusgrafieken:
Er zijn verschillende voorbeelden van cyclusgrafieken. Sommigen van hen worden als volgt beschreven:
Voorbeeld 1: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande cyclusgrafiek zijn er 3 verschillende kleuren voor drie hoekpunten, en geen van de aangrenzende hoekpunten is gekleurd met dezelfde kleur. In deze grafiek is het aantal hoekpunten oneven. Dus
Chromatisch getal = 3
Voorbeeld 2: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande cyclusgrafiek zijn er twee kleuren voor vier hoekpunten, en geen van de aangrenzende hoekpunten is gekleurd met dezelfde kleur. In deze grafiek is het aantal hoekpunten even. Dus
Chromatisch getal = 2
Voorbeeld 3: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er vier verschillende kleuren voor vijf hoekpunten, en twee aangrenzende hoekpunten zijn gekleurd met dezelfde kleur (blauw). Deze grafiek is dus geen cyclusgrafiek en bevat geen chromatisch getal.
Voorbeeld 4: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er twee verschillende kleuren voor zes hoekpunten, en geen van de aangrenzende hoekpunten is gekleurd met dezelfde kleur. In deze grafiek is het aantal hoekpunten even. Dus
Chromatisch getal = 2
Plannergrafiek
Een grafiek wordt een plannergrafiek genoemd als deze in een vlak is getekend. De randen van de plannergrafiek mogen elkaar niet kruisen.
Chromatisch nummer:
- In een plannergrafiek moet het chromatische getal kleiner dan of gelijk aan 4 zijn.
- De plannergrafiek kan ook worden weergegeven door alle bovenstaande cyclusgrafieken behalve voorbeeld 3.
Voorbeelden van Planer-grafieken:
Er zijn verschillende voorbeelden van planergrafieken. Sommigen van hen worden als volgt beschreven:
Voorbeeld 1: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er 3 verschillende kleuren voor drie hoekpunten, en geen van de randen van deze grafiek kruist elkaar. Dus
rujira banerjee
Chromatisch getal = 3
Hier is het chromatische getal kleiner dan 4, dus deze grafiek is een vlakke grafiek.
Voorbeeld 2: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er twee verschillende kleuren voor vier hoekpunten, en geen van de randen van deze grafiek kruist elkaar. Dus
Chromatisch getal = 2
Hier is het chromatische getal kleiner dan 4, dus deze grafiek is een vlakke grafiek.
Voorbeeld 3: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er vijf verschillende kleuren voor vijf hoekpunten, en geen van de randen van deze grafiek kruist elkaar. Dus
Chromatisch getal = 5
Hier is het chromatische getal groter dan 4, dus deze grafiek is geen vlakke grafiek.
Voorbeeld 4: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: In de bovenstaande grafiek zijn er twee verschillende kleuren voor zes hoekpunten, en geen van de randen van deze grafiek kruist elkaar. Dus
Chromatisch getal = 2
Hier is het chromatische getal kleiner dan 4, dus deze grafiek is een vlakke grafiek.
Volledige grafiek
Een grafiek wordt een volledige grafiek genoemd als er slechts één rand wordt gebruikt om elke twee afzonderlijke hoekpunten met elkaar te verbinden. Elk hoekpunt in een volledige grafiek is verbonden met elk ander hoekpunt. In deze grafiek wordt elk hoekpunt gekleurd met een andere kleur. Dat betekent dat in de volledige grafiek twee hoekpunten niet dezelfde kleur hebben.
Chromatisch nummer
In een volledige grafiek is het chromatische getal gelijk aan het aantal hoekpunten in die grafiek.
Voorbeelden van volledige grafiek:
Er zijn verschillende voorbeelden van volledige grafieken. Sommigen van hen worden als volgt beschreven:
Voorbeeld 1: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: Er zijn 4 verschillende kleuren voor 4 verschillende hoekpunten, en geen van de kleuren is hetzelfde in de bovenstaande grafiek. Volgens de definitie is een chromatisch getal het aantal hoekpunten. Dus,
Chromatisch getal = 4
Voorbeeld 2: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: Er zijn 5 verschillende kleuren voor 5 verschillende hoekpunten, en geen van de kleuren is hetzelfde in de bovenstaande grafiek. Volgens de definitie is een chromatisch getal het aantal hoekpunten. Dus,
Chromatisch getal = 5
Voorbeeld 3: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: Er zijn 3 verschillende kleuren voor 4 verschillende hoekpunten, en één kleur wordt herhaald in twee hoekpunten in de bovenstaande grafiek. Deze grafiek is dus geen volledige grafiek en bevat geen chromatisch getal.
Bipartiete grafiek
inclusief c-programmering
Een graaf wordt een bipartiete graaf genoemd als deze twee sets hoekpunten bevat, A en B. De hoekpunten van A kunnen alleen samenkomen met de hoekpunten van B. Dat betekent dat de randen de hoekpunten niet kunnen verbinden met een set.
Chromatisch nummer
In elke bipartiete grafiek is het chromatische getal altijd gelijk aan 2.
Voorbeelden van bipartiete grafiek:
Er zijn verschillende voorbeelden van bipartiete grafieken. Sommigen van hen worden als volgt beschreven:
Voorbeeld 1: In de volgende grafiek moeten we het chromatische getal bepalen.
Oplossing: Er zijn 2 verschillende sets hoekpunten in de bovenstaande grafiek. Het chromatische getal van alle bipartiete grafieken zal dus altijd 2 zijn. Dus
Chromatisch getal = 2
Boom:
Een verbonden grafiek wordt een boom genoemd als er geen circuits in die grafiek voorkomen. In een boom is het chromatische getal gelijk aan 2, ongeacht hoeveel hoekpunten er in de boom zijn. Elke bipartiete grafiek is ook een boom.
Chromatisch nummer
In elke boom is het chromatische getal gelijk aan 2.
inkapseling Java
Voorbeelden van boom:
Er zijn verschillende voorbeelden van een boom. Sommigen van hen worden als volgt beschreven:
Voorbeeld 1: In de volgende boom moeten we het chromatische getal bepalen.
Oplossing: Er zijn 2 verschillende kleuren voor vier hoekpunten. Een boom met een willekeurig aantal hoekpunten moet het chromatische getal 2 in de bovenstaande boom bevatten. Dus,
Chromatisch getal = 2
Voorbeeld 2: In de volgende boom moeten we het chromatische getal bepalen.
Oplossing: Er zijn 2 verschillende kleuren voor vijf hoekpunten. Een boom met een willekeurig aantal hoekpunten moet het chromatische getal 2 in de bovenstaande boom bevatten. Dus,
Chromatisch getal = 2
Voorbeeld uit de praktijk van chromatisch getal
Stel dat Marry een manager is bij Xyz Company. Het bedrijf neemt een aantal nieuwe medewerkers aan en ze moet een trainingsschema voor die nieuwe medewerkers opstellen. Ze moet de drie vergaderingen plannen en probeert de weinige tijdvakken zoveel mogelijk te gebruiken voor vergaderingen. Als er een medewerker bij twee verschillende vergaderingen aanwezig moet zijn, dan moet de manager voor die vergaderingen verschillende tijdschema's hanteren. Stel dat we een visuele weergave van deze bijeenkomst willen krijgen.
Voor de visuele weergave gebruikt Marry de stip om de ontmoeting aan te duiden. Als er een medewerker is die twee vergaderingen heeft en aan beide vergaderingen moet deelnemen, worden beide vergaderingen met elkaar verbonden met behulp van een edge. Met behulp van kleuren worden de verschillende tijdslots weergegeven. De manager vult de stippen dus zo met deze kleuren dat twee stippen niet dezelfde kleur bevatten die een rand deelt. (Dat betekent dat een medewerker die beide vergaderingen moet bijwonen, niet hetzelfde tijdslot mag hebben). De visuele weergave hiervan wordt als volgt omschreven:
