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

אריאל: /* פתרון */

2019-06-30T12:57:25Z

פתרון

→ הגרסה הקודמת		גרסה מ־12:57, 30 ביוני 2019
שורה 4:		שורה 4:

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

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

2019-06-30T12:56:46Z

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

דף חדש

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

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

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

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

אריאל: /* פתרון */

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

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