TechCodeview

צביעת גרפים

ניתן לתאר צביעת גרפים כתהליך של הקצאת צבעים לקודקודים של גרף. במקרה זה, אין להשתמש באותו צבע למילוי שני הקודקודים הסמוכים. אנחנו יכולים גם לקרוא לצביעת גרפים בתור צביעת קודקוד. בצביעת גרפים, עלינו לדאוג שגרף לא יכיל אף קצה שקודקודי הקצה שלו נצבעים באותו צבע. סוג זה של גרף ידוע בשם הגרף בצבע נכון.

דוגמה לצביעת גרפים

הדרכה של react js

בגרף זה, אנו מציגים את הגרף הצבעוני הנכון, המתואר כדלקמן:

הגרף לעיל מכיל כמה נקודות, המתוארות כדלקמן:

• לא ניתן להשתמש באותו צבע כדי לצבוע את שני הקודקודים הסמוכים.
• לפיכך, אנו יכולים לקרוא לזה כגרף בצבע כהלכה.

יישומים של צביעת גרפים

ישנם יישומים שונים של צביעת גרפים. כמה מהיישומים החשובים שלהם מתוארים כדלקמן:

• מְשִׁימָה
• צביעת מפה
• תזמון המשימות
• סודוקו
• הכן לוח זמנים
• פתרון סכסוכים

מספר כרומטי

ניתן לתאר את המספר הכרומטי כמספר המינימלי של צבעים הנדרש כדי לצבוע כראוי כל גרף. במילים אחרות, ניתן לתאר את המספר הכרומטי כמספר מינימלי של צבעים הדרושים כדי לצבוע כל גרף בצורה כזו שאף שני קודקודים סמוכים של גרף לא יקבלו אותו צבע.

דוגמה למספר כרומטי:

כדי להבין את המספר הכרומטי, נשקול גרף, המתואר כך:

הגרף לעיל מכיל כמה נקודות, המתוארות כדלקמן:

• אותו צבע אינו משמש לצביעת שני הקודקודים הסמוכים.
• המספר המינימלי של צבעים של גרף זה הוא 3, אשר יש צורך לצבוע נכון את הקודקודים.
• לפיכך, בגרף זה, המספר הכרומטי = 3
• אם ברצוננו לצבוע נכון את הגרף הזה, במקרה זה, נדרשים לנו לפחות 3 צבעים.

סוגי מספר גרפים כרומטי:

ישנם סוגים שונים של מספר כרומטי של גרפים, המתוארים כדלקמן:

גרף מחזור:

גרף יהיה ידוע בתור גרף מחזור אם הוא מכיל 'n' קצוות ו-'n' קודקודים (n >= 3), היוצרים מחזור באורך 'n'. יכולים להיות רק 2 או 3 מספר מעלות מכל הקודקודים בגרף המחזור.

מספר כרומטי:

1. המספר הכרומטי בגרף מחזורי יהיה 2 אם מספר הקודקודים בגרף זה זוגי.
2. המספר הכרומטי בגרף מחזורי יהיה 3 אם מספר הקודקודים בגרף זה הוא אי זוגי.

דוגמאות לגרף מחזור:

ישנן דוגמאות שונות של גרפי מחזור. כמה מהם מתוארים כך:

דוגמה 1: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף המחזור שלמעלה, ישנם 3 צבעים שונים עבור שלושה קודקודים, ואף אחד מהקודקודים הסמוכים לא צבוע באותו צבע. בגרף זה, מספר הקודקודים הוא אי זוגי. כך

מספר כרומטי = 3

דוגמה 2: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף המחזור שלמעלה, ישנם 2 צבעים לארבעה קודקודים, ואף אחד מהקודקודים הסמוכים לא צבוע באותו צבע. בגרף זה, מספר הקודקודים הוא זוגי. כך

מספר כרומטי = 2

דוגמה 3: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 4 צבעים שונים עבור חמישה קודקודים, ושני קודקודים סמוכים נצבעים באותו צבע (כחול). אז הגרף הזה אינו גרף מחזורי ואינו מכיל מספר כרומטי.

דוגמה 4: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 2 צבעים שונים עבור שישה קודקודים, ואף אחד מהקודקודים הסמוכים לא צבוע באותו צבע. בגרף זה, מספר הקודקודים הוא זוגי. כך

מספר כרומטי = 2

גרף מתכנן

גרף יהיה ידוע בתור גרף מתכנן אם הוא מצויר במישור. הקצוות של גרף המתכנן לא צריכים לחצות זה את זה.

מספר כרומטי:

1. בגרף מתכנן, המספר הכרומטי חייב להיות קטן או שווה ל-4.
2. ניתן להציג את גרף המתכנן גם על ידי כל גרפי המחזור שלעיל למעט דוגמה 3.

דוגמאות לגרף פלנר:

ישנן דוגמאות שונות של גרפים פלנריים. כמה מהם מתוארים כך:

דוגמה 1: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 3 צבעים שונים עבור שלושה קודקודים, ואף אחד מהקצוות של הגרף הזה לא חוצה זה את זה. כך

כיצד להשבית את מצב מפתח באנדרואיד

מספר כרומטי = 3

כאן, המספר הכרומטי קטן מ-4, כך שהגרף הזה הוא גרף מישור.

דוגמה 2: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 2 צבעים שונים עבור ארבעה קודקודים, ואף אחד מהקצוות של הגרף הזה לא חוצה זה את זה. כך

מספר כרומטי = 2

כאן, המספר הכרומטי קטן מ-4, כך שהגרף הזה הוא גרף מישור.

דוגמה 3: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 5 צבעים שונים עבור חמישה קודקודים, ואף אחד מהקצוות של הגרף הזה לא חוצה זה את זה. כך

מספר כרומטי = 5

כאן, המספר הכרומטי גדול מ-4, כך שהגרף הזה אינו גרף מישור.

דוגמה 4: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: בגרף לעיל, ישנם 2 צבעים שונים לשישה קודקודים, ואף אחד מהקצוות של הגרף הזה לא חוצה זה את זה. כך

מספר כרומטי = 2

כאן, המספר הכרומטי קטן מ-4, כך שהגרף הזה הוא גרף מישור.

גרף שלם

גרף יהיה ידוע בתור גרף שלם אם רק קצה אחד משמש לחיבור כל שני קודקודים נפרדים. כל קודקוד בגרף שלם קשור לכל קודקוד אחר. בגרף זה, כל קודקוד יצבע בצבע אחר. כלומר בגרף המלא, שני קודקודים אינם מכילים את אותו צבע.

מספר כרומטי

בגרף שלם, המספר הכרומטי יהיה שווה למספר הקודקודים באותו גרף.

דוגמאות לגרף שלם:

ישנן דוגמאות שונות של גרפים שלמים. כמה מהם מתוארים כך:

דוגמה 1: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

ב-java regex

פִּתָרוֹן: ישנם 4 צבעים שונים עבור 4 קודקודים שונים, ואף אחד מהצבעים אינו זהה בגרף לעיל. על פי ההגדרה, מספר כרומטי הוא מספר הקודקודים. כך,

מספר כרומטי = 4

דוגמה 2: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: ישנם 5 צבעים שונים עבור 5 קודקודים שונים, ואף אחד מהצבעים אינו זהה בגרף לעיל. על פי ההגדרה, מספר כרומטי הוא מספר הקודקודים. כך,

מספר כרומטי = 5

דוגמה 3: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: ישנם 3 צבעים שונים עבור 4 קודקודים שונים, וצבע אחד חוזר בשני קודקודים בגרף לעיל. אז הגרף הזה אינו גרף שלם ואינו מכיל מספר כרומטי.

גרף דו-צדדי

גרף יהיה ידוע בתור גרף דו-חלקי אם הוא מכיל שתי קבוצות של קודקודים, A ו-B. הקודקוד של A יכול להצטרף רק עם הקודקודים של B. כלומר, הקצוות לא יכולים להצטרף לקודקודים עם קבוצה.

מספר כרומטי

בכל גרף דו-חלקי, המספר הכרומטי תמיד שווה ל-2.

דוגמאות לגרף דו-צדדי:

ישנן דוגמאות שונות של גרפים דו-צדדיים. כמה מהם מתוארים כך:

דוגמה 1: בגרף הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: ישנן 2 קבוצות שונות של קודקודים בגרף לעיל. אז המספר הכרומטי של כל הגרפים הדו-חלקיים תמיד יהיה 2. אז

מספר כרומטי = 2

עֵץ:

גרף מחובר ייקרא עץ אם אין מעגלים בגרף זה. בעץ, המספר הכרומטי יהיה שווה ל-2 לא משנה כמה קודקודים יש בעץ. כל גרף דו-צדדי הוא גם עץ.

מספר כרומטי

בכל עץ, המספר הכרומטי שווה ל-2.

סוגי הצטרפות ב-rdbms

דוגמאות לעץ:

ישנן דוגמאות שונות לעץ. כמה מהם מתוארים כך:

דוגמה 1: בעץ הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: ישנם 2 צבעים שונים עבור ארבעה קודקודים. עץ עם כל מספר של קודקודים חייב להכיל את המספר הכרומטי כמו 2 בעץ שלמעלה. כך,

מספר כרומטי = 2

דוגמה 2: בעץ הבא, עלינו לקבוע את המספר הכרומטי.

פִּתָרוֹן: ישנם 2 צבעים שונים עבור חמישה קודקודים. עץ עם כל מספר של קודקודים חייב להכיל את המספר הכרומטי כמו 2 בעץ שלמעלה. כך,

מספר כרומטי = 2

דוגמה אמיתית למספר כרומטי

נניח שמרי היא מנהלת בחברת Xyz. החברה שוכרת כמה עובדים חדשים, והיא צריכה לקבל לוח הכשרה עבור אותם עובדים חדשים. היא צריכה לקבוע את שלוש הפגישות, והיא מנסה לנצל את משבצות הזמן המועטות ככל האפשר לפגישות. אם יש עובד שצריך להיות בשתי פגישות שונות, אז המנהל צריך להשתמש בלוחות הזמנים השונים לאותן פגישות. נניח שאנו רוצים לקבל ייצוג חזותי של הפגישה הזו.

עבור הייצוג החזותי, Marry משתמשת בנקודה כדי לציין את הפגישה. אם יש עובד שיש לו שתי פגישות ודורש להצטרף לשתי הישיבות, אז שתיהן הפגישה תתחבר בעזרת קצה. משבצות הזמן השונות מיוצגות בעזרת צבעים. אז המנהל ממלא את הנקודות בצבעים האלה בצורה כזו ששתי נקודות לא מכילות את אותו צבע שחולק קצה. (כלומר שלעובד שצריך להשתתף בשתי הפגישות אסור שיהיה לו אותה משבצת זמן). הייצוג החזותי של זה מתואר באופן הבא: