מעגל אוילר ונוסחת אוילר

מתוך Math-Wiki
גרסה מ־12:57, 30 ביוני 2019 מאת אריאל (שיחה | תרומות) (פתרון)

(הבדל) → הגרסה הקודמת | הגרסה האחרונה (הבדל) | הגרסה הבאה ← (הבדל)
קפיצה אל: ניווט, חיפוש

מעגל אוילר

תרגיל

יהי G=(V\cup U,E) גרף דו-צדדי. הוכיחו שאם |E| מס' אי-זוגי אז אין ב-G מעגל אוילר.

פתרון

נשים לב שבגרף דו צדדי מתקיים: \underset{v\in V}{\sum}\deg{v}=|E|=\underset{u\in U}{\sum}\deg{u}, וזאת כיון שכל קשת יוצאת מצד אחד ומגיעה לצד השני, ולכן אם נספור את דרגות הקודקודים באחד הצדדים נקבל כל קשת (כי כל אחת חייב לעבור באחד הקודקודים בצד זה) בדיוק פעם אחת (כי לא יכול להיות ששתי קצוות הקשת באותו צד של הגרף). קיבלנו שסך דרגות הקודקודים בכל צד הוא אי-זוגי, ולכן בכל צד קיים קודקוד עם דרגה אי-זוגית, ובפרט אין מעגל אוילר.

נוסחת אוילר

תרגיל

יהי G=(V,E) גרף מישורי. נסמן: v=|V|,e=|E| (וכן נסמן את מס' התחומים בציור המישורי ב-f). נניח v\geq 3. הוכיחו: e\leq 3(v-2).