שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2024

נתונים שני עצים

G_{1} = (V, E_{1})

G_{2} = (V, E_{2})

עם אותה קבוצת הקודקודים

V

. הוכיחו כי קיים

v \in V

כך ש-

de g_{G_{1}} v + de g_{G_{2}} v \leq 3

.

הבהרה:

de g_{G_{1}} v

מסמן את הדרגה של

v

בגרף

G_{1}

, ואילו

de g_{G_{2}} v

מסמן את הדרגה שלו בגרף

G_{2}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה העבריתמועד א2024סמסטר א

★★★★★

עציםגרפיםהוכחה

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

נסמן

∣ V ∣ = n

. בעץ עם

n

קודקודים יש

n - 1

צלעות.

נחשב את סכום הדרגות בשני הגרפים יחד:

v \in V \sum (de g_{G_{1}} v + de g_{G_{2}} v) = v \in V \sum de g_{G_{1}} v + v \in V \sum de g_{G_{2}} v = 2∣ E_{1} ∣ + 2∣ E_{2} ∣ = 2 (n - 1) + 2 (n - 1) = 4 (n - 1)

הממוצע של

de g_{G_{1}} v + de g_{G_{2}} v

על כל הקודקודים הוא:

\frac{4 ( n - 1 )}{n} = 4 - \frac{4}{n} < 4

לפי עקרון השובך, קיים קודקוד

v

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

de g_{G_{1}} v + de g_{G_{2}} v \leq 3

■

שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2024 - עצים