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

דוגמא: הגרף המוצג באיור הוא גרף מישורי.

רשימת לטקס

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

אזור סופי: אם השטח של האזור סופי, אז האזור הזה נקרא אזור סופי.

אזור אינסופי: אם השטח של האזור הוא אינסופי, האזור הזה נקרא אזור אינסופי. לגרף מישור יש רק אזור אינסופי אחד.

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

פִּתָרוֹן: ישנם חמישה אזורים בגרף לעיל, כלומר r₁,ר₂,ר₃,ר₄,ר₅.

ישנם ארבעה אזורים סופיים בגרף, כלומר, r₂,ר₃,ר₄,ר₅.

יש רק אזור סופי אחד, כלומר, r₁

מאפיינים של גרפים מישוריים:

1. אם לגרף מישורי מחובר G יש קצוות e ואזורים r, אז r ≦ זה.
2. אם לגרף מישורי מחובר G יש קצוות e, v קודקודים ו-r אזורים, אז v-e+r=2.
3. אם לגרף מישורי מחובר G יש קצוות e וקודקודים v, אז 3v-e≧6.
4. גרף שלם K_נהוא מישורי אם ורק אם n<5.< li>
5. גרף דו-צדדי שלם K_מנהוא מישורי אם ורק אם m3.

דוגמא: הוכח כי גרף שלם K₄הוא מישורי.

פִּתָרוֹן: הגרף המלא K₄מכיל 4 קודקודים ו-6 קצוות.

אנו יודעים כי עבור גרף מישורי מחובר 3v-e≧6. מכאן עבור K₄, יש לנו 3x4-6=6 שמספק את הנכס (3).

כיצד למרכז תמונה ב-CSS

כך ק₄הוא גרף מישורי. מכאן הוכח.

גרף לא מישורי:

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

דוגמא: הגרפים המוצגים באיור הם גרפים לא מישוריים.

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

מאפיינים של גרפים לא מישוריים:

גרף אינו מישורי אם ורק אם הוא מכיל תת-גרף הומיאומורפי ל-K₅או ק_3.3

הצהרת מקרה של java

דוגמה1: הראה ש-K₅אינו מישורי.

פִּתָרוֹן: הגרף המלא K₅מכיל 5 קודקודים ו-10 קצוות.

כעת, עבור גרף מישורי מחובר 3v-e≧6.

לפיכך, עבור ק₅, יש לנו 3 x 5-10=5 (שלא עומד בתכונה 3 כי היא חייבת להיות גדולה או שווה ל-6).

לפיכך, ק₅הוא גרף לא מישורי.

דוגמה 2: הראה שהגרפים המוצגים באיור אינם מישוריים על ידי מציאת תת-גרף הומיאומורפי ל-K₅או ק_3.3.

פִּתָרוֹן: אם נסיר את הקצוות (V₁,IN₄),(IN₃,IN₄) ו (V₅,IN₄) הגרף G₁, הופך להומיאומורפי ל-K₅.לכן זה לא מישורי.

אם נסיר את הקצה V_2,V7) הגרף G₂הופך להומיאומורפי ל-K_3.3.מכאן שזה לא מישורי.

צביעת גרפים:

נניח ש-G= (V,E) הוא גרף ללא קצוות מרובים. צביעת קודקוד של G היא הקצאת צבעים לקודקודים של G כך שלקודקודים סמוכים יש צבעים שונים. גרף G הוא M-Colorable אם קיימת צביעה של G המשתמשת ב-M-Colors.

צביעה נכונה: צביעה מתאימה אם לכל שני קודקודים סמוכים u ו-v יש צבעים שונים, אחרת זה נקרא צביעה לא נכונה.

דוגמא: שקול את הגרף הבא ואת הצבע C={r, w, b, y}. צבע את הגרף כראוי באמצעות כל הצבעים או פחות צבעים.

הגרף המוצג באיור הוא מינימום 3-צבעוני, ומכאן x(G)=3

פִּתָרוֹן: איור מציג את הגרף בצבע כהלכה עם כל ארבעת הצבעים.

איור מציג את הגרף בצבע כהלכה עם שלושה צבעים.

מספר כרומטי של G: המספר המינימלי של צבעים הדרוש להפקת צביעה נכונה של גרף G נקרא המספר הכרומטי של G ומסומן ב-x(G).

סדר אקראי sql

דוגמא: המספר הכרומטי של K_נהוא נ.

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

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

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

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

ציין והוכח את משפט לחיצת היד.

משפט לחיצת יד: סכום המעלות של כל הקודקודים בגרף G שווה פי שניים ממספר הקצוות בגרף.

מבחינה מתמטית ניתן לומר זאת כך:

∑_v∈Vdeg(v)=2e

הוכחה: תן ל-G = (V, E) להיות גרף שבו V = {v₁,ב₂, . . . . . . . . . .} תהיה קבוצת הקודקודים ו-E = {e₁,זה₂. . . . . . . . . .} להיות קבוצת הקצוות. אנו יודעים שכל קצה נמצא בין שני קודקודים ולכן הוא מספק דרגה אחת לכל קודקוד. מכאן שכל קצה תורם תואר שני עבור הגרף. אז סכום המעלות של כל הקודקודים שווה פי שניים ממספר הקצוות ב-G.

לפיכך, ∑_v∈Vdeg(v)=2e

q3 חודשים