Math-Wiki - תרומות המשתמש [he]

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-09-01T18:56:01Z

Mike: /* יהיו תשובות לשאלות מהמבחנים בלינארית ובדידה? */

{{הוראות דף שיחה}}

=כללים=
* לפני ששואלים שאלה, בדקו האם משהו כבר שאל שאלה דומה.
* מאד מומלץ לנסח את השאלות תוך שימוש ב[[עזרה:תפריט ראשי#כתיבה מתמטית|כתיבה מתמטית]] - כך השאלה תהיה ברורה יותר.
* בסוף כל שאלה, עליכם לחתום את שם המשתמש שלכם, כלומר לרשום ארבעה סימני טילדה: ~.

=שאלות=

== תרגיל 2 שאלה 5 ==

בשאלה 5, ע"פ התכונות בהחלט ניתן לראות כי <math>A\setminus B</math> שייך ל-<math>X</math>, אך איני מבין כיצד להשתמש שוב בתכונה בהמשך השאלה,
אודה לעזרה והכוונה.
:זה שמתקיים <math>A \setminus B \in X</math> זה ישירות לפי הנתון. הרעיון הוא להצליח להציג את החיתוך <math>A \cap B</math> אך ורק בעזרת ההפרש, ואז ינבע שהוא שייך אל <math>X</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 17:21, 14 ביולי 2015 (UTC)

== תרגיל 2, שאלה 9 ==

לאחר הנחת האינדוקציה, מכפילים את שני אגפי האי שוויון ב3, מדוע?
בנוסף לכך המשך התרגיל לא ברור כל כך מה מתרחש ומדוע למרות שהשאלה נענתה נכונה, אשמח להסבר.
:למה עושים את הצעדים האלה בתרגיל? קודם כל, כי אפשר - אין בהם משהו לא נכון; יותר מכך, הם מביאים אל הפתרון - בתרגיל הזה הפתרון בנוי על "טריקים", ולאט לאט תתרגלו אליהם ותלמדו איך להשתמש בהם בעצמכם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 18:44, 16 ביולי 2015 (UTC)

== תרגיל 2, שאלות 10 ו- 11 ==

בשאלה 10, האם הבונוס הוא משהו שאנו אמורים לחשוב עליו בלי קשר לתרגיל (ע"י אינדוקציה חזקה אולי), או שישנה דרך לענות על הבונוס כחלק מהתרגיל?

בשאלה 11, איני מבין מדוע בקבוצה <math>C_2</math>, המוגדרת כך:<math>C_2 = \{(M,N \cup \{a\}) \in B : M \subseteq N \subseteq A \setminus \{a\}\}</math>, הרי כעת <math>a \in N</math> מתוקף האיחוד אך אינו נמצא ב-<math>A</math> מתוקף ההפרש. כנ"ל עם <math>C_3</math>. אודה להכוונה.

[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 23:39, 16 ביולי 2015 (UTC)
:1.הבונוס אינו חלק מהתרגיל הממוחשב; עליכם לחשוב על הדרך הנכונה להכליל את הנוסחא בפתרון כאשר כעת <math>F_1,F_2</math> לא ידועים, ואז להוכיח שהיא באמת נכונה באינדוקציה שלמה.
:2. אבדוק את העניין, יכול להיות שיש טעות בניסוח השאלה. אגיב על כך מאוחר יותר היום, ואם אכן יש טעות נפרסם הודעה לכולם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 06:10, 17 ביולי 2015 (UTC)
::השאלה הייתה מנוסחת באופן קצת לא ברור, כעת הניסוח שונה ונראה לי שאין בעיה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 08:51, 17 ביולי 2015 (UTC)

==תרגיל 3 שאלה 1 ==
בשאלה 1, היה צריך לעשות זוג סדור, ולא ידעתי איך אני כותב אותו במחשב אז פשוט כתבתי (a,b) ואז עשיתי הגשת שאלה וזה לא קיבל את התשובה, ואח"כ בתשובה כתוב שזה צריך להיות בצורת עמודה ואז הבנתי איך צריך לכתוב את זה אבל אני לא יכול לערוך את התשובה...

'''תשובה:''' היי, לא ממש הבנתי. הגשת כבר את התרגיל סופית? כי אם לא, אמורה להיות לך האפשרות לשנות את התשובות ולהגיש שוב.
עדכן פה מה קורה, ערן.

== תרגיל 3 שאלה 3 ==

בשאלה 3 הצלחתי הכל חוץ משני הסעיפים האחרונים, בהם צריך "לבחור" m וn.
ניסיתי להכניס כל מיני דברים שנראו לי הגיוניים והגעתי למסקנה שכנראה לא הבנתי
את מה שביקשו ממני. מה אני אמור לרשום שם ולמה?
: נסה לחשוב אילו <math>n,m</math> ייתנו לך יחס בין <math>a</math> ל-<math>c</math>, בהינתן המספרים שמבטיחים יחס כזה עם <math>b</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 14:59, 23 ביולי 2015 (UTC)

== תרגיל 3 שאלה 9 ==

היי, אני חושב שיש כמה טעויות בסוף התרגיל:

- בשורה "לכן y חסם תחתון של B ולפי הגדרת הinf קיבלנו" צריך להיות חסם מלרע במקום חסם תחתון.

- בשורה "הוכחנו שזהו חסם עליון של A נשאר להוכיח שהוא החסם המינימלי" צריך להיות חסם מלעיל במקום חסם עליון, והחסם הקטן ביותר במקום החסם המינימלי.

- בשורה האחרונה צריך להיות <math>(S,x)</math> במקום <math>(x,S)</math>.

[[משתמש:Mattya|Mattya]] ([[שיחת משתמש:Mattya|שיחה]]) 13:49, 23 ביולי 2015 (UTC)
: 1. תוקן; 2. ההערה הראשונה - תוקן, בנוגע להערה השנייה - מינימלי וקטן ביותר זה אותו הדבר (להבדיל מ'''מינימום'''). 3. תוקן ; תודה! [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 15:08, 23 ביולי 2015 (UTC)
::אני חוזר בי, מסתבר שהתבלבלתי בין מינימלי למינימום. ההערה שלך הייתה נכונה, אתקן את זה גם בתרגיל. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:12, 26 ביולי 2015 (UTC)

== פתרון לבוחן לדוגמה ==

האם ניתן להעלות פתרון מלא לבוחן לדוגמה?
בתודה מראש,
אלעד פרנס, ירדן אברמוביץ', פאר נגר ואלון כהנא.
:מחר יתקיים [[88-195 בדידה לתיכוניסטים קיץ תשעה#שיעור חזרה|שיעור חזרה]], אולי נפתור חלק מהשאלות שם. אולי נעלה פתרון ביום-יומיים הקרובים. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 26 ביולי 2015 (UTC)

== תרגיל 4 שאלה 10 ==

בסעיף ג רשום: "ואז לפי הפיכת הסדר של <math>g</math> נקבל [מה שצריך למלא]<math>g(f(x))\geq</math>". זה לא אמור להיות [מה שצריך למלא]<math>g(f(x))\leq</math>?
:כן, זה כתוב הפוך. תיקנתי. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 1 באוגוסט 2015 (UTC)

== פונקציה מוגדרת היטב ==

היי, במהלך ההרצאות דיברנו על פונקציות מוגדרות היטב, שכדי להוכיח זאת צריך להוכיח ח"ע ושלם.
תוכלו להעלות הסבר לבדיוק מה זה אומר ואולי להעלות דוגמה פשוטה להבנה?
[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 09:03, 3 באוגוסט 2015 (UTC)
:כל המתרגלים דברו על זה (ועוד נדבר על זה); לדוגמאות, ראה למשל במערכי התרגול - במיוחד את [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5#פונקציות המכבדות יחס שקילות|הדוגמא הזו]]; בהמשך גם נגדיר פונקציות כדי להראות שקילות עוצמות, ולעתים יהיה צורך להראות שהן מוגדרות היטב - ראה למשל את הדוגמאות ב[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|מערך תרגול 7]], החל מ[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7#תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)|הדוגמא הזו]] ועד הסוף. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 16:59, 3 באוגוסט 2015 (UTC)

== האלכסון של קנטור ==

אם נתבקש במבחן להוכיח את האלכסון של קנטור, האם צריך להוכיח שהפונקציה שהתקבלה באמת חח"ע ועל?
בסיכומי ההרצאות כתוב "ברור לפי הבנייה", וההוכחה מההרצאה די מסובכת. [[משתמש:Omri323|Omri323]] ([[שיחת משתמש:Omri323|שיחה]]) 12:23, 28 באוגוסט 2015 (UTC)
:שאלות מהסוג הזה יש להפנות אל המרצים; ככלל, פתרון שאמור להתקבל הוא הוכחה שראיתם בהרצאה, אבל שוב, כדאי לשאול את המרצה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:15, 28 באוגוסט 2015 (UTC)
::איך אפשר לפנות אל המרצים? [[משתמש:Omri323|Omri323]] ([[שיחת משתמש:Omri323|שיחה]]) 12:23, 28 באוגוסט 2015 (UTC)
:::אפשר במייל, אפשר גם באחד משיעורי החזרה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 13:32, 28 באוגוסט 2015 (UTC)
:הוכחה פשוטה, נחמדה ומסודרת נתווספה למערך התירגול בנושא עוצמות (הוכחה לטענה ש אלף 0 כפולה אלף 0 שווה אלף 0) [[משתמש:אחיה בר-און|אחיה בר-און]] ([[שיחת משתמש:אחיה בר-און|שיחה]]) 18:31, 30 באוגוסט 2015 (UTC)

== יהיו תשובות לשאלות מהמבחנים בלינארית ובדידה? ==

יהיו תשובות מלאות כמו לבחנים?
:לפי הבנתי אין תכנון כזה; את הפתרונות לרוב השאלות אפשר למצוא בשיעורים/מבחנים קודמים. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 18:56, 1 בספטמבר 2015 (UTC)

מבחנים בבדידה

2015-09-01T12:13:26Z

Mike: סדר

==מבחני בר-אילן==
מועד א' קיץ 2015

[[מדיה:DMtest2015.pdf|מבחן מועד א קיץ תשע"ה]]

מועד א' 2015

[[מדיה:88195_test_75a_150201.pdf|מבחן מועד א תשע"ה]], [[מדיה:88195_test_75a_sol_150220.pdf|פתרון מבחן מועד א תשע"ה]]

מועד ב' קיץ 2014

[[מדיה:DMtestB2014.pdf|מבחן מועד ב קיץ תשע"ד]],
[[מדיה:DMtestBsol2014.pdf|פתרון מבחן מועד ב קיץ תשע"ד]]

מועד א׳ 2014

[[מדיה:14BdidaTestA.pdf|מבחן מועד א תשע"ד]]
[[מדיה:14BdidaTestAsol.pdf|פתרון מבחן מועד א תשע"ד]]

מועד א׳ 2013

[[מדיה:mivh11anmoesaatim.pdf | מבחן מועד א כולל פתרון]]

מועד ב׳ 2013

[[מדיה:mivh11anmoedb11m.pdf | מבחן מועד ב כולל פתרון]]

מועד א' 2012

[[מדיה:s2012a.pdf|מועד א' + פתרון]]

מועד ב' 2012

[[מדיה:s2012b.pdf|מועד ב' + פתרון]]

מועד א, 2011

[[מדיה:11BdidaTestASol.pdf|פתרון]]

מועד ב, 2011

[[מדיה:11BdidaTestBSol.pdf|פתרון]]

מועד א, 2010

[[מדיה:10BdidaTestASol.pdf|פתרון]]

מועד ב, 2010

[[מדיה:10BdidaTestBSol.pdf|פתרון]]

[[מדיה:BdidaExamMoedA2009.pdf|מועד א, 2009]]

[[מדיה:BdidaExamMoedA2009Sol.pdf|פתרון]]

[[מדיה:BdidaExamMoedB2009.pdf|מועד ב, 2009]]

[[מדיה:BdidaExamMoedB2009Sol.pdf|פתרון]]

[[מדיה:BdidaExamMoedA2008.pdf|מועד א, 2008]]

[[מדיה:BdidaExamMoedA2008Sol.pdf|פתרון]]

[[מדיה:BdidaExamMoedB2008.pdf|מועד ב, 2008]]

[[מדיה:BdidaExamMoedA2007.pdf|מועד א, 2007]]

[[מדיה:BdidaExamMoedB2007.pdf|מועד ב, 2007]]

[[מדיה:BdidaExamMoedA2006.pdf|מועד א, 2006]]

[[מדיה:BdidaExamMoedA2005.pdf|מועד א, 2005]]

[[מדיה:BdidaExamMoedB2005.pdf|מועד ב, 2005]]

[[מדיה:BdidaExamMoedA2004.pdf|מועד א, 2004]]

[[מדיה:BdidaExamMoedB2004.pdf|מועד ב, 2004]]

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-30T18:42:58Z

Mike: /* הודעה חשובה!!!!!!!!!!!!! */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

===התחרות נסגרה!===

ברכות לזוכים:
*במקום הראשון: '''איתי מועלם''' , היחיד שפתר את שני הסעיפים!
* במקומות השני והשלישי: '''אפרים וגנר''' ו'''נעם לסרי'''.
בקרוב נפרסם את הפתרונות שלהם.

ישר כוח גם לכל מי שניסה, ובהצלחה במבחן!

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

==מבחן==
==='''הודעה חשובה!!!!!!!!!!!!!'''===
בעקבות שאלה שעלתה מצד סטודנטים רבים -- לא ברור האם מותר להיעזר במשפט קש"ב בהוכחת <math>\aleph_0 \cdot \aleph_0 = \aleph_0</math>. הוכחה ללא קש"ב מופיעה להלן, ואם המשפט יופיע ותרצו לתת הוכחה בכלים אחרים -- תוכלו לשאול את המרצה.

===פרטי המבחן===
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===הוכחות למשפטים===
אני מוסיף כאן קובץ של ההוכחות של המשפטים למבחן שאספתי וכתבתי. תודה מיוחדת לאחיה בר און וליותם ליבוביץ', דרור מידן.
[[מדיה:Mispatimbdida.pdf|הוכחות משפטים]]

אזהרה! השימוש על אחריות המשתמש בלבד.

כל הכבוד לדרור שריכז והעלה פתרונות אך זיכרו שהאחריות על נכונות הפתרון הוא על הכותב. בידקו בעצמכם את נכונות ההוכחות! בהצלחה [[משתמש:אחיה בר-און|אחיה בר-און]] ([[שיחת משתמש:אחיה בר-און|שיחה]]) 18:36, 30 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-30T18:42:15Z

Mike: /* מבחן */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

===התחרות נסגרה!===

ברכות לזוכים:
*במקום הראשון: '''איתי מועלם''' , היחיד שפתר את שני הסעיפים!
* במקומות השני והשלישי: '''אפרים וגנר''' ו'''נעם לסרי'''.
בקרוב נפרסם את הפתרונות שלהם.

ישר כוח גם לכל מי שניסה, ובהצלחה במבחן!

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

==מבחן==
==='''הודעה חשובה!!!!!!!!!!!!!'''===
בעקבות שאלה שעלתה מצד סטודנטים רבים, ולאחר בירור עם המרצים -- לא ברור האם מותר להיעזר במשפט קש"ב בהוכחת <math>\aleph_0 \cdot \aleph_0 = \aleph_0</math>. הוכחה ללא קש"ב מופיע להלן, ואם המשפט יופיע -- תוכלו לשאול את המרצה.

===פרטי המבחן===
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===הוכחות למשפטים===
אני מוסיף כאן קובץ של ההוכחות של המשפטים למבחן שאספתי וכתבתי. תודה מיוחדת לאחיה בר און וליותם ליבוביץ', דרור מידן.
[[מדיה:Mispatimbdida.pdf|הוכחות משפטים]]

אזהרה! השימוש על אחריות המשתמש בלבד.

כל הכבוד לדרור שריכז והעלה פתרונות אך זיכרו שהאחריות על נכונות הפתרון הוא על הכותב. בידקו בעצמכם את נכונות ההוכחות! בהצלחה [[משתמש:אחיה בר-און|אחיה בר-און]] ([[שיחת משתמש:אחיה בר-און|שיחה]]) 18:36, 30 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-30T18:32:49Z

Mike: /* מבחן */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

===התחרות נסגרה!===

ברכות לזוכים:
*במקום הראשון: '''איתי מועלם''' , היחיד שפתר את שני הסעיפים!
* במקומות השני והשלישי: '''אפרים וגנר''' ו'''נעם לסרי'''.
בקרוב נפרסם את הפתרונות שלהם.

ישר כוח גם לכל מי שניסה, ובהצלחה במבחן!

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

==מבחן==
==='''הודעה חשובה!!!!!!!!!!!!!'''===
בעקבות שאלה שעלתה מצד סטודנטים רבים, ולאחר בירור עם המרצים -- במבחן '''מותר''' להיעזר במשפט קש"ב בהוכחת <math>\aleph_0 \cdot \aleph_0 = \aleph_0</math>.

===פרטי המבחן===
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===הוכחות למשפטים===
אני מוסיף כאן קובץ של ההוכחות של המשפטים למבחן שאספתי וכתבתי. תודה מיוחדת לאחיה בר און וליותם ליבוביץ', דרור מידן.
[[מדיה:Mispatimbdida.pdf|הוכחות משפטים]]

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-30T18:29:25Z

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

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

===התחרות נסגרה!===

ברכות לזוכים:
*במקום הראשון: '''איתי מועלם''' , היחיד שפתר את שני הסעיפים!
* במקומות השני והשלישי: '''אפרים וגנר''' ו'''נעם לסרי'''.
בקרוב נפרסם את הפתרונות שלהם.

ישר כוח גם לכל מי שניסה, ובהצלחה במבחן!

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

==מבחן==

'''הודעה חשובה!!!!!!!!!!!!!'''

בעקבות שאלה שעלתה מצד סטודנטים רבים- מותר להוכיח במבחן שא0 כפול א0 שווה א0 באמצעות קש"ב.

המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===הוכחות למשפטים===
אני מוסיף כאן קובץ של ההוכחות של המשפטים למבחן שאספתי וכתבתי. תודה מיוחדת לאחיה בר און וליותם ליבוביץ', דרור מידן.
[[מדיה:Mispatimbdida.pdf|הוכחות משפטים]]

===שיעורי חזרה===
להלן המידע על שיעורי החזרה. כולם מוזמנים לכל השיעורים.

ביום חמישי, 27/8:
# ארז, בשעות 10-12, בניין 905 חדר 61
# תמר, בשעות 12-14, בניין 504 חדר 6
# עדי, בשעות 12-14, בניין 504 חדר 7

ביום ראשון, 30/8:
# יונתן בק, בשעות 10-12, בניין 306 חדר 111
# אחיה, בשעות 13-15, בניין 507 חדר 202
# מיכאל, בשעות 12-14, בניין 507 חדר 203
[[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:11, 24 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-30T13:11:26Z

Mike: /* טעויות נפוצות */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===הוכחות למשפטים===
אני מוסיף כאן קובץ של ההוכחות של המשפטים למבחן שאספתי וכתבתי. תודה מיוחדת לאחיה בר און וליותם ליבוביץ', דרור מידן.
[[מדיה:Mispatimbdida.pdf|הוכחות משפטים]]

===שיעורי חזרה===
להלן המידע על שיעורי החזרה. כולם מוזמנים לכל השיעורים.

ביום חמישי, 27/8:
# ארז, בשעות 10-12, בניין 905 חדר 61
# תמר, בשעות 12-14, בניין 504 חדר 6
# עדי, בשעות 12-14, בניין 504 חדר 7

ביום ראשון, 30/8:
# יונתן בק, בשעות 10-12, בניין 306 חדר 111
# אחיה, בשעות 13-15, בניין 507 חדר 202
# מיכאל, בשעות 12-14, בניין 507 חדר 203
[[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:11, 24 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-525 גיאומטריה אלגברית 1 תשעה סמסטר א

2015-08-29T13:42:47Z

Mike: /* פתרונות */

[[88-525 גיאומטריה אלגברית 1]]

==קישורים==

* [http://u.math.biu.ac.il/~bandman/Course525/ האתר של פרופ' טטיאנה בנדמן], כולל מבחנים משנים קודמות וגם חומרים.
* [[שיחה:88-525 גיאומטריה אלגברית 1 תשעה סמסטר א|שאלות ותשובות]]

==שאלות מהספר של Shafarevich==

* [[מדיה:Shafarevich- section-1 - Algebraic Curves in the Plane.pdf|פרק 1 - עקומות אלגבריות במרחב]]
* [[מדיה:Shafarevich- section-2 - Closed Subsets of Affine Space.pdf|פרק 2 - קבוצות סגורות במרחב האפיני]]
* [[מדיה:Shafarevich- section-3 - Rational Functions.pdf|פרק 3 - פונקציות רציונליות]]
* [[מדיה:Shafarevich- section-4 - Quasiprojective Varieties.pdf|פרק 4 - יריעות קוואזי-פרויקטיביות]]
* [[מדיה:Shafarevich- section-5 - Products and Maps of Quasiprojective Varieties.pdf|פרק 5 - מכפלות ופונקציות של יריעות קוואזי-פרויקטיביות]]
* [[מדיה:Shafarevich- section-6 - Dimensions.pdf|פרק 6 - מימדים]]

==מבחנים משנים קודמות==

להלן המבחנים מהאתר של פרופ' בנדמן, מסודרים לפי המועדים (שימו לב שיש עוד חומרים באתר שלה, כמו סיכום של הקורס ועוד בעיות):

# [http://u.math.biu.ac.il/~bandman/Course525/525-a-11.pdf מבחן 2011, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/525-b-11.pdf מבחן 2011, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test-525-100210.pdf מבחן 2010, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test-525-240310.pdf מבחן 2010, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-0901.pdf מבחן 2009, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-09-2.pdf מבחן 2009, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-08.pdf מבחן 2008, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test1-07.pdf מבחן 2007, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test2-06.pdf מבחן 2006, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test1-06.pdf מבחן 2006, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test2.pdf מבחן 2004, מועד א']

==פתרונות==

* [[מדיה:פתרון מבחן 2011 מועד א.pdf|מועד א' 2011]]
* [[מדיה:פתרון מבחן 2011 מועד ב.pdf|מועד ב' 2011]]
* [[מדיה:גיאומטריה_אלגברית_1_-_פתרון_מבחן_2010_-_מועד_ב.pdf|מועד ב' 2010]]
* [[מדיה:Algebraic_Geometry_2009_A.pdf|מועד א' 2009]]
* [[מדיה:Algebraic_Geometry_2009_B.pdf|מועד ב' 2009]]
* [[מדיה:Algeo_2008_a.pdf|מועד א' 2008]]
* [[מדיה:Algeo_2007_a.pdf|מועד א' 2007]]

88-525 גיאומטריה אלגברית 1 תשעה סמסטר א

2015-08-29T13:42:35Z

Mike: /* התחייבויות */ תמו הימים היפים

[[88-525 גיאומטריה אלגברית 1]]

==קישורים==

* [http://u.math.biu.ac.il/~bandman/Course525/ האתר של פרופ' טטיאנה בנדמן], כולל מבחנים משנים קודמות וגם חומרים.
* [[שיחה:88-525 גיאומטריה אלגברית 1 תשעה סמסטר א|שאלות ותשובות]]

==שאלות מהספר של Shafarevich==

* [[מדיה:Shafarevich- section-1 - Algebraic Curves in the Plane.pdf|פרק 1 - עקומות אלגבריות במרחב]]
* [[מדיה:Shafarevich- section-2 - Closed Subsets of Affine Space.pdf|פרק 2 - קבוצות סגורות במרחב האפיני]]
* [[מדיה:Shafarevich- section-3 - Rational Functions.pdf|פרק 3 - פונקציות רציונליות]]
* [[מדיה:Shafarevich- section-4 - Quasiprojective Varieties.pdf|פרק 4 - יריעות קוואזי-פרויקטיביות]]
* [[מדיה:Shafarevich- section-5 - Products and Maps of Quasiprojective Varieties.pdf|פרק 5 - מכפלות ופונקציות של יריעות קוואזי-פרויקטיביות]]
* [[מדיה:Shafarevich- section-6 - Dimensions.pdf|פרק 6 - מימדים]]

==מבחנים משנים קודמות==

להלן המבחנים מהאתר של פרופ' בנדמן, מסודרים לפי המועדים (שימו לב שיש עוד חומרים באתר שלה, כמו סיכום של הקורס ועוד בעיות):

# [http://u.math.biu.ac.il/~bandman/Course525/525-a-11.pdf מבחן 2011, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/525-b-11.pdf מבחן 2011, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test-525-100210.pdf מבחן 2010, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test-525-240310.pdf מבחן 2010, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-0901.pdf מבחן 2009, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-09-2.pdf מבחן 2009, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test525-08.pdf מבחן 2008, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test1-07.pdf מבחן 2007, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test2-06.pdf מבחן 2006, מועד א']
# [http://u.math.biu.ac.il/~bandman/Course525/test1-06.pdf מבחן 2006, מועד ב']
# [http://u.math.biu.ac.il/~bandman/Course525/test2.pdf מבחן 2004, מועד א']

==פתרונות==

* [[מדיה:פתרון מבחן 2011 מועד א.pdf|מועד א' 2011]]
* [[מדיה:פתרון מבחן 2011 מועד ב.pdf|מועד ב' 2011]]
* [[מדיה:גיאומטריה_אלגברית_1_-_פתרון_מבחן_2010_-_מועד_ב.pdf|מועד ב' 2010]]
* [[מדיה:Algebraic_Geometry_2009_A.pdf|מועד א' 2009]]
* [[מדיה:Algebraic_Geometry_2009_B.pdf|מועד ב' 2009]] (גרסא טובה יותר)
* [[מדיה:Algeo_2008_a.pdf|מועד א' 2008]]
* [[מדיה:Algeo_2007_a.pdf|מועד א' 2007]]

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-28T13:32:46Z

Mike: /* האלכסון של קנטור */

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-28T11:15:53Z

Mike: /* האלכסון של קנטור */

{{הוראות דף שיחה}}

=כללים=
* לפני ששואלים שאלה, בדקו האם משהו כבר שאל שאלה דומה.
* מאד מומלץ לנסח את השאלות תוך שימוש ב[[עזרה:תפריט ראשי#כתיבה מתמטית|כתיבה מתמטית]] - כך השאלה תהיה ברורה יותר.
* בסוף כל שאלה, עליכם לחתום את שם המשתמש שלכם, כלומר לרשום ארבעה סימני טילדה: ~.

=שאלות=

== תרגיל 2 שאלה 5 ==

בשאלה 5, ע"פ התכונות בהחלט ניתן לראות כי <math>A\setminus B</math> שייך ל-<math>X</math>, אך איני מבין כיצד להשתמש שוב בתכונה בהמשך השאלה,
אודה לעזרה והכוונה.
:זה שמתקיים <math>A \setminus B \in X</math> זה ישירות לפי הנתון. הרעיון הוא להצליח להציג את החיתוך <math>A \cap B</math> אך ורק בעזרת ההפרש, ואז ינבע שהוא שייך אל <math>X</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 17:21, 14 ביולי 2015 (UTC)

== תרגיל 2, שאלה 9 ==

לאחר הנחת האינדוקציה, מכפילים את שני אגפי האי שוויון ב3, מדוע?
בנוסף לכך המשך התרגיל לא ברור כל כך מה מתרחש ומדוע למרות שהשאלה נענתה נכונה, אשמח להסבר.
:למה עושים את הצעדים האלה בתרגיל? קודם כל, כי אפשר - אין בהם משהו לא נכון; יותר מכך, הם מביאים אל הפתרון - בתרגיל הזה הפתרון בנוי על "טריקים", ולאט לאט תתרגלו אליהם ותלמדו איך להשתמש בהם בעצמכם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 18:44, 16 ביולי 2015 (UTC)

== תרגיל 2, שאלות 10 ו- 11 ==

בשאלה 10, האם הבונוס הוא משהו שאנו אמורים לחשוב עליו בלי קשר לתרגיל (ע"י אינדוקציה חזקה אולי), או שישנה דרך לענות על הבונוס כחלק מהתרגיל?

בשאלה 11, איני מבין מדוע בקבוצה <math>C_2</math>, המוגדרת כך:<math>C_2 = \{(M,N \cup \{a\}) \in B : M \subseteq N \subseteq A \setminus \{a\}\}</math>, הרי כעת <math>a \in N</math> מתוקף האיחוד אך אינו נמצא ב-<math>A</math> מתוקף ההפרש. כנ"ל עם <math>C_3</math>. אודה להכוונה.

[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 23:39, 16 ביולי 2015 (UTC)
:1.הבונוס אינו חלק מהתרגיל הממוחשב; עליכם לחשוב על הדרך הנכונה להכליל את הנוסחא בפתרון כאשר כעת <math>F_1,F_2</math> לא ידועים, ואז להוכיח שהיא באמת נכונה באינדוקציה שלמה.
:2. אבדוק את העניין, יכול להיות שיש טעות בניסוח השאלה. אגיב על כך מאוחר יותר היום, ואם אכן יש טעות נפרסם הודעה לכולם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 06:10, 17 ביולי 2015 (UTC)
::השאלה הייתה מנוסחת באופן קצת לא ברור, כעת הניסוח שונה ונראה לי שאין בעיה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 08:51, 17 ביולי 2015 (UTC)

==תרגיל 3 שאלה 1 ==
בשאלה 1, היה צריך לעשות זוג סדור, ולא ידעתי איך אני כותב אותו במחשב אז פשוט כתבתי (a,b) ואז עשיתי הגשת שאלה וזה לא קיבל את התשובה, ואח"כ בתשובה כתוב שזה צריך להיות בצורת עמודה ואז הבנתי איך צריך לכתוב את זה אבל אני לא יכול לערוך את התשובה...

'''תשובה:''' היי, לא ממש הבנתי. הגשת כבר את התרגיל סופית? כי אם לא, אמורה להיות לך האפשרות לשנות את התשובות ולהגיש שוב.
עדכן פה מה קורה, ערן.

== תרגיל 3 שאלה 3 ==

בשאלה 3 הצלחתי הכל חוץ משני הסעיפים האחרונים, בהם צריך "לבחור" m וn.
ניסיתי להכניס כל מיני דברים שנראו לי הגיוניים והגעתי למסקנה שכנראה לא הבנתי
את מה שביקשו ממני. מה אני אמור לרשום שם ולמה?
: נסה לחשוב אילו <math>n,m</math> ייתנו לך יחס בין <math>a</math> ל-<math>c</math>, בהינתן המספרים שמבטיחים יחס כזה עם <math>b</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 14:59, 23 ביולי 2015 (UTC)

== תרגיל 3 שאלה 9 ==

היי, אני חושב שיש כמה טעויות בסוף התרגיל:

- בשורה "לכן y חסם תחתון של B ולפי הגדרת הinf קיבלנו" צריך להיות חסם מלרע במקום חסם תחתון.

- בשורה "הוכחנו שזהו חסם עליון של A נשאר להוכיח שהוא החסם המינימלי" צריך להיות חסם מלעיל במקום חסם עליון, והחסם הקטן ביותר במקום החסם המינימלי.

- בשורה האחרונה צריך להיות <math>(S,x)</math> במקום <math>(x,S)</math>.

[[משתמש:Mattya|Mattya]] ([[שיחת משתמש:Mattya|שיחה]]) 13:49, 23 ביולי 2015 (UTC)
: 1. תוקן; 2. ההערה הראשונה - תוקן, בנוגע להערה השנייה - מינימלי וקטן ביותר זה אותו הדבר (להבדיל מ'''מינימום'''). 3. תוקן ; תודה! [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 15:08, 23 ביולי 2015 (UTC)
::אני חוזר בי, מסתבר שהתבלבלתי בין מינימלי למינימום. ההערה שלך הייתה נכונה, אתקן את זה גם בתרגיל. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:12, 26 ביולי 2015 (UTC)

== פתרון לבוחן לדוגמה ==

האם ניתן להעלות פתרון מלא לבוחן לדוגמה?
בתודה מראש,
אלעד פרנס, ירדן אברמוביץ', פאר נגר ואלון כהנא.
:מחר יתקיים [[88-195 בדידה לתיכוניסטים קיץ תשעה#שיעור חזרה|שיעור חזרה]], אולי נפתור חלק מהשאלות שם. אולי נעלה פתרון ביום-יומיים הקרובים. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 26 ביולי 2015 (UTC)

== תרגיל 4 שאלה 10 ==

בסעיף ג רשום: "ואז לפי הפיכת הסדר של <math>g</math> נקבל [מה שצריך למלא]<math>g(f(x))\geq</math>". זה לא אמור להיות [מה שצריך למלא]<math>g(f(x))\leq</math>?
:כן, זה כתוב הפוך. תיקנתי. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 1 באוגוסט 2015 (UTC)

== פונקציה מוגדרת היטב ==

היי, במהלך ההרצאות דיברנו על פונקציות מוגדרות היטב, שכדי להוכיח זאת צריך להוכיח ח"ע ושלם.
תוכלו להעלות הסבר לבדיוק מה זה אומר ואולי להעלות דוגמה פשוטה להבנה?
[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 09:03, 3 באוגוסט 2015 (UTC)
:כל המתרגלים דברו על זה (ועוד נדבר על זה); לדוגמאות, ראה למשל במערכי התרגול - במיוחד את [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5#פונקציות המכבדות יחס שקילות|הדוגמא הזו]]; בהמשך גם נגדיר פונקציות כדי להראות שקילות עוצמות, ולעתים יהיה צורך להראות שהן מוגדרות היטב - ראה למשל את הדוגמאות ב[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|מערך תרגול 7]], החל מ[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7#תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)|הדוגמא הזו]] ועד הסוף. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 16:59, 3 באוגוסט 2015 (UTC)

== האלכסון של קנטור ==

אם נתבקש במבחן להוכיח את האלכסון של קנטור, האם צריך להוכיח שהפונקציה שהתקבלה באמת חח"ע ועל?
בסיכומי ההרצאות כתוב "ברור לפי הבנייה", וההוכחה מההרצאה די מסובכת.
:שאלות מהסוג הזה יש להפנות אל המרצים; ככלל, פתרון שאמור להתקבל הוא הוכחה שראיתם בהרצאה, אבל שוב, כדאי לשאול את המרצה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:15, 28 באוגוסט 2015 (UTC)

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-28T11:15:32Z

Mike: /* האלכסון של קנטור */

{{הוראות דף שיחה}}

=כללים=
* לפני ששואלים שאלה, בדקו האם משהו כבר שאל שאלה דומה.
* מאד מומלץ לנסח את השאלות תוך שימוש ב[[עזרה:תפריט ראשי#כתיבה מתמטית|כתיבה מתמטית]] - כך השאלה תהיה ברורה יותר.
* בסוף כל שאלה, עליכם לחתום את שם המשתמש שלכם, כלומר לרשום ארבעה סימני טילדה: ~.

=שאלות=

== תרגיל 2 שאלה 5 ==

בשאלה 5, ע"פ התכונות בהחלט ניתן לראות כי <math>A\setminus B</math> שייך ל-<math>X</math>, אך איני מבין כיצד להשתמש שוב בתכונה בהמשך השאלה,
אודה לעזרה והכוונה.
:זה שמתקיים <math>A \setminus B \in X</math> זה ישירות לפי הנתון. הרעיון הוא להצליח להציג את החיתוך <math>A \cap B</math> אך ורק בעזרת ההפרש, ואז ינבע שהוא שייך אל <math>X</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 17:21, 14 ביולי 2015 (UTC)

== תרגיל 2, שאלה 9 ==

לאחר הנחת האינדוקציה, מכפילים את שני אגפי האי שוויון ב3, מדוע?
בנוסף לכך המשך התרגיל לא ברור כל כך מה מתרחש ומדוע למרות שהשאלה נענתה נכונה, אשמח להסבר.
:למה עושים את הצעדים האלה בתרגיל? קודם כל, כי אפשר - אין בהם משהו לא נכון; יותר מכך, הם מביאים אל הפתרון - בתרגיל הזה הפתרון בנוי על "טריקים", ולאט לאט תתרגלו אליהם ותלמדו איך להשתמש בהם בעצמכם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 18:44, 16 ביולי 2015 (UTC)

== תרגיל 2, שאלות 10 ו- 11 ==

בשאלה 10, האם הבונוס הוא משהו שאנו אמורים לחשוב עליו בלי קשר לתרגיל (ע"י אינדוקציה חזקה אולי), או שישנה דרך לענות על הבונוס כחלק מהתרגיל?

בשאלה 11, איני מבין מדוע בקבוצה <math>C_2</math>, המוגדרת כך:<math>C_2 = \{(M,N \cup \{a\}) \in B : M \subseteq N \subseteq A \setminus \{a\}\}</math>, הרי כעת <math>a \in N</math> מתוקף האיחוד אך אינו נמצא ב-<math>A</math> מתוקף ההפרש. כנ"ל עם <math>C_3</math>. אודה להכוונה.

[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 23:39, 16 ביולי 2015 (UTC)
:1.הבונוס אינו חלק מהתרגיל הממוחשב; עליכם לחשוב על הדרך הנכונה להכליל את הנוסחא בפתרון כאשר כעת <math>F_1,F_2</math> לא ידועים, ואז להוכיח שהיא באמת נכונה באינדוקציה שלמה.
:2. אבדוק את העניין, יכול להיות שיש טעות בניסוח השאלה. אגיב על כך מאוחר יותר היום, ואם אכן יש טעות נפרסם הודעה לכולם. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 06:10, 17 ביולי 2015 (UTC)
::השאלה הייתה מנוסחת באופן קצת לא ברור, כעת הניסוח שונה ונראה לי שאין בעיה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 08:51, 17 ביולי 2015 (UTC)

==תרגיל 3 שאלה 1 ==
בשאלה 1, היה צריך לעשות זוג סדור, ולא ידעתי איך אני כותב אותו במחשב אז פשוט כתבתי (a,b) ואז עשיתי הגשת שאלה וזה לא קיבל את התשובה, ואח"כ בתשובה כתוב שזה צריך להיות בצורת עמודה ואז הבנתי איך צריך לכתוב את זה אבל אני לא יכול לערוך את התשובה...

'''תשובה:''' היי, לא ממש הבנתי. הגשת כבר את התרגיל סופית? כי אם לא, אמורה להיות לך האפשרות לשנות את התשובות ולהגיש שוב.
עדכן פה מה קורה, ערן.

== תרגיל 3 שאלה 3 ==

בשאלה 3 הצלחתי הכל חוץ משני הסעיפים האחרונים, בהם צריך "לבחור" m וn.
ניסיתי להכניס כל מיני דברים שנראו לי הגיוניים והגעתי למסקנה שכנראה לא הבנתי
את מה שביקשו ממני. מה אני אמור לרשום שם ולמה?
: נסה לחשוב אילו <math>n,m</math> ייתנו לך יחס בין <math>a</math> ל-<math>c</math>, בהינתן המספרים שמבטיחים יחס כזה עם <math>b</math>. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 14:59, 23 ביולי 2015 (UTC)

== תרגיל 3 שאלה 9 ==

היי, אני חושב שיש כמה טעויות בסוף התרגיל:

- בשורה "לכן y חסם תחתון של B ולפי הגדרת הinf קיבלנו" צריך להיות חסם מלרע במקום חסם תחתון.

- בשורה "הוכחנו שזהו חסם עליון של A נשאר להוכיח שהוא החסם המינימלי" צריך להיות חסם מלעיל במקום חסם עליון, והחסם הקטן ביותר במקום החסם המינימלי.

- בשורה האחרונה צריך להיות <math>(S,x)</math> במקום <math>(x,S)</math>.

[[משתמש:Mattya|Mattya]] ([[שיחת משתמש:Mattya|שיחה]]) 13:49, 23 ביולי 2015 (UTC)
: 1. תוקן; 2. ההערה הראשונה - תוקן, בנוגע להערה השנייה - מינימלי וקטן ביותר זה אותו הדבר (להבדיל מ'''מינימום'''). 3. תוקן ; תודה! [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 15:08, 23 ביולי 2015 (UTC)
::אני חוזר בי, מסתבר שהתבלבלתי בין מינימלי למינימום. ההערה שלך הייתה נכונה, אתקן את זה גם בתרגיל. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:12, 26 ביולי 2015 (UTC)

== פתרון לבוחן לדוגמה ==

האם ניתן להעלות פתרון מלא לבוחן לדוגמה?
בתודה מראש,
אלעד פרנס, ירדן אברמוביץ', פאר נגר ואלון כהנא.
:מחר יתקיים [[88-195 בדידה לתיכוניסטים קיץ תשעה#שיעור חזרה|שיעור חזרה]], אולי נפתור חלק מהשאלות שם. אולי נעלה פתרון ביום-יומיים הקרובים. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 26 ביולי 2015 (UTC)

== תרגיל 4 שאלה 10 ==

בסעיף ג רשום: "ואז לפי הפיכת הסדר של <math>g</math> נקבל [מה שצריך למלא]<math>g(f(x))\geq</math>". זה לא אמור להיות [מה שצריך למלא]<math>g(f(x))\leq</math>?
:כן, זה כתוב הפוך. תיקנתי. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:40, 1 באוגוסט 2015 (UTC)

== פונקציה מוגדרת היטב ==

היי, במהלך ההרצאות דיברנו על פונקציות מוגדרות היטב, שכדי להוכיח זאת צריך להוכיח ח"ע ושלם.
תוכלו להעלות הסבר לבדיוק מה זה אומר ואולי להעלות דוגמה פשוטה להבנה?
[[משתמש:אריאל421|אריאל421]] ([[שיחת משתמש:אריאל421|שיחה]]) 09:03, 3 באוגוסט 2015 (UTC)
:כל המתרגלים דברו על זה (ועוד נדבר על זה); לדוגמאות, ראה למשל במערכי התרגול - במיוחד את [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5#פונקציות המכבדות יחס שקילות|הדוגמא הזו]]; בהמשך גם נגדיר פונקציות כדי להראות שקילות עוצמות, ולעתים יהיה צורך להראות שהן מוגדרות היטב - ראה למשל את הדוגמאות ב[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|מערך תרגול 7]], החל מ[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7#תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)|הדוגמא הזו]] ועד הסוף. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 16:59, 3 באוגוסט 2015 (UTC)

== האלכסון של קנטור ==

אם נתבקש במבחן להוכיח את האלכסון של קנטור, האם צריך להוכיח שהפונקציה שהתקבלה באמת חח"ע ועל?
בסיכומי ההרצאות כתוב "ברור לפי הבנייה", וההוכחה מההרצאה די מסובכת.
:שאלות מהסוג הזה יש להפנות אל המרצים; כככל, פתרון שאמור להתקבל הוא הוכחה שראיתם בהרצאה, אבל שוב, כדאי לשאול את המרצה. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:15, 28 באוגוסט 2015 (UTC)

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-27T06:00:31Z

Mike:

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

===טעויות נפוצות===
====שאלה 3====
* בסעיף א', רבים מכם הניחו את מה שצריך להוכיח ואז הוכיחו את הנתון; אחרים לא התנסחו באופן מובן, פצלו למקרים לא מובנים או מיותרים.
* רבים מכם אמרו שאם הקבוצות לא ריקות ואם <math>A \times B = B \times A</math> אז <math>(a,b)=(b,a)</math> - וזה '''לא נכון'''!!! הנתון רק אומר שכל <math>(a,b) \in B \times A</math> וההפך.
* בכל השאלות של סעיף ב, קראתי הרבה תשובות מגוונות וסיפורים מעניינים; ניקוד מלא קיבלו רק הוכחות פורמליות ומנוסחות היטב.
* רבים מכם ערבבו מונחים מליניארית (כמו שדה, צירוף ליניארי,...) במקומות לא כ"כ קשורים.

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===מבנה המבחן===
*חמש שאלות, 115 נק' סה"כ, ללא בחירה. לשאלות אין משקל שווה, ליד כל שאלה רשום הניקוד שלה.
*'''הוכחת משפט מההרצאה''' - יופיע במבחן משפט מההרצאה בשווי של 20 נקודות מתוך הרשימה הבאה:
**קבוצת המנה של יחס שקילות על A היא חלוקה של A. כמו כן, כל חלוקה של A משרה יחס שקילות על A.
**פונקציה הפיכה אם"ם היא חח"ע ועל.
**לכל קבוצה סופית A, מתקיים <math>|P(A)|=2^{|A|}</math>.
**<math>\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0</math>
**לכל קבוצה A מתקיים <math>|A|<|P(A)|</math>
**איחוד של מספר בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

===שיעורי חזרה===
להלן המידע על שיעורי החזרה. כולם מוזמנים לכל השיעורים.

ביום חמישי, 27/8:
# ארז, בשעות 10-12, בניין 905 חדר 61
# תמר, בשעות 12-14, בניין 504 חדר 6
# עדי, בשעות 12-14, בניין 504 חדר 7

ביום ראשון, 30/8:
# יונתן בק, בשעות 10-12, בניין 306 חדר 111
# אחיה, בשעות 13-15, בניין 507 חדר 202
# מיכאל, בשעות 12-14, בניין 507 חדר 203
[[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:11, 24 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-24T11:12:41Z

Mike: /* מבחן */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

===טעויות נפוצות===
====שאלה 3====
* בסעיף א', רבים מכם הניחו את מה שצריך להוכיח ואז הוכיחו את הנתון; אחרים לא התנסחו באופן מובן, פצלו למקרים לא מובנים או מיותרים.
* רבים מכם אמרו שאם הקבוצות לא ריקות ואם <math>A \times B = B \times A</math> אז <math>(a,b)=(b,a)</math> - וזה '''לא נכון'''!!! הנתון רק אומר שכל <math>(a,b) \in B \times A</math> וההפך.
* בכל השאלות של סעיף ב, קראתי הרבה תשובות מגוונות וסיפורים מעניינים; ניקוד מלא קיבלו רק הוכחות פורמליות ומנוסחות היטב.
* רבים מכם ערבבו מונחים מליניארית (כמו שדה, צירוף ליניארי,...) במקומות לא כ"כ קשורים.

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===שיעורי חזרה===
להלן המידע על שיעורי החזרה. כולם מוזמנים לכל השיעורים.

ביום חמישי, 27/8:
# ארז, בשעות 10-12, בניין 905 חדר 61
# תמר, בשעות 12-14, בניין 504 חדר 6
# עדי, בשעות 12-14, בניין 504 חדר 7

ביום ראשון, 30/8:
# יונתן בק, בשעות 10-12, בניין 306 חדר 111
# אחיה, בשעות 13-15, בניין 507 חדר 202
# מיכאל, בשעות 12-14, בניין 507 חדר 203
[[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:11, 24 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-24T11:11:57Z

Mike: /* מבחן */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

===טעויות נפוצות===
====שאלה 3====
* בסעיף א', רבים מכם הניחו את מה שצריך להוכיח ואז הוכיחו את הנתון; אחרים לא התנסחו באופן מובן, פצלו למקרים לא מובנים או מיותרים.
* רבים מכם אמרו שאם הקבוצות לא ריקות ואם <math>A \times B = B \times A</math> אז <math>(a,b)=(b,a)</math> - וזה '''לא נכון'''!!! הנתון רק אומר שכל <math>(a,b) \in B \times A</math> וההפך.
* בכל השאלות של סעיף ב, קראתי הרבה תשובות מגוונות וסיפורים מעניינים; ניקוד מלא קיבלו רק הוכחות פורמליות ומנוסחות היטב.
* רבים מכם ערבבו מונחים מליניארית (כמו שדה, צירוף ליניארי,...) במקומות לא כ"כ קשורים.

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
* בהמשך נודיע על זמן ומקום של שיעורי החזרה של המתרגלים.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

===שיעורי חזרה===
להלן המידע על שיעורי החזרה. כולם מוזמנים לכל השיעורים.

ביום חמישי, 27/8:
# ארז, בשעות 10-12, בניין 905 חדר 61
# תמר, בשעות 12-14, בניין 504 חדר 6
# עדי, בשעות 12-14, בניין 504 חדר 7

ביום ראשון, 30/8:
# יונתן בק, בשעות 10-12, בניין 306 חדר 111
# אחיה, בשעות 13-15, בניין 507 חדר 202
# מיכאל, בשעות 12-14, בניין 507 חדר 203
[[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 11:11, 24 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-16T19:24:18Z

Mike: /* מבחן */

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

===טעויות נפוצות===
====שאלה 3====
* בסעיף א', רבים מכם הניחו את מה שצריך להוכיח ואז הוכיחו את הנתון; אחרים לא התנסחו באופן מובן, פצלו למקרים לא מובנים או מיותרים.
* רבים מכם אמרו שאם הקבוצות לא ריקות ואם <math>A \times B = B \times A</math> אז <math>(a,b)=(b,a)</math> - וזה '''לא נכון'''!!! הנתון רק אומר שכל <math>(a,b) \in B \times A</math> וההפך.
* בכל השאלות של סעיף ב, קראתי הרבה תשובות מגוונות וסיפורים מעניינים; ניקוד מלא קיבלו רק הוכחות פורמליות ומנוסחות היטב.
* רבים מכם ערבבו מונחים מליניארית (כמו שדה, צירוף ליניארי,...) במקומות לא כ"כ קשורים.

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]]. שימו לב שחלק מהשאלות כוללות נושאים שלא נלמדו השנה (הלמה של צורן, קומבינטוריקה).
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
* בהמשך נודיע על זמן ומקום של שיעורי החזרה של המתרגלים.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 19:24, 16 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

שיחה:88-112 לינארית 1 תיכוניסטים קיץ תשעה

2015-08-16T17:34:17Z

Mike: סדר

{{הוראות דף שיחה}}

=שאלות=

==תרגיל שאלה 1==
לא הבנתי מזה ה A עם הפס למעלה וגם כשכתבתי אותו אז יצא לי A עם כוכב בצד
מזה ה A הזה? והאם זה בעיה בתכנות ?

===תשובה===
אותו ה-A אם הפס למעלה הוא למעשה הצמוד לו כלומר אם Z=a+bi אז Z=a-bi הוא הצמוד לו (במספרים מרוכבים).

==תרגיל 5 שאלה 6 סעיף 1 ==
למה T העתקה לינארית?
הרי הגדירו אותה להיות מ R2 לR3 כך שאם מכניסים וקטור (x y) מקבלים (7y+3x 2y+7x) אבל וקטור זה שייך ל R2 ולא לR3

===תשובה===
זוהי טעות, תודה על ההערה, תוקן.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-16T17:03:28Z

Mike:

[[88-195 מתמטיקה בדידה]]

==חומר עזר==
* [[סרטונים:מתמטיקה בדידה|הרצאות מצולמות]]
* [[מתמטיקה בדידה - מערך תרגול|מערכי תרגול]]
* [[מבחנים בבדידה|מבחנים משנים קודמות]]
* [[מדיה:10BdidaTargilBook.pdf|חוברת]]
* [[מתמטיקה בדידה - מערך הרצאה|מערכי הרצאה]]

==קישורים==
*[http://xi.math-wiki.com מערכת XI לתרגילי הבית]
:במקרה של בעיות עם תרגילי הבית (בעיות טכניות או טעויות שאתם חושבים שיש), אתם מוזמנים לשלוח מייל לכתובת: guykapon@gmail.com

*[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|שאלות ותשובות]]

* שווה לקרוא:
# [http://www.gadial.net/2007/05/12/rational_numbers/ לא מדויק - נקודת השבר] - זהו הפוסט השני מסדרת פוסטים על הגדרת המספרים, מהטבעיים למרוכבים.
# שני פוסטים מעולים על עוצמות.
:: [http://www.gadial.net/2007/08/22/cardinality_of_sets/ לא מדויק - איזה גודל(?)]
:: [http://www.gadial.net/2007/08/25/cantor_cardinality/ לא מדויק - הגודל כן קובע] (פוסט המשך ל"איזה גודל(?)")

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

שימו לב! שימו לב! תחרות סמסטר קיץ בבדידה נפתחת!
כולם מוזמנים להשתתף!
שלושת העונים ראשונה יזכו לתהילת עולם בmath-wiki!

1. מה עוצמת קבוצת הפו' החח"ע ועל מהטבעיים לעצמם?

2. תהי A קבוצה אינסופית, מה עוצמת קבוצת הפו' החח"ע ועל מA לA?

פתרונות (מנומקים בלבד!) נא לשלוח לתמר נחשוני t a m a r n a c h s h o n i@gmail.com [[משתמש:תמר|תמר]] ([[שיחת משתמש:תמר|שיחה]]) 08:39, 11 באוגוסט 2015 (UTC)

==בוחן==
===פרטים===
* הבוחן יתקיים ביום רביעי, 29/7, בשעה 11:00. הבוחן יימשך שעה וחצי.
* החומר לבוחן - כל החומר שנלמד עד יחסי סדר (עד המפגש החמישי) כולל.
* בבוחן יהיו 3 שאלות ללא בחירה: שתיים ששוות 30 נק' ואחת ששווה 40.

===בוחן לדוגמא===
[[מדיה:בוחן לדוגמא.pdf|בוחן לדוגמא]]

מצורף בוחן לדוגמא, בסגנון דומה לבוחן האמתי. בחנים נוספים לדוגמא ניתן למצוא ב[[88-195 מתמטיקה בדידה#מועדי לימוד|דפי הקורס משנים קודמות]].

[[מדיה:פתרון הבוחן לדוגמא.pdf|פתרון הבוחן לדוגמא]]

===הבוחן ופתרון===
[[מדיה:פתרון הבוחן בבדידה.pdf|פתרון הבוחן]]

===ציונים===
[[מדיה:DM_Quiz_Grades+Statistics.xlsx|ציוני הבוחן]]

===טעויות נפוצות===
====שאלה 3====
* בסעיף א', רבים מכם הניחו את מה שצריך להוכיח ואז הוכיחו את הנתון; אחרים לא התנסחו באופן מובן, פצלו למקרים לא מובנים או מיותרים.
* רבים מכם אמרו שאם הקבוצות לא ריקות ואם <math>A \times B = B \times A</math> אז <math>(a,b)=(b,a)</math> - וזה '''לא נכון'''!!! הנתון רק אומר שכל <math>(a,b) \in B \times A</math> וההפך.
* בכל השאלות של סעיף ב, קראתי הרבה תשובות מגוונות וסיפורים מעניינים; ניקוד מלא קיבלו רק הוכחות פורמליות ומנוסחות היטב.
* רבים מכם ערבבו מונחים מליניארית (כמו שדה, צירוף ליניארי,...) במקומות לא כ"כ קשורים.

==מבחן==
המבחן (מועד א') ייערך בתאריך 31/8. לקראת המבחן, מומלץ:
* לעבור על ההרצאות, התרגולים ושיעורי הבית.
* לתרגל שאלות נוספות, ובמיוחד לפתור כמה שיותר [[מבחנים בבדידה|מבחנים משנים קודמות]].
* בנושא גרפים עלו תרגילים נוספים בתור תרגיל בית 6; התרגיל איננו להגשה, וכדי להתכונן על גרפים לקראת המבחן, מומלץ לפתור את השאלות הללו (לא תמצאו הרבה תרגילים על גרפים במבחנים).
* כל שאלה שתעלה לכם/ן, תוכלו לשאול ב[[שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה|דף השאלות והתשובות]] וכן אל אחד המתרגלים/מרצים במייל.
* בהמשך נודיע על זמן ומקום של שיעורי החזרה של המתרגלים.
'''בהצלחה'''. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 17:03, 16 באוגוסט 2015 (UTC)

==הערות==
* '''תרגיל 2 שאלה 11''' - שימו לב, היום (שישי, 17/7) שונה הניסוח בתרגיל 2 שאלה 11, שהיה קודם לכן קצת לא ברור. מי שכבר פתר את התרגיל, מומלץ לחזור ולוודא שאתם מבינים את הפתרון. [[משתמש:Mike|Mike]] ([[שיחת משתמש:Mike|שיחה]]) 10:12, 17 ביולי 2015 (UTC)

* '''תרגיל 3 שאלה 4''' - שימו לב, תוקנו כמה בעיות עם השאלה. אנא וודאו שוב את תשובתכם.

* '''תרגיל 3 שאלות 7-8''' - תוקנו בעיות עם הניקוד, בדקו שקיבלתם ניקוד מלא על תשובה נכונה.

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

2015-08-12T08:03:15Z

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

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(u,v)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> u\to v</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>u</math> ל-<math>v</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>v</math> ל-<math>u</math>, ולכן <math>v \to u</math>.
# ''טרנזיטיבי'' - אם <math> u\to v</math> וגם <math> v\to w</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> u\to w</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי <math>G=(V,E)</math> גרף בעל <math>n\ge 3</math> קדקודים. ו-<math>m \ge n </math> צלעות. אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-4 צלעות עבור 3 קדקודים) ואכן יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>. יהי <math>G</math> בעל <math>n+1>3</math> קדקודים ו- <math> m\ge n+1</math> צלעות.

''אפשרות 0'' - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.

''אפשרות 1'': קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>m-1 \ge n </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף מסדר <math>n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.

'''פתרון:''' נביט בפונקציית הדרגה <math>\operatorname{deg}:V \to \{0,1,\dots,n-1\}</math> השולחת כל איבר אל הדרגה שלו: <math>v\mapsto \operatorname{deg}(v)</math>; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:
#אם קיים קדקוד מדרגה <math>n-1</math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים
<math>\operatorname{Im}(f) \subseteq \{1,\dots n-1\} </math>.
#אם אין קדקוד מדרגה <math>n-1</math> אז <math>\operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה.

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math>. צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים, אזי ב<math>|[v]|,|[u]|\geq 50</math>. אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל היותר 100 קדקודים, בהכרח <math>|[v]|=|[u]|=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49, סתירה.

'''תרגיל''': נניח כ בגרף מתקיים <math>\forall v\in V : \operatorname{degre}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיו להם 2 שכנים). לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\operatorname{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>, ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי <math>G=(V,E)</math> גרף ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו (אם קיימת), ונקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו). יש מספר מקרים:
# אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.
# אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.
# אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.
# אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!

'''תרגיל''': הוכח/הפרך:
# אם מתקיים <math>\forall v \in V: \operatorname{deg}(v)\ge2</math>, אז <math>G</math> קשיר.
# קיים גרף בין שישה קדקודים 1,2,3,4,4,5.
# קיים גרף בין שישה קדקודים 1,2,3,4,5,5.

'''פתרון''':
# לא נכון, למשל שני משולשים מופרדים.
# לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.
# הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1.

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

2015-08-12T08:02:30Z

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

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

2015-08-12T05:10:26Z

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

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

2015-08-12T04:59:33Z

Mike: /* תרגילים נוספים */ דרגה שווה

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(u,v)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> u\to v</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>u</math> ל-<math>v</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>v</math> ל-<math>u</math>, ולכן <math>v \to u</math>.
# ''טרנזיטיבי'' - אם <math> u\to v</math> וגם <math> v\to w</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> u\to w</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי <math>G=(V,E)</math> גרף בעל <math>n\ge 3</math> קדקודים. ו-<math>m \ge n </math> צלעות. אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-4 צלעות עבור 3 קדקודים) ואכן יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>. יהי <math>G</math> בעל <math>n+1>3</math> קדקודים ו- <math> m\ge n+1</math> צלעות.

''אפשרות 0'' - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.

''אפשרות 1'': קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>m-1 \ge n </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף מסדר <math>n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.

'''פתרון:''' נביט בפונקציית הדרגה <math>\operatorname{deg}:V \to \{0,1,\dots,n-1\}</math> השולחת כל איבר אל הדרגה שלו: <math>v\mapsto deg(v)</math>; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:
#אם קיים קדקוד מדרגה <math>n-1</math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים
<math>\operatorname{Im}(f) \subseteq \{1,\dots n-1\} </math>.
#אם אין קדקוד מדרגה <math>n-1</math> אז<math>\operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה.

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-12T04:43:34Z

Mike: /* בניה */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(u,v)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> u\to v</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>u</math> ל-<math>v</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>v</math> ל-<math>u</math>, ולכן <math>v \to u</math>.
# ''טרנזיטיבי'' - אם <math> u\to v</math> וגם <math> v\to w</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> u\to w</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-12T04:41:40Z

Mike: /* הגדרות נוספות */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-12T04:40:23Z

Mike: /* משפט (לחיצת הידיים) */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-11T20:48:44Z

Mike: /* תרגיל */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-11T20:47:13Z

Mike: /* הגדרות בסיסיות */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא '''<math>k</math>-רגולרי''' אם כל הדרגה של כל קדקוד שווה ל-<math>k</math>.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-11T20:43:08Z

Mike: /* הגדרות בסיסיות */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הצלעות במשולש, ובפרט הוא סופי.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא '''<math>k</math>-רגולרי''' אם כל הדרגה של כל קדקוד שווה ל-<math>k</math>.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

2015-08-11T19:05:32Z

Mike: עריכה

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

= הגדרות בסיסיות =
'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.

הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.

'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.

'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.

'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. הסדר שלו הוא 3, כמספר הצלעות במשולש, ובפרט הוא סופי.

'''הערה''': שימו לב שמהניסוח לעיל נובע-
# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.

'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)

את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.

ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.

'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.

=== תרגיל ===
נאמר כי גרף <math>G=(V,E)</math> הוא '''<math>k</math>-רגולרי''' אם כל הדרגה של כל קדקוד שווה ל-<math>k</math>.

הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.

הוכחה:

לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן <math>k</math> זוגי או <math>n</math> זוגי.

==הגדרות נוספות==

יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.

מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

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

ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

===בניה===
עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).

'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

'''דוגמא''': ציור חביב לפי דעת המתרגל.

=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.

'''פתרון''': באינדוקציה.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- <math>n+1\leq m </math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

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

'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.

אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.

בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה

'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.

'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.

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

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

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

כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.

נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1.

אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.

אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-11T18:21:09Z

Mike: /* קישורים */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-11T18:19:58Z

Mike: /* קישורים */ סדר

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-11T18:18:10Z

Mike: /* קישורים */

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-03T16:59:14Z

Mike: /* פונקציה מוגדרת היטב */

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-08-01T10:40:26Z

Mike: /* תרגיל 4 שאלה 10 */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-31T14:35:50Z

Mike: /* בוחן */ טעויות נפוצות

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-31T13:34:02Z

Mike: /* הבוחן ופתרון */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-31T13:32:50Z

Mike: /* בוחן */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-29T17:25:29Z

Mike: /* בוחן */ ארגון

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-27T19:18:54Z

Mike: /* פתרון */ LOL

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-27T19:16:39Z

Mike: /* בוחן לדוגמא */

קובץ:פתרון הבוחן לדוגמא.pdf

2015-07-27T19:15:09Z

Mike: פתרון הבוחן לדוגמא

פתרון הבוחן לדוגמא

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-26T11:12:09Z

Mike: /* תרגיל 3 שאלה 9 */

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-26T10:40:31Z

Mike: /* פתרון לבוחן לדוגמה */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-26T08:44:09Z

Mike: /* שיעור חזרה */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-26T08:43:47Z

Mike: /* בוחן */ שיעור חזרה

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-24T10:00:29Z

Mike: /* בוחן לדוגמא */

88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-24T09:58:43Z

Mike: /* בוחן */

קובץ:בוחן לדוגמא.pdf

2015-07-24T09:52:31Z

Mike: בוחן לדוגמא בבדידה, קיץ תשע"ה

בוחן לדוגמא בבדידה, קיץ תשע"ה

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-23T15:08:02Z

Mike: /* תרגיל 3 שאלה 9 */

שיחה:88-195 בדידה לתיכוניסטים קיץ תשעה

2015-07-23T14:59:49Z

Mike: /* תרגיל 3 שאלה 3 */