Grafiku krāsošana
Grafu krāsošanu var raksturot kā krāsu piešķiršanas procesu grafika virsotnēm. Šajā gadījumā vienu un to pašu krāsu nevajadzētu izmantot, lai aizpildītu divas blakus esošās virsotnes. Grafiku krāsošanu varam saukt arī par virsotņu krāsošanu. Grafu krāsošanā mums ir jārūpējas, lai grafā nebūtu nevienas malas, kuras gala virsotnes ir iekrāsotas vienā krāsā. Šis diagrammas veids ir pazīstams kā pareizi iekrāsots grafiks.
Grafika krāsošanas piemērs
kas ir java hashset
Šajā grafikā mēs parādām pareizi iekrāsotu grafiku, kas aprakstīts šādi:
Iepriekš minētajā grafikā ir daži punkti, kas aprakstīti šādi:
- To pašu krāsu nevar izmantot, lai krāsotu divas blakus esošās virsotnes.
- Tāpēc mēs to varam saukt par pareizi iekrāsotu grafiku.
Grafu krāsošanas pielietojumi
Ir dažādi grafiku krāsošanas pielietojumi. Daži no to svarīgajiem lietojumiem ir aprakstīti šādi:
- Piešķiršana
- Kartes krāsošana
- Uzdevumu plānošana
- Sudoku
- Sagatavojiet laika grafiku
- Konfliktu risināšana
Hromatiskais numurs
Hromatisko skaitli var raksturot kā minimālo krāsu skaitu, kas nepieciešams, lai pareizi nokrāsotu jebkuru grafiku. Citiem vārdiem sakot, hromatisko skaitli var raksturot kā minimālo krāsu skaitu, kas nepieciešams, lai krāsotu jebkuru grafiku tā, lai divām blakus esošajām grafika virsotnēm netiktu piešķirta viena krāsa.
Hromatiskā skaitļa piemērs:
Lai saprastu hromatisko skaitli, mēs apsvērsim grafiku, kas aprakstīts šādi:
Iepriekš minētajā grafikā ir daži punkti, kas aprakstīti šādi:
- Viena un tā pati krāsa netiek izmantota, lai krāsotu divas blakus esošās virsotnes.
- Minimālais šī grafika krāsu skaits ir 3, kas ir nepieciešams, lai pareizi nokrāsotu virsotnes.
- Tādējādi šajā diagrammā hromatiskais skaitlis = 3
- Ja mēs vēlamies pareizi nokrāsot šo grafiku, šajā gadījumā mums ir nepieciešamas vismaz 3 krāsas.
Grafiku hromatiskā skaita veidi:
Ir dažādi grafiku hromatiskā skaita veidi, kas aprakstīti šādi:
Cikla diagramma:
Grafu sauc par cikla grafiku, ja tajā ir “n” malas un “n” virsotnes (n >= 3), kas veido ciklu ar garumu “n”. Cikla diagrammā visām virsotnēm var būt tikai 2 vai 3 grādu skaits.
Hromatiskais numurs:
- Hromatiskais skaitlis cikla grafikā būs 2, ja virsotņu skaits šajā grafikā ir pāra.
- Hromatiskais skaitlis cikla grafikā būs 3, ja virsotņu skaits šajā grafikā ir nepāra.
Cikla diagrammas piemēri:
Ir dažādi ciklu grafiku piemēri. Daži no tiem ir aprakstīti šādi:
1. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā cikla grafikā trim virsotnēm ir 3 dažādas krāsas, un neviena no blakus esošajām virsotnēm nav iekrāsota ar tādu pašu krāsu. Šajā grafikā virsotņu skaits ir nepāra. Tātad
Hromātiskais skaitlis = 3
2. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā cikla grafikā četrām virsotnēm ir 2 krāsas, un neviena no blakus esošajām virsotnēm nav iekrāsota ar tādu pašu krāsu. Šajā grafikā virsotņu skaits ir pāra. Tātad
Hromātiskais skaitlis = 2
3. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā piecām virsotnēm ir 4 dažādas krāsas, un divas blakus esošās virsotnes ir iekrāsotas vienā krāsā (zilā). Tātad šis grafiks nav cikla grafiks un nesatur hromatisku skaitli.
4. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā sešām virsotnēm ir 2 dažādas krāsas, un neviena no blakus esošajām virsotnēm nav iekrāsota ar tādu pašu krāsu. Šajā grafikā virsotņu skaits ir pāra. Tātad
Hromātiskais skaitlis = 2
Plānotāja grafiks
Grafiku sauc par plānotāja grafiku, ja tas ir zīmēts plaknē. Plānotāja grafika malas nedrīkst šķērsot viena otru.
Hromatiskais numurs:
- Plānotāja diagrammā hromatiskajam skaitlim ir jābūt mazākam par 4 vai vienādam ar to.
- Plānotāja grafiku var parādīt arī ar visām iepriekš minētajām cikla diagrammām, izņemot 3. piemēru.
Planer diagrammas piemēri:
Ir dažādi ēveles grafiku piemēri. Daži no tiem ir aprakstīti šādi:
1. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā trim virsotnēm ir 3 dažādas krāsas, un neviena no šī grafika malām nešķērso viena otru. Tātad
ko nozīmē xd
Hromātiskais skaitlis = 3
Šeit hromatiskais skaitlis ir mazāks par 4, tāpēc šis grafiks ir plaknes grafiks.
2. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā četrām virsotnēm ir 2 dažādas krāsas, un neviena no šī grafika malām nešķērso viena otru. Tātad
Hromātiskais skaitlis = 2
Šeit hromatiskais skaitlis ir mazāks par 4, tāpēc šis grafiks ir plaknes grafiks.
3. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā piecām virsotnēm ir 5 dažādas krāsas, un neviena no šī grafika malām nešķērso viena otru. Tātad
Hromātiskais skaitlis = 5
Šeit hromatiskais skaitlis ir lielāks par 4, tāpēc šis grafiks nav plaknes grafiks.
4. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā sešām virsotnēm ir 2 dažādas krāsas, un neviena no šī grafika malām nešķērso viena otru. Tātad
Hromātiskais skaitlis = 2
Šeit hromatiskais skaitlis ir mazāks par 4, tāpēc šis grafiks ir plaknes grafiks.
Pabeigts grafiks
Grafu sauc par pilnīgu grafiku, ja katras divas atšķirīgās virsotnes savienošanai tiek izmantota tikai viena mala. Katra pilna grafa virsotne ir saistīta ar katru otro virsotni. Šajā diagrammā katra virsotne tiks iekrāsota ar citu krāsu. Tas nozīmē, ka pilnā grafikā divas virsotnes nesatur vienu un to pašu krāsu.
Hromatiskais numurs
Pilnā grafikā hromatiskais skaitlis būs vienāds ar virsotņu skaitu šajā grafikā.
Pilnas diagrammas piemēri:
Ir dažādi pilnu grafiku piemēri. Daži no tiem ir aprakstīti šādi:
1. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Ir 4 dažādas krāsas 4 dažādām virsotnēm, un neviena no krāsām nav vienāda iepriekš minētajā diagrammā. Saskaņā ar definīciju hromatiskais skaitlis ir virsotņu skaits. Tātad,
Hromātiskais skaitlis = 4
sarakstu kārtot java
2. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Ir 5 dažādas krāsas 5 dažādām virsotnēm, un neviena no krāsām nav vienāda iepriekš minētajā diagrammā. Saskaņā ar definīciju hromatiskais skaitlis ir virsotņu skaits. Tātad,
Hromātiskais skaitlis = 5
3. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Ir 3 dažādas krāsas 4 dažādām virsotnēm, un viena krāsa tiek atkārtota divās virsotnēs iepriekš minētajā grafikā. Tātad šis grafiks nav pilnīgs grafiks un nesatur hromatisku skaitli.
Divpusējs grafiks
Grafu sauc par divpusēju grafiku, ja tajā ir divas virsotņu kopas A un B. A virsotne var savienoties tikai ar B virsotnēm. Tas nozīmē, ka malas nevar savienot virsotnes ar kopu.
Hromatiskais numurs
Jebkurā divpusējā grafikā hromatiskais skaitlis vienmēr ir vienāds ar 2.
Divpusējās diagrammas piemēri:
Ir dažādi divpusējo grafiku piemēri. Daži no tiem ir aprakstīti šādi:
1. piemērs: Nākamajā grafikā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Iepriekš minētajā grafikā ir 2 dažādas virsotņu kopas. Tātad visu divpusējo grafiku hromatiskais skaitlis vienmēr būs 2. Tātad
Hromātiskais skaitlis = 2
Koks:
Savienots grafiks būs pazīstams kā koks, ja šajā grafikā nav ķēžu. Kokā hromatiskais skaitlis būs vienāds ar 2 neatkarīgi no tā, cik virsotņu ir kokā. Katrs divpusējs grafiks ir arī koks.
Hromatiskais numurs
Jebkurā kokā hromatiskais skaitlis ir vienāds ar 2.
kā darbojas dators
Koku piemēri:
Ir dažādi koka piemēri. Daži no tiem ir aprakstīti šādi:
1. piemērs: Nākamajā kokā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Četrām virsotnēm ir 2 dažādas krāsas. Kokam ar jebkuru virsotņu skaitu ir jāsatur hromatiskais skaitlis kā 2 iepriekš minētajā kokā. Tātad,
Hromātiskais skaitlis = 2
2. piemērs: Nākamajā kokā mums ir jānosaka hromatiskais skaitlis.
Risinājums: Piecām virsotnēm ir 2 dažādas krāsas. Kokam ar jebkuru virsotņu skaitu ir jāsatur hromatiskais skaitlis kā 2 iepriekš minētajā kokā. Tātad,
Hromātiskais skaitlis = 2
Hromatiskā skaitļa piemērs dzīvē
Pieņemsim, ka Marrijs ir uzņēmuma Xyz vadītājs. Uzņēmums pieņem darbā dažus jaunus darbiniekus, un viņai ir jāsagatavo apmācību grafiks šiem jaunajiem darbiniekiem. Viņai ir jāieplāno trīs tikšanās, un viņa cenšas sapulcēm izmantot pēc iespējas vairāk laika. Ja ir darbinieks, kuram ir jāpiedalās divās dažādās sanāksmēs, tad vadītājam šīm sanāksmēm ir jāizmanto dažādi laika grafiki. Pieņemsim, ka mēs vēlamies iegūt vizuālu šīs sanāksmes attēlojumu.
Vizuālajam attēlojumam Marry izmanto punktu, lai norādītu tikšanos. Ja ir darbinieks, kuram ir divas sapulces un ir jāpiedalās abās sanāksmēs, tad abas sapulces tiks savienotas ar malas palīdzību. Dažādas laika nišas tiek attēlotas ar krāsu palīdzību. Tātad vadītājs aizpilda punktus ar šīm krāsām tā, lai divi punkti nesatur vienu un to pašu krāsu, kurai ir kopīga mala. (Tas nozīmē, ka darbiniekam, kuram jāapmeklē abas sanāksmes, nedrīkst būt vienāds laika posms). Tā vizuālais attēlojums ir aprakstīts šādi:
