88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11 - היסטוריית גרסאות

1593237070 ב־07:11, 19 באוגוסט 2019

2019-08-19T07:11:37Z

→ הגרסה הקודמת		גרסה מ־07:11, 19 באוגוסט 2019
שורה 159:		שורה 159:
	הוכיחו שקיים קודקוד בעל דרגה אי זוגית.		הוכיחו שקיים קודקוד בעל דרגה אי זוגית.

	פתרון: נסתכל על תת הגרף <math>V_1</math> אם <math>v_1</math> בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת ~~היחדים~~ שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. ~~כיון~~ שהקשת היחידה בין <math>V_1</math> ל <math>V_2</math> היא <math>(v_1,v_2)\in E</math> נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.		פתרון: נסתכל על תת הגרף <math>V_1</math> אם <math>v_1</math> בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת הידיים שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. כיוון שהקשת היחידה בין <math>V_1</math> ל <math>V_2</math> היא <math>(v_1,v_2)\in E</math> נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.

	==תרגיל==		==תרגיל==

Relweiz: /* תרגיל */

2019-08-15T13:03:44Z

תרגיל

→ הגרסה הקודמת		גרסה מ־13:03, 15 באוגוסט 2019
שורה 75:		שורה 75:

	==תרגיל==		==תרגיל==
	יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{\~~min~~}{v\~~in V~~}\{deg(V)\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>. הוכיחו:		יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{v\in V}{\min}\{deg(V)\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>. הוכיחו:

	א. יש בגרף מסלול פשוט מאורך לפחות <math>\delta_G</math>.		א. יש בגרף מסלול פשוט מאורך לפחות <math>\delta_G</math>.
שורה 85:		שורה 85:
	א. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. מתקיים: <math>\deg(v_1)\geq \delta_G</math>. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו <math>\delta_G</math>.		א. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. מתקיים: <math>\deg(v_1)\geq \delta_G</math>. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו <math>\delta_G</math>.

	ב.		ב. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל <math>v_1</math> ולקבל מעגל פשוט מהאורך המתאים.

	==תרגיל==		==תרגיל==

Relweiz: /* תרגיל */

2019-08-15T12:44:42Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:44, 15 באוגוסט 2019
שורה 73:		שורה 73:

	'''פתרון''': נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!		'''פתרון''': נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

			==תרגיל==
			יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{\min}{v\in V}\{deg(V)\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>. הוכיחו:

			א. יש בגרף מסלול פשוט מאורך לפחות <math>\delta_G</math>.

			ב. יש בגרף מעגל פשוט מאורך לפחות <math>\delta_G+1</math>.

			===פתרון===

			א. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. מתקיים: <math>\deg(v_1)\geq \delta_G</math>. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו <math>\delta_G</math>.

			ב.

	==תרגיל==		==תרגיל==

Relweiz: /* תרגיל */

2019-08-15T12:34:41Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:34, 15 באוגוסט 2019
שורה 142:		שורה 142:

	==תרגיל==		==תרגיל==
	יהא <math>G=(V,E)</math> גרף פשוט סופי לא מכוון. נניח כי <math>V=V_1\cup V_2</math> איחוד זר (כלומר החיתוך <math>V_1\cap V_2\emptyset</math>. עוד נניח כי קיים <math>v_i\in V_i</math> כך שקיימת קשת <math>(v_1,v_2)\in E</math> והיא הקשת היחידה בין <math>V_1</math> ל <math>V_2</math>.		יהא <math>G=(V,E)</math> גרף פשוט סופי לא מכוון. נניח כי <math>V=V_1\cup V_2</math> איחוד זר (כלומר החיתוך <math>V_1\cap V_2=\emptyset</math>. עוד נניח כי קיים <math>v_i\in V_i</math> כך שקיימת קשת <math>(v_1,v_2)\in E</math> והיא הקשת היחידה בין <math>V_1</math> ל <math>V_2</math>.

	הוכיחו שקיים קודקוד בעל דרגה אי זוגית.		הוכיחו שקיים קודקוד בעל דרגה אי זוגית.

Relweiz: /* תרגיל */

2019-08-15T12:33:08Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:33, 15 באוגוסט 2019
שורה 109:		שורה 109:
	'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n-1}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.		'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n-1}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.

	הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>\|\Gamma(v)\|,\|\Gamma(u)\|\geq \frac{n-1}{2}+1</math>, ולכן יש בגרף לפחות <math>n+1</math> קודקודים בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.		הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>\|\Gamma(v)\|,\|\Gamma(u)\|\geq \frac{n-1}{2}</math>, ולכן יש בגרף לפחות <math>\|\Gamma(v)\cup \Gamma(u)\cup \{v,u\}\|=2\cdot \frac{n-1}{2}+2=n+1</math> קודקודים (נובע מכך שהאיחוד זר) בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.

	==תרגיל==		==תרגיל==

אריאל: /* תרגיל */

2018-08-12T06:44:42Z

תרגיל

→ הגרסה הקודמת		גרסה מ־06:44, 12 באוגוסט 2018
שורה 107:		שורה 107:
	נניח כי הם שונים, אזי ב<math>\|[v]\|,\|[u]\|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.		נניח כי הם שונים, אזי ב<math>\|[v]\|,\|[u]\|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.

	'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.		'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n-1}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.

	הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>\|\Gamma(v)\|,\|\Gamma(u)\|\geq \frac{n}{2}+1</math>, ולכן יש בגרף לפחות <math>n+1</math> קודקודים ~~(צריך לקחת את הערך השלם של החצי)~~ בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.		הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>\|\Gamma(v)\|,\|\Gamma(u)\|\geq \frac{n-1}{2}+1</math>, ולכן יש בגרף לפחות <math>n+1</math> קודקודים בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.

	==תרגיל==		==תרגיל==

אריאל: /* תרגילים נוספים */

2018-08-12T05:33:09Z

תרגילים נוספים

→ הגרסה הקודמת		גרסה מ־05:33, 12 באוגוסט 2018
שורה 163:		שורה 163:
	נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math>		נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math>
	הוא בעל <math>\|V\| \leq\|E\|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.		הוא בעל <math>\|V\| \leq\|E\|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.

			==תרגיל==
			א. מהו הקוטר המקסימלי של גרף קשיר עם <math>n</math> קודקודים?

			ב. מהו המספר המינימלי של קשתות בגרף עם <math>n</math> קודקודים וקוטר 2?

			'''פתרון:'''

			א. <math>n-1</math>. לא יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר <math>n</math> קודקודים, ולכן לכל היותר <math>n-1</math> קשתות. גרף קו הוא עם קוטר <math>n-1</math> כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.

			ב. <math>n-1</math>. לא יכול להיות פחות כי אז הגרף לא יהיה קשיר וקטרו יהיה אינסוף ולא 2. גרף כוכב (יש קודקוד <math>u</math> המקיים <math>E=\{\{u,v\}:u\neq v\}</math> כלומר, הוא מחובר לכולם ואין עוד קשתות) הוא עם <math>n-1</math> קשתות וקוטר 2, כי המרחק בין שני קודקודים שאינם <math>u</math> הוא 2 (ואם אחד מהם הוא <math>u</math> אז 1).

אריאל: /* תרגיל */

2018-08-12T05:12:23Z

תרגיל

→ הגרסה הקודמת		גרסה מ־05:12, 12 באוגוסט 2018
שורה 109:		שורה 109:
	'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.		'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.

	הוכחה: ~~כנ"ל~~, ~~רק שבמקום להסתכל על מחלקת השקילות מסתכלים על~~ <math>\Gamma(v)</math>.		הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>\|\Gamma(v)\|,\|\Gamma(u)\|\geq \frac{n}{2}+1</math>, ולכן יש בגרף לפחות <math>n+1</math> קודקודים (צריך לקחת את הערך השלם של החצי) בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.

	==תרגיל==		==תרגיל==

אריאל: /* תרגיל */

2018-08-12T05:03:56Z

תרגיל

→ הגרסה הקודמת		גרסה מ־05:03, 12 באוגוסט 2018
שורה 106:		שורה 106:
	'''פתרון''': יהיו <math>v,u\in V</math>. צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).		'''פתרון''': יהיו <math>v,u\in V</math>. צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
	נניח כי הם שונים, אזי ב<math>\|[v]\|,\|[u]\|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.		נניח כי הם שונים, אזי ב<math>\|[v]\|,\|[u]\|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.

			'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>\|V\|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.

			הוכחה: כנ"ל, רק שבמקום להסתכל על מחלקת השקילות מסתכלים על <math>\Gamma(v)</math>.

	==תרגיל==		==תרגיל==

אריאל: /* תרגיל */

2018-08-12T04:56:14Z

תרגיל

→ הגרסה הקודמת		גרסה מ־04:56, 12 באוגוסט 2018
שורה 112:		שורה 112:
	'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).		'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).

	נמשיך באינדוקציה על <math>n</math>מספר הקדקודים בגרף.		נמשיך באינדוקציה על <math>n</math>, מספר הקדקודים בגרף.

	אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הן מדרגה קטנה שווה ל-1.		אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הן מדרגה קטנה שווה ל-1.