מעגל אוילר ונוסחת אוילר: הבדלים בין גרסאות בדף
(יצירת דף עם התוכן "==מעגל אוילר== ===תרגיל=== יהי <math>G=(V\cup U,E)</math> גרף דו-צדדי. הוכיחו שאם <math>|E|</math> מס' אי-זוגי אז א...") |
(←פתרון) |
||
| שורה 4: | שורה 4: | ||
====פתרון==== | ====פתרון==== | ||
נשים לב שבגרף דו צדדי מתקיים: <math>\underset{v\in V}{\sum | נשים לב שבגרף דו צדדי מתקיים: <math>\underset{v\in V}{\sum}\deg{v}=|E|=\underset{u\in U}{\sum}\deg{u}</math>, וזאת כיון שכל קשת יוצאת מצד אחד ומגיעה לצד השני, ולכן אם נספור את דרגות הקודקודים באחד הצדדים נקבל כל קשת (כי כל אחת חייב לעבור באחד הקודקודים בצד זה) בדיוק פעם אחת (כי לא יכול להיות ששתי קצוות הקשת באותו צד של הגרף). | ||
קיבלנו שסך דרגות הקודקודים בכל צד הוא אי-זוגי, ולכן בכל צד קיים קודקוד עם דרגה אי-זוגית, ובפרט אין מעגל אוילר. | קיבלנו שסך דרגות הקודקודים בכל צד הוא אי-זוגי, ולכן בכל צד קיים קודקוד עם דרגה אי-זוגית, ובפרט אין מעגל אוילר. | ||
גרסה אחרונה מ־12:57, 30 ביוני 2019
מעגל אוילר
תרגיל
יהי [math]\displaystyle{ G=(V\cup U,E) }[/math] גרף דו-צדדי. הוכיחו שאם [math]\displaystyle{ |E| }[/math] מס' אי-זוגי אז אין ב-[math]\displaystyle{ G }[/math] מעגל אוילר.
פתרון
נשים לב שבגרף דו צדדי מתקיים: [math]\displaystyle{ \underset{v\in V}{\sum}\deg{v}=|E|=\underset{u\in U}{\sum}\deg{u} }[/math], וזאת כיון שכל קשת יוצאת מצד אחד ומגיעה לצד השני, ולכן אם נספור את דרגות הקודקודים באחד הצדדים נקבל כל קשת (כי כל אחת חייב לעבור באחד הקודקודים בצד זה) בדיוק פעם אחת (כי לא יכול להיות ששתי קצוות הקשת באותו צד של הגרף). קיבלנו שסך דרגות הקודקודים בכל צד הוא אי-זוגי, ולכן בכל צד קיים קודקוד עם דרגה אי-זוגית, ובפרט אין מעגל אוילר.
נוסחת אוילר
תרגיל
יהי [math]\displaystyle{ G=(V,E) }[/math] גרף מישורי. נסמן: [math]\displaystyle{ v=|V|,e=|E| }[/math] (וכן נסמן את מס' התחומים בציור המישורי ב-[math]\displaystyle{ f }[/math]). נניח [math]\displaystyle{ v\geq 3 }[/math]. הוכיחו: [math]\displaystyle{ e\leq 3(v-2) }[/math].