כדי להבין את המדרגה והחוצה של קודקוד, עלינו ללמוד תחילה על מושג המדרגה של קודקוד. לאחר מכן, נוכל להבין בקלות את המדרגה הפנימית והחוצה של קודקוד. עלינו לדעת כי ניתן לקבוע את התואר והחוצה רק בגרף המכוון. נוכל לחשב את מידת הקודקוד בעזרת גרף לא מכוון. בגרף הבלתי מכוון, איננו יכולים לחשב את המעלות והחוצה של קודקוד.
דרגת קודקוד
אם אנחנו רוצים למצוא את המידה של כל קודקוד בגרף, במקרה זה, עלינו לספור את מספר היחסים שנוצרים על ידי קודקוד מסוים עם הקודקוד השני. במילים אחרות, נוכל לקבוע את מידת הקודקוד בעזרת חישוב מספר הקצוות המתחברים לאותו קודקוד. דרגת קודקוד מסומנת בעזרת deg(v). אם יש גרף פשוט, המכיל n מספר קודקודים, במקרה זה, דרגת כל קודקוד תהיה:
Deg(v) = n-1 ∀ v ∈ G
לקודקוד יש את היכולת ליצור קצה עם כל שאר הקודקודים בגרף חוץ מעצמו. אז בגרף פשוט, מידת הקודקוד תגלה לפי מספר הקודקודים בגרף מינוס 1. כאן 1 משמש לקודקוד העצמי כי הוא לא עושה לולאה בעצמו. אם הגרף מכיל את הקודקודים שיש להם לולאה עצמית, אז סוג זה של גרף לא יהיה גרף פשוט.
דוגמא:
בדוגמה זו, יש לנו גרף בעל 6 קודקודים, כלומר, a, b, c, d, e ו-f. לקודקוד 'a' יש תואר 5, ולכל הקודקודים האחרים יש תואר 1. אם לקודקוד כלשהו יש תואר 1, אז סוג הקודקוד הזה ייקרא 'קודקוד הקצה'.
ישנם שני מקרים של גרפים בהם אנו יכולים לשקול את מידת הקודקוד, המתוארים כך:
- גרף לא מכוון
- גרף מכוון
כעת נלמד את מידת הקודקוד בגרף מכוון ואת מידת הקודקוד בגרף לא מכוון בפירוט.
דרגת קודקוד בגרף לא מכוון
אם יש גרף לא מכוון, אז בסוג זה של גרף, לא יהיה קצה מכוון. הדוגמאות לקביעת מידת הקודקוד בגרף לא מכוון מתוארות כדלקמן:
דוגמה 1: בדוגמה זו, נשקול גרף לא מכוון. כעת נגלה את המידה של כל קודקוד באותו גרף.
פִּתָרוֹן: בגרף הלא מכוון לעיל, ישנם בסך הכל 5 מספרים של קודקודים, כלומר, a, b, c, d ו-e. הדרגה של כל קודקוד מתוארת באופן הבא:
- הגרף שלמעלה מכיל 2 קצוות, הנפגשים בקודקוד 'a'. מכאן Deg(a) = 2
- גרף זה מכיל 3 קצוות, הנפגשים בקודקוד 'b'. מכאן Deg(b) = 3
- הגרף שלמעלה מכיל קצה אחד, הנפגש בקודקוד 'c'. מכאן Deg(c) = 1. הקודקוד c ידוע גם כקודקוד התלוי.
- הגרף שלמעלה מכיל 2 קצוות, הנפגשים בקודקוד 'd'. מכאן Deg(d) = 2.
- הגרף שלמעלה מכיל 0 קצוות, הנפגשים בקודקוד 'e'. מכאן Deg(a) = 0. ניתן לקרוא לקודקוד e גם הקודקוד המבודד.
דוגמה 2: בדוגמה זו, נשקול גרף לא מכוון. כעת נגלה את המידה של כל קודקוד באותו גרף.
פִּתָרוֹן: בגרף הבלתי מכוון לעיל, ישנם בסך הכל 5 מספרים של קודקודים, כלומר, a, b, c, d ו-e. הדרגה של כל קודקוד מתוארת באופן הבא:
דרגת קודקוד a = deg(a) = 2
דרגת קודקוד b = deg(b) = 2
דרגת הקודקוד c = deg(c) = 2
דרגת קודקוד d = deg(d) = 2
דרגת קודקוד e = deg(e) = 0
בגרף זה, אין קודקוד תלוי, וקודקוד 'e' הוא קודקוד מבודד.
דרגת קודקוד בגרף מכוון
אם הגרף הוא גרף מכוון, אז בגרף זה, כל קודקוד חייב להיות בעל תואר פנימה ומעלה החוצה. נניח שיש גרף מכוון. בגרף זה, נוכל להשתמש בשלבים הבאים כדי לגלות את המדרגה הפנימית, המדרגה החוצה והדרגה של קודקוד.
מערך מיון java
בדרגה של קודקוד
ניתן לתאר את המדרגה של קודקוד כמספר קצוות עם v, כאשר v משמש לציון הקודקוד הסופי. במילים אחרות, אנו יכולים לתאר אותו כמספר קצוות המגיעים לקודקוד. בעזרת תחביר deg-(v), נוכל לכתוב את המעלה של קודקוד. אם ברצוננו לקבוע את המעלה של קודקוד, לשם כך, עלינו לספור את מספר הקצוות שמסתיימים בקודקוד.
דרגת חוץ של קודקוד
ניתן לתאר את דרגת החוץ של קודקוד כמספר קצוות עם v, כאשר v משמש לציון הקודקוד הראשוני. במילים אחרות, אנו יכולים לתאר אותו כמספר קצוות היוצאים מהקודקוד. בעזרת תחביר deg+(v), נוכל לכתוב את דרגת החוץ של קודקוד. אם אנו רוצים לקבוע את דרגת החוץ של קודקוד, לשם כך, עלינו לספור את מספר הקצוות שמתחילים מהקודקוד.
דרגת קודקוד
דרגת קודקוד מסומנת בעזרת deg(v), השווה לתוספת של מעלה של קודקוד ומעלה של קודקוד. הייצוג הסמלי של דרגת קודקוד מתואר באופן הבא:
Deg(v) = deg-(v) + deg+(v)
דוגמה 1: בדוגמה זו, יש לנו גרף, ועלינו לקבוע את המידה של כל קודקוד.
פִּתָרוֹן: לשם כך נברר תחילה את מידת הקודקוד, בדרגת קודקוד ולאחר מכן את דרגת החוץ של קודקוד.
כפי שאנו יכולים לראות כי הגרף לעיל מכיל את סך 6 הקודקודים, כלומר, v1, v2, v3, v4, v5 ו-v6.
בתואר:
בדרגה של קודקוד v1 = deg(v1) = 1
בדרגה של קודקוד v2 = deg(v2) = 1
בדרגה של קודקוד v3 = deg(v3) = 1
בדרגה של קודקוד v4 = deg(v4) = 5
מה זה gb
בדרגה של קודקוד v5 = deg(v5) = 1
בדרגה של קודקוד v6 = deg(v6) = 0
תואר חוץ:
דרגת חוץ של קודקוד v1 = deg(v1) = 2
דרגת חוץ של קודקוד v2 = deg(v2) = 3
דרגת חוץ של קודקוד v3 = deg(v3) = 2
דרגת חוץ של קודקוד v4 = deg(v4) = 0
דרגת חוץ של קודקוד v5 = deg(v5) = 2
דרגת חוץ של קודקוד v6 = deg(v6) = 0
דרגת קודקוד
בעזרת ההגדרה שתוארה לעיל, אנו יודעים שמידת קודקוד Deg(v) = deg-(v) + אתה+(v). כעת נחשב אותו בעזרת הנוסחה הזו כך:
דרגת קודקוד v1 = deg(v1) = 1+2 = 3
דרגת קודקוד v2 = deg(v2) = 1+3 = 4
דרגת קודקוד v3 = deg(v3) = 1+2 = 3
דרגת קודקוד v4 = deg(v4) = 5+0 = 5
דרגת קודקוד v5 = deg(v5) = 1+2 = 3
דרגת קודקוד v6 = deg(v6) = 0+0 = 0
דוגמה 2:
בדוגמה זו, יש לנו גרף מכוון עם 7 קודקודים. הקודקוד 'a' מכיל 2 קצוות, כלומר 'ad' ו-'ab', היוצאים החוצה. לפיכך, קודקוד 'a' מכיל את המעלה החיצונית, שהיא 2. באופן דומה, לקודקוד 'a' יש גם קצה 'ga', שמגיע לקודקוד זה 'a'. לפיכך, הקודקוד 'a' מכיל את המעלה, שהיא 1.
פִּתָרוֹן: המדרגה הפנימית והחוצה של כל הקודקודים לעיל מתוארים כדלקמן:
בתואר:
בדרגה של קודקוד a = deg(a) = 1
הזמנה ב-sql לפי תאריך
בדרגה של קודקוד b = deg(b) = 2
בדרגה של קודקוד c = deg(c) = 2
בדרגה של קודקוד d = deg(d) = 1
בדרגה של קודקוד e = deg(e) = 1
בדרגה של קודקוד f = deg(f) = 1
בדרגה של קודקוד g = deg(g) = 0
תואר חוץ:
דרגת חוץ של קודקוד a = deg(a) = 2
דרגת חוץ של קודקוד b = deg(b) = 0
דרגת חוץ של קודקוד c = deg(c) = 1
דרגת חוץ של קודקוד d = deg(d) = 1
דרגת חוץ של קודקוד e = deg(e) = 1
דרגת חוץ של קודקוד f = deg(f) = 1
דרגת חוץ של קודקוד g = deg(g) = 2
דרגת כל קודקוד:
ידענו שדרגת קודקוד Deg(v) = deg-(v) + אתה+(v). כעת נחשב אותו בעזרת הנוסחה הזו כך:
דרגת קודקוד a = deg(a) = 1+2 = 3
דרגת קודקוד b = deg(b) = 2+0 = 2
דרגת קודקוד c = deg(c) = 2+1 = 3
דרגת קודקוד d = deg(d) = 1+1 = 2
דרגת קודקוד e = deg(e) = 1+1 = 2
דרגת קודקוד f = deg(f) = 1+1 = 2
דרגת קודקוד g = deg(g) = 0+2 = 2
דוגמה 3: בדוגמה זו, יש לנו גרף מכוון עם 5 קודקודים. הקודקוד 'a' מכיל קצה אחד, כלומר 'ae', אשר יוצאים החוצה. לפיכך, קודקוד 'a' מכיל מעלה חיצונית, שהיא 1. באופן דומה, לקודקוד 'a' יש גם קצה 'ba', שמגיע לקודקוד 'a' זה. לפיכך, הקודקוד 'a' מכיל את המעלה, שהיא 1.
פִּתָרוֹן: המדרגה הפנימית והחוצה של כל הקודקודים לעיל מתוארים כדלקמן:
בתואר
בדרגה של קודקוד a = deg(a) = 1
בדרגה של קודקוד b = deg(b) = 0
בדרגה של קודקוד c = deg(c) = 2
בדרגה של קודקוד d = deg(d) = 1
בדרגה של קודקוד e = deg(e) = 1
תואר חוץ:
דרגת חוץ של קודקוד a = deg(a) = 1
דרגת חוץ של קודקוד b = deg(b) = 2
דרגת חוץ של קודקוד c = deg(c) = 0
דרגת חוץ של קודקוד d = deg(d) = 1
דרגת חוץ של קודקוד e = deg(e) = 1
דרגת כל קודקוד:
ידענו שדרגת קודקוד Deg(v) = deg-(v) + אתה+(v). כעת נחשב אותו בעזרת הנוסחה הזו כך:
דרגת קודקוד a = deg(a) = 1+1 = 2
דרגת קודקוד b = deg(b) = 0+2 = 2
דרגת קודקוד c = deg(c) = 2+0 = 2
דרגת קודקוד d = deg(d) = 1+1 = 2
דרגת קודקוד e = deg(e) = 1+1 = 2
ג'אווה להפסקה
דוגמה 4: בדוגמה זו, יש לנו גרף, ועלינו לקבוע את התואר, התואר והמעלה של כל קודקוד.
פִּתָרוֹן: לשם כך נברר תחילה את דרגת פנימה של קודקוד ולאחר מכן את דרגת החוץ של קודקוד.
כפי שאנו יכולים לראות כי הגרף לעיל מכיל את סך 8 הקודקודים, כלומר 0, 1, 2, 3, 4, 5 ו-6.
בתואר:
בדרגה של קודקוד 0 = deg(0) = 1
בדרגה של קודקוד 1 = deg(1) = 2
בדרגה של קודקוד 2 = deg(2) = 2
בדרגה של קודקוד 3 = deg(3) = 2
בדרגה של קודקוד 4 = deg(4) = 2
מחרוזת של מערך c
בדרגה של קודקוד 5 = deg(5) = 2
בדרגה של קודקוד 6 = deg(6) = 2
תואר חוץ:
דרגת חוץ של קודקוד 0 = deg(0) = 2
דרגת חוץ של קודקוד 1 = deg(1) = 1
דרגת חוץ של קודקוד 2 = deg(2) = 3
דרגת חוץ של קודקוד 3 = deg(3) = 2
דרגת חוץ של קודקוד 4 = deg(4) = 2
דרגת חוץ של קודקוד 5 = deg(5) = 2
דרגת חוץ של קודקוד 6 = deg(6) = 1
דרגת כל קודקוד:
ידענו שדרגת קודקוד Deg(v) = deg-(v) + אתה+(v). כעת נחשב אותו בעזרת הנוסחה הזו כך:
דרגת קודקוד 0 = deg(0) = 1+2 = 3
דרגת קודקוד 1 = deg(1) = 2+1 = 3
דרגת קודקוד 2 = deg(2) = 2+3 = 5
דרגת קודקוד 3 = deg(3) = 2+2 = 4
דרגת קודקוד 4 = deg(4) = 2+2 = 4
דרגת קודקוד 5 = deg(5) = 2+2 = 4
דרגת קודקוד 6 = deg(5) = 2+1 = 3
רצף מעלות של גרף
כדי לקבוע את רצף המעלות של גרף, עלינו לקבוע תחילה את המידה של כל קודקוד בגרף. לאחר מכן, נכתוב את המעלות הללו בסדר עולה. ניתן לקרוא לסדר/רצף זה רצף מעלות של גרף.
לדוגמה: בדוגמה זו, יש לנו שלושה גרפים שיש להם 3, 4 ו-5 קודקודים, ורצף המעלות של כל הגרפים הוא 3.
בגרף למעלה יש 3 קודקודים. מידת הרצף של גרף זה מתוארת באופן הבא:
בגרף לעיל, ישנם 4 קודקודים. רצף המעלות של גרף זה מתואר כדלקמן:
בגרף לעיל, ישנם 5 קודקודים. רצף המעלות של גרף זה מתואר כדלקמן: