Grafiko dažymas

Grafiko spalvinimą galima apibūdinti kaip spalvų priskyrimo grafo viršūnėms procesą. Šiuo atveju ta pati spalva neturėtų būti naudojama dviem gretimoms viršūnėms užpildyti. Grafikų spalvinimą taip pat galime vadinti viršūnių dažymu. Dažydami grafą, turime pasirūpinti, kad grafe nebūtų briaunų, kurių galinės viršūnės būtų nuspalvintos ta pačia spalva. Šio tipo grafikas žinomas kaip tinkamai nuspalvintas grafikas.

Grafiko spalvinimo pavyzdys

fmovies Indija

Šiame grafike rodome tinkamai nuspalvintą grafiką, kuris apibūdinamas taip:

Aukščiau pateiktoje diagramoje yra keletas taškų, kurie aprašyti taip:

• Ta pati spalva negali būti naudojama dviem gretimoms viršūnėms nuspalvinti.
• Vadinasi, galime tai vadinti tinkamai nuspalvintu grafiku.

Grafinio spalvinimo taikymas

Yra įvairių grafikų spalvinimo pritaikymų. Kai kurios svarbios jų programos aprašytos taip:

• Užduotis
• Žemėlapio dažymas
• Užduočių planavimas
• Sudoku
• Paruoškite tvarkaraštį
• Konfliktų sprendimas

Chromatinis skaičius

Chromatinį skaičių galima apibūdinti kaip minimalų spalvų skaičių, reikalingą norint tinkamai nuspalvinti bet kurį grafiką. Kitaip tariant, chromatinį skaičių galima apibūdinti kaip minimalų spalvų skaičių, kurio reikia norint nuspalvinti bet kurį grafiką taip, kad jokiai dvi gretimos grafo viršūnės nebūtų priskirtos ta pačia spalva.

Chromatinio skaičiaus pavyzdys:

Norėdami suprasti chromatinį skaičių, apsvarstysime grafiką, kuris aprašytas taip:

Aukščiau pateiktoje diagramoje yra keletas taškų, kurie aprašyti taip:

• Ta pati spalva nenaudojama dviem gretimoms viršūnėms spalvinti.
• Minimalus šio grafiko spalvų skaičius yra 3, kurių reikia norint tinkamai nuspalvinti viršūnes.
• Taigi šiame grafike chromatinis skaičius = 3
• Jei norime tinkamai nuspalvinti šį grafiką, šiuo atveju mums reikia bent 3 spalvų.

Chromatinio grafikų skaičiaus tipai:

Yra įvairių tipų chromatinių grafikų, kurie apibūdinami taip:

Ciklo grafikas:

Grafas bus žinomas kaip ciklo grafikas, jei jame yra „n“ briaunų ir „n“ viršūnių (n >= 3), kurios sudaro „n“ ilgio ciklą. Visų ciklo grafiko viršūnių laipsnių skaičius gali būti tik 2 arba 3.

Chromatinis skaičius:

1. Chromatinis skaičius ciklo grafike bus 2, jei to grafo viršūnių skaičius yra lyginis.
2. Chromatinis skaičius ciklo grafike bus 3, jei to grafo viršūnių skaičius yra nelyginis.

Ciklo grafiko pavyzdžiai:

Yra įvairių ciklo grafikų pavyzdžių. Kai kurie iš jų aprašyti taip:

1 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame ciklo grafike yra 3 skirtingos spalvos trims viršūnėms ir nė viena iš gretimų viršūnių nėra nuspalvinta ta pačia spalva. Šiame grafike viršūnių skaičius yra nelyginis. Taigi

Chromatinis skaičius = 3

2 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame ciklo grafike yra 2 spalvos keturioms viršūnėms ir nė viena iš gretimų viršūnių nėra nuspalvinta ta pačia spalva. Šiame grafike viršūnių skaičius yra lyginis. Taigi

Chromatinis skaičius = 2

3 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike penkioms viršūnėms yra 4 skirtingos spalvos, o dvi gretimos viršūnės yra nuspalvintos ta pačia spalva (mėlyna). Taigi šis grafikas nėra ciklo grafikas ir jame nėra chromatinio skaičiaus.

4 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike šešioms viršūnėms yra 2 skirtingos spalvos ir nė viena iš gretimų viršūnių nėra nuspalvinta ta pačia spalva. Šiame grafike viršūnių skaičius yra lyginis. Taigi

Chromatinis skaičius = 2

Planavimo grafikas

Grafas bus žinomas kaip planuotojo grafikas, jei jis nubraižytas plokštumoje. Planavimo grafiko kraštai neturi kirsti vienas kito.

Chromatinis skaičius:

1. Planavimo schemoje chromatinis skaičius turi būti mažesnis arba lygus 4.
2. Planuotojo grafiką taip pat galima parodyti visomis aukščiau pateiktomis ciklo diagramomis, išskyrus 3 pavyzdį.

Planer grafiko pavyzdžiai:

Yra įvairių obliavimo grafikų pavyzdžių. Kai kurie iš jų aprašyti taip:

1 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike yra 3 skirtingos spalvos trims viršūnėms ir nė viena šio grafo briauna nekerta viena kitos. Taigi

į styginių metodą java

Chromatinis skaičius = 3

Čia chromatinis skaičius yra mažesnis nei 4, todėl šis grafikas yra plokštuminis grafikas.

2 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike keturioms viršūnėms yra 2 skirtingos spalvos ir nė viena šio grafo briauna nekerta viena kitos. Taigi

Chromatinis skaičius = 2

Čia chromatinis skaičius yra mažesnis nei 4, todėl šis grafikas yra plokštuminis grafikas.

3 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike penkioms viršūnėms yra 5 skirtingos spalvos ir nė viena šio grafo briauna nekerta viena kitos. Taigi

Chromatinis skaičius = 5

Čia chromatinis skaičius yra didesnis nei 4, todėl šis grafikas nėra plokštuminis grafikas.

4 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike šešioms viršūnėms yra 2 skirtingos spalvos ir nė viena šio grafo briauna nekerta viena kitos. Taigi

Chromatinis skaičius = 2

Čia chromatinis skaičius yra mažesnis nei 4, todėl šis grafikas yra plokštuminis grafikas.

Pilnas grafikas

Grafas bus žinomas kaip pilnas grafikas, jei kiekvienai dviem skirtingoms viršūnėms sujungti naudojama tik viena briauna. Kiekviena viso grafo viršūnė yra sujungta su kiekviena kita viršūne. Šiame grafike kiekviena viršūnė bus nuspalvinta skirtinga spalva. Tai reiškia, kad visame grafike dvi viršūnės neturi tos pačios spalvos.

Chromatinis skaičius

Visame grafe chromatinis skaičius bus lygus to grafiko viršūnių skaičiui.

ketvirčius per metus

Viso grafiko pavyzdžiai:

Yra įvairių pilnų grafikų pavyzdžių. Kai kurie iš jų aprašyti taip:

1 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Yra 4 skirtingos spalvos, skirtos 4 skirtingoms viršūnėms, ir nė viena spalva nėra tokia pati aukščiau pateiktame grafike. Pagal apibrėžimą chromatinis skaičius yra viršūnių skaičius. Taigi,

Chromatinis skaičius = 4

2 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Yra 5 skirtingos spalvos, skirtos 5 skirtingoms viršūnėms, ir nė viena spalva nėra tokia pati aukščiau pateiktame grafike. Pagal apibrėžimą chromatinis skaičius yra viršūnių skaičius. Taigi,

Chromatinis skaičius = 5

3 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Yra 3 skirtingos spalvos 4 skirtingoms viršūnėms, o viena spalva pasikartoja dviejose aukščiau pateikto grafiko viršūnėse. Taigi šis grafikas nėra pilnas grafikas ir jame nėra chromatinio skaičiaus.

Dvišalis grafikas

Grafas bus žinomas kaip dvišalis grafikas, jei jame yra du viršūnių rinkiniai A ir B. A viršūnė gali susijungti tik su B viršūnėmis. Tai reiškia, kad briaunos negali sujungti viršūnių su aibe.

Chromatinis skaičius

Bet kuriame dvišaliame grafe chromatinis skaičius visada yra lygus 2.

Dvišalio grafiko pavyzdžiai:

Yra įvairių dvišalių grafikų pavyzdžių. Kai kurie iš jų aprašyti taip:

1 pavyzdys: Toliau pateiktame grafike turime nustatyti chromatinį skaičių.

Sprendimas: Aukščiau pateiktame grafike yra 2 skirtingi viršūnių rinkiniai. Taigi visų dvišalių grafų chromatinis skaičius visada bus 2. Taigi

Chromatinis skaičius = 2

Medis:

Sujungtas grafikas bus žinomas kaip medis, jei tame grafike nėra grandinių. Medyje chromatinis skaičius bus lygus 2, nesvarbu, kiek viršūnių yra medyje. Kiekvienas dvišalis grafikas taip pat yra medis.

Chromatinis skaičius

Bet kuriame medyje chromatinis skaičius yra lygus 2.

25 c iki k

Medžių pavyzdžiai:

Yra įvairių medžio pavyzdžių. Kai kurie iš jų aprašyti taip:

1 pavyzdys: Šiame medyje turime nustatyti chromatinį skaičių.

Sprendimas: Yra 2 skirtingos spalvos keturioms viršūnėms. Medis su bet kokiu viršūnių skaičiumi turi turėti chromatinį skaičių kaip 2 aukščiau esančiame medyje. Taigi,

Chromatinis skaičius = 2

2 pavyzdys: Šiame medyje turime nustatyti chromatinį skaičių.

Sprendimas: Yra 2 skirtingos spalvos penkioms viršūnėms. Medis su bet kokiu viršūnių skaičiumi turi turėti chromatinį skaičių kaip 2 aukščiau esančiame medyje. Taigi,

Chromatinis skaičius = 2

Realus chromatinio skaičiaus pavyzdys

Tarkime, Marry yra įmonės „Xyz“ vadovas. Įmonė samdo keletą naujų darbuotojų ir ji turi sudaryti šių naujų darbuotojų mokymo grafiką. Ji turi suplanuoti tris susitikimus ir stengiasi kuo daugiau išnaudoti keletą laiko tarpsnių susitikimams. Jei yra darbuotojas, kuris turi dalyvauti dviejuose skirtinguose susitikimuose, vadovas turi naudoti skirtingus šių susitikimų grafikus. Tarkime, kad norime gauti vaizdinį šio susitikimo vaizdą.

Vizualiniam vaizdui Marry naudoja tašką, nurodydama susitikimą. Jei yra darbuotojas, turintis du susitikimus ir reikalaujantis prisijungti prie abiejų susirinkimų, abu susitikimai bus sujungti briaunos pagalba. Įvairūs laiko tarpsniai pavaizduoti spalvų pagalba. Taigi valdytojas užpildo taškus šiomis spalvomis taip, kad dviejuose taškuose nebūtų tos pačios spalvos, kuri turi bendrą kraštą. (Tai reiškia, kad darbuotojas, kuris turi dalyvauti dviejuose susitikimuose, neturi turėti tą patį laiko tarpą). Vizualus jo vaizdas aprašomas taip: