Graafinen väritys
Graafisten värjäystä voidaan kuvata prosessina, jossa graafin huipuille määrätään värejä. Tässä samaa väriä ei tulisi käyttää kahden vierekkäisen kärjen täyttämiseen. Voimme kutsua kuvaajavärjäystä myös Vertex Coloring -värjäykseksi. Graafin värjäyksessä on huolehdittava siitä, että graafissa ei saa olla reunaa, jonka päätypisteet ovat värjätty samalla värillä. Tämän tyyppinen kaavio tunnetaan nimellä 'Oikein värillinen kaavio'.
Esimerkki graafin värjäyksestä
10 teho 6:sta
Tässä kaaviossa näytämme oikein väritetyn kaavion, joka on kuvattu seuraavasti:
Yllä oleva kaavio sisältää joitain kohtia, jotka kuvataan seuraavasti:
- Samaa väriä ei voi käyttää kahden vierekkäisen kärjen värjäämiseen.
- Siksi voimme kutsua sitä oikein väritetyksi kaavioksi.
Graafisen värityksen sovellukset
Graafisen värjäyksen sovelluksia on useita. Jotkut niiden tärkeistä sovelluksista kuvataan seuraavasti:
- Tehtävä
- Kartan väritys
- Tehtävien ajoittaminen
- Sudoku
- Valmistele aikataulu
- Konfliktien ratkaiseminen
Kromaattinen numero
Kromaattinen luku voidaan kuvata värien vähimmäismääräksi, joka tarvitaan minkä tahansa graafin värittämiseen oikein. Toisin sanoen kromaattista lukua voidaan kuvata värien vähimmäismääränä, joka tarvitaan minkä tahansa graafin värjäämiseen siten, että graafin kahdelle vierekkäiselle pisteelle ei anneta samaa väriä.
Esimerkki kromaattisesta numerosta:
Kromaattisen luvun ymmärtämiseksi tarkastelemme kuvaajaa, joka kuvataan seuraavasti:
Yllä oleva kaavio sisältää joitain kohtia, jotka kuvataan seuraavasti:
- Samaa väriä ei käytetä kahden vierekkäisen kärjen värittämiseen.
- Tämän kaavion värien vähimmäismäärä on 3, mikä tarvitaan pisteiden oikeaan värittämiseen.
- Tästä syystä tässä kaaviossa kromaattinen luku = 3
- Jos haluamme värittää tämän kaavion oikein, tässä tapauksessa vaaditaan vähintään 3 väriä.
Graafisten kromaattisten lukumäärän tyypit:
Graafeja on erityyppisiä kromaattisia lukumääriä, jotka kuvataan seuraavasti:
Kiertokaavio:
Graafi tunnetaan sykligraafina, jos se sisältää 'n' reunaa ja 'n' kärkeä (n >= 3), jotka muodostavat syklin, jonka pituus on 'n'. Kaikista syklin pisteistä voi olla vain 2 tai 3 astetta.
Kromaattinen numero:
- Jaksograafin kromaattinen luku on 2, jos graafin kärkien määrä on parillinen.
- Jaksograafin kromaattinen luku on 3, jos graafin kärkien lukumäärä on pariton.
Esimerkkejä syklikaaviosta:
Syklikaavioista on useita esimerkkejä. Jotkut niistä on kuvattu seuraavasti:
Esimerkki 1: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa syklikaaviossa kolmelle pisteelle on 3 eri väriä, eikä mikään vierekkäisistä pisteistä ole värjätty samalla värillä. Tässä kaaviossa pisteiden lukumäärä on pariton. Niin
Kromaattinen luku = 3
Esimerkki 2: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa syklikaaviossa on 2 väriä neljälle pisteelle, eikä mikään vierekkäisistä pisteistä ole värjätty samalla värillä. Tässä kaaviossa kärkien lukumäärä on parillinen. Niin
Kromaattinen luku = 2
Esimerkki 3: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa viidelle pisteelle on 4 eri väriä ja kaksi vierekkäistä kärkeä on värjätty samalla värillä (sininen). Joten tämä kaavio ei ole syklikaavio eikä sisällä kromaattista lukua.
Esimerkki 4: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa on 2 eri väriä kuudelle pisteelle, eikä mikään vierekkäisistä pisteistä ole värjätty samalla värillä. Tässä kaaviossa kärkien lukumäärä on parillinen. Niin
Kromaattinen luku = 2
Suunnittelukaavio
Kuvaaja tunnetaan suunnittelijakuvaajana, jos se piirretään tasoon. Suunnittelukaavion reunat eivät saa ylittää toisiaan.
Kromaattinen numero:
- Suunnittelukaaviossa kromaattisen luvun on oltava pienempi tai yhtä suuri kuin 4.
- Suunnittelijan kaavio voidaan näyttää myös kaikilla yllä olevilla syklikaavioilla paitsi esimerkkiä 3.
Esimerkkejä höyläkaaviosta:
Höyläkaavioista on useita esimerkkejä. Jotkut niistä on kuvattu seuraavasti:
Esimerkki 1: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa graafissa on kolme eri väriä kolmelle huipulle, eikä mikään tämän graafin reunoista ylitä toisiaan. Niin
"eulerin numero javassa"
Kromaattinen luku = 3
Tässä kromaattinen luku on pienempi kuin 4, joten tämä kuvaaja on tasograafi.
Esimerkki 2: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa on 2 eri väriä neljälle huipulle, eikä mikään tämän graafin reunoista ylitä toisiaan. Niin
Kromaattinen luku = 2
Tässä kromaattinen luku on pienempi kuin 4, joten tämä kuvaaja on tasograafi.
Esimerkki 3: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa on 5 eri väriä viidelle huipulle, eikä mikään tämän graafin reunoista ylitä toisiaan. Niin
Kromaattinen luku = 5
Tässä kromaattinen luku on suurempi kuin 4, joten tämä kuvaaja ei ole tasograafi.
Esimerkki 4: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa on 2 eri väriä kuudelle pisteelle, eikä yksikään tämän graafin reunoista ylitä toisiaan. Niin
Kromaattinen luku = 2
Tässä kromaattinen luku on pienempi kuin 4, joten tämä kuvaaja on tasograafi.
Täydellinen kaavio
Graafia kutsutaan täydelliseksi graafiksi, jos vain yhtä reunaa käytetään yhdistämään kaksi erillistä kärkeä. Täydellisen graafin jokainen kärkipiste on yhteydessä jokaiseen toiseen kärkeen. Tässä kaaviossa jokainen kärki on väritetty eri värillä. Tämä tarkoittaa, että koko graafissa kaksi kärkeä eivät sisällä samaa väriä.
c# koodiesimerkkejä
Kromaattinen numero
Täydellisessä graafissa kromaattinen luku on yhtä suuri kuin graafin kärkien lukumäärä.
Esimerkkejä täydellisestä kaaviosta:
Täydellisistä kaavioista on useita esimerkkejä. Jotkut niistä on kuvattu seuraavasti:
Esimerkki 1: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: On 4 eri väriä 4 eri huipulla, eikä mikään väreistä ole sama yllä olevassa kaaviossa. Määritelmän mukaan kromaattinen luku on pisteiden lukumäärä. Niin,
Kromaattinen luku = 4
Esimerkki 2: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Viidelle eri pisteelle on 5 eri väriä, eikä mikään väreistä ole sama yllä olevassa kaaviossa. Määritelmän mukaan kromaattinen luku on pisteiden lukumäärä. Niin,
Kromaattinen luku = 5
Esimerkki 3: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Neljälle eri pisteelle on 3 eri väriä, ja yksi väri toistuu kahdessa pisteessä yllä olevassa kaaviossa. Joten tämä kaavio ei ole täydellinen graafi, eikä se sisällä kromaattista lukua.
Kaksiosainen kaavio
Graafi tunnetaan kaksiosaisena graafina, jos se sisältää kaksi kärkijoukkoa, A ja B. A:n kärki voi liittyä vain B:n kärkien kanssa. Tämä tarkoittaa, että reunat eivät voi liittyä pisteitä joukon kanssa.
Kromaattinen numero
Missä tahansa kaksiosaisessa graafissa kromaattinen luku on aina yhtä suuri kuin 2.
Esimerkkejä kaksiosaisesta graafista:
Kaksiosaisista kaavioista on useita esimerkkejä. Jotkut niistä on kuvattu seuraavasti:
Esimerkki 1: Seuraavassa kaaviossa meidän on määritettävä kromaattinen luku.
Ratkaisu: Yllä olevassa kaaviossa on 2 erilaista kärkijoukkoa. Kaikkien kaksiosaisten graafien kromaattinen luku on siis aina 2. Joten
Kromaattinen luku = 2
Puu:
Yhdistetty graafi tunnetaan puuna, jos siinä ei ole piirejä. Puussa kromaattinen luku on 2 riippumatta siitä, kuinka monta kärkeä puussa on. Jokainen kaksiosainen graafi on myös puu.
Kromaattinen numero
Missä tahansa puussa kromaattinen luku on yhtä suuri kuin 2.
kuvan keskittäminen css:ssä
Esimerkkejä puusta:
Puusta on useita esimerkkejä. Jotkut niistä on kuvattu seuraavasti:
Esimerkki 1: Seuraavassa puussa meidän on määritettävä kromaattinen luku.
Ratkaisu: Neljää kärkeä varten on 2 eri väriä. Puun, jolla on mikä tahansa määrä pisteitä, tulee sisältää kromaattinen luku kuten 2 yllä olevassa puussa. Niin,
Kromaattinen luku = 2
Esimerkki 2: Seuraavassa puussa meidän on määritettävä kromaattinen luku.
Ratkaisu: Viidelle pisteelle on 2 eri väriä. Puun, jolla on mikä tahansa määrä pisteitä, tulee sisältää kromaattinen luku kuten 2 yllä olevassa puussa. Niin,
Kromaattinen luku = 2
Tosielämän esimerkki kromaattisesta numerosta
Oletetaan, että Marry on johtaja Xyz Companyssa. Yritys palkkaa uusia työntekijöitä, ja hänen on hankittava koulutusohjelma näille uusille työntekijöille. Hän joutuu ajoittamaan kolme tapaamista, ja hän yrittää käyttää muutaman aikavälin mahdollisimman paljon kokouksiin. Jos on työntekijä, jonka on oltava kahdessa eri kokouksessa, esimiehen on käytettävä eri aikatauluja näissä kokouksissa. Oletetaan, että haluamme saada visuaalisen esityksen tästä kokouksesta.
Visuaalisessa esityksessä Marry käyttää pistettä ilmaisemaan tapaamisen. Jos on työntekijä, jolla on kaksi kokousta ja joka vaatii liittymistä molempiin kokouksiin, molempien kokous yhdistetään reunan avulla. Eri aikavälit esitetään värien avulla. Joten johtaja täyttää pisteet näillä väreillä siten, että kaksi pistettä eivät sisällä samaa väriä, jolla on yhteinen reuna. (Tämä tarkoittaa, että työntekijällä, jonka on osallistuttava kahteen kokoukseen, ei saa olla samaa aikaväliä). Tämän visuaalinen esitys on kuvattu seuraavasti:
