בדידה - דף נוסחאות PDF

Preview

Summary

סיכום הגדרות ומשפטים מתמטיקה בדידה...

Description

‫דף נוסחאות במתמטיקה בדידה (אוניברסיטת ת"א‪)2000 ,‬‬ ‫יחסים‬

‫כמה זהויות לוגיות‬ ‫דה מורגן‬

‫‪  A  B   A  B‬‬

‫יחס‬

‫‪  A  B   A  B‬‬

‫יחס הפוך‬

‫חשבון עוצמות‬ ‫תת קבוצה של ‪A B‬‬

‫‪ASB‬‬

‫‪S  P A B ‬‬

‫‪‬‬

‫‪  A  B   A  B‬‬ ‫דיסטריבוטיביות‬

‫‪aSb  bS a‬‬ ‫‪a, c  T o S ‬‬

‫הרכבת יחסים‬

‫‪b B . a ,b S  b ,c T ‬‬ ‫‪S  A  B  S‬‬

‫יחס משלים‬

‫‪‬‬ ‫‪S 1 S‬‬

‫יחס סימטרי‬

‫‪‬‬

‫כלל‬ ‫בביטוי עם משתנה קשור‪ ,‬אפשר להחליף את המשתנה בכל‬‫משתנה אחר ‪ ,‬שאינו בתחום הקשירה‬ ‫שלילת לכל‬

‫‪x.P  x. P‬‬

‫יחס טרנסיטיבי‬

‫שלילת קיים‬

‫‪x.P  x. P‬‬

‫יחס רפלקסיבי‬ ‫בקבוצה ‪A‬‬ ‫יחס שקילות‬

‫לכל – גם‬ ‫קיים ‪ -‬או‬

‫‪x . A  B   x.A  x.B‬‬ ‫‪x.  A  B    x.A    x.B ‬‬

‫הכלה‬ ‫משפט‬

‫‪A  B  x.  x  A    x  B  ‬‬ ‫‪A  B  x.  x  A   x  B ‬‬ ‫‪A  B   A  B   B  A‬‬

‫‪x. x  ‬‬ ‫קבוצה ריקה‬ ‫מוכלת בכל קבוצה‬ ‫איחוד‬

‫הפרש‬

‫‪A  B   x  x  A   x  B ‬‬

‫אי רפלקסיבי‬ ‫אנטי סימטרי‬

‫‪a  Ab  B. aSb  bSa  a  b ‬‬

‫רפלקסיבי ‪ +‬אנטי סימטרי ‪ +‬טרנסיטיבי‬

‫‪A  B C   A  B  A  C‬‬

‫‪A U  A‬‬

‫סדר מלא חזק‬

‫סדר חלקי חזק‪+‬‬

‫‪‬‬

‫‪‬‬

‫‪xSy‬‬

‫‪P  A  B B  A‬‬ ‫‪P A   2‬‬

‫עוצמתה‬

‫‪A‬‬

‫דוגמא‪:‬‬

‫‪P     ‬‬

‫‪A‬‬

‫‪A B  B‬‬

‫‪A  B  A B‬‬

‫לכל ‪A,B‬‬

‫הגדרה‪:‬‬

‫‪ B‬‬

‫‪A‬‬

‫‪P A   2‬‬

‫‪ 0 A  1  B‬‬ ‫‪f : A  B  A  B‬‬

‫הגדרה‪ A :‬בת מניה‬

‫‪f : N  A ‬‬

‫‪AB ‬‬

‫הפיכה‬ ‫הפיכה‬

‫הגדרה‪ :‬קבוצה אינסופית יש לה תת ‪-‬קבוצה בת מניה‬ ‫משפט‪ :‬לכל קבוצה סופית ‪ ,A‬קיים ‪ n‬טבעי כך שקיימת‬ ‫‪ f : 0,1,..., n 1  A‬הפיכה‪ ,‬ואז ‪A  n‬‬

‫‪‬‬

‫משפט‪ :‬אם ‪ A‬בת מניה ו ‪B  A‬‬

‫אז ‪ B‬סופית או בת מניה‬

‫שמות‪:‬‬ ‫‪‬א"ב סופי ‪ * ,‬קבוצת כל המחרוזות ב אורך סופי מעל ‪. ‬‬ ‫אם ‪ A‬אינסופית וקיימת ‪ f : *  A‬פונקציה חלקית שהיא על‪ ,‬אז ‪A‬‬ ‫בת מניה ‪.‬‬

‫‪ .1‬אם קיימת ‪f : A  B‬‬ ‫‪ .2‬אם קיימת ‪ f : B  A‬על או ‪A  ‬‬ ‫אם ‪A  B  A  B‬‬

‫‪AB‬‬

‫חח"ע‬

‫כלומר קיימת ‪f : A  B‬‬ ‫אבל לא קיימת ‪ g : A  B‬הפיכה‬ ‫משפט קנטור‬ ‫לכל קבוצה ‪,A‬‬

‫‪ x   y‬‬

‫קבוצת המנה ‪ -‬קבוצת מחלקות השקילות ‪.‬‬

‫‪2  P  A  A‬‬

‫הוכחה שלא קיימת‬

‫‪A‬‬

‫‪: N  NN‬‬

‫‪ f‬בעזרת שיטת האלכסון‪.‬‬

‫משפט קנטור‪-‬ברנשטיין‬

‫‪AB  B A  AB‬‬ ‫כלל הסנדביץ'‪ :‬אם ‪ A  C  A  B  C‬אז ‪B  A  C‬‬

‫חלוקות‬ ‫חלוקה ‪ P‬של ‪ A‬היא קבוצת תת ‪-‬קבוצות לא ריקות של ‪A‬‬

‫‪a  A.  m  P. a  m ‬‬

‫המקיימת‬

‫‪m1, m2  P.  m1  m2    m1  m2 ‬‬

‫הקבוצות זרות‬

‫משפט‪ :‬קבוצת מחלק ו ת השקילות היא חלוקה ‪.‬‬

‫פונקציות‬ ‫לכל ‪a  A‬‬ ‫‪a, b  S‬‬ ‫לכל ‪a  A‬‬ ‫‪a, b  S‬‬

‫יחס חד ערכי‬

‫קיים לכל היותר ‪ b  B‬אחד כך ש‬ ‫קיים לפחות ‪ b  B‬אחד כך ש‬

‫פונקציה‬

‫‪f : A B‬‬

‫פונקציה חח" ע‬

‫מספר הגדרות ‪:‬‬ ‫‪ .1‬היחס ההפוך חד ערכי‬ ‫‪.2‬‬

‫היא יחס מ ‪ A‬ל ‪ B‬חד ערכי ו ‪-‬מלא‬

‫‪ x, y A. x y f  x  f  y ‬‬

‫‪a, b  a, b , a‬‬

‫קבוצת החזקה‬

‫קבוצת הפונקציות מ‪ A-‬ל‪-‬‬ ‫‪B‬‬ ‫ל ‪ A,B‬זרות‬

‫‪AB‬‬

‫מחלקת שקילות ‪ -‬מחלקת השקילות של ‪ x‬היא כל האיברים‬ ‫שמקיימים את יחס השקילות איתו‬

‫‪A   BVC    A  B V A  C ‬‬

‫‪A  B  a, b a  A  b  B‬‬

‫‪A‬‬

‫חח"ע‬

‫‪AVB   A  B   A B ‬‬

‫‪A B  A B‬‬

‫מספר היחסים בקבוצה‬

‫‪x S  T  y  xSy  xTy‬‬

‫יחס מלא‬

‫קבוצה תת‪-‬הקבוצות של ‪A‬‬

‫‪+‬‬

‫איחוד יחסים‬

‫‪A B  A B‬‬

‫דה‪-‬מורגן‬

‫הגדרת זוג סדור‬

‫‪ ‬‬

‫‪a, b  A. aSb bSa a  b ‬‬

‫‪AVB  AVB‬‬

‫מכפלה קרטזית‬

‫‪ ‬‬

‫‪a , b  A. aSb  bSa‬‬

‫סדר מלא‬

‫סדר חלקי‬

‫‪A VB   A  B   B  A ‬‬

‫הקבוצה המשלימה‬ ‫(כאשר יש מובן ל ‪)U‬‬ ‫הפרש‬

‫זהות‬

‫‪a  Ab  A. aSb  bSa ‬‬

‫סדר חלקי חזק‬

‫‪ x x  A  x  B    x  B  x  A‬‬

‫הפרש סימטרי‬

‫רפלקסיבי ‪ +‬סימטרי ‪ +‬טרנסיטיבי‬

‫אי רפלקסיבי ‪ +‬טרנסיטיבי‬

‫‪A B  A  B‬‬

‫‪‬‬

‫‪a  A. aSa‬‬

‫‪A  B  x x  A  x  B ‬‬

‫חיתוך‬

‫דיסטריבוטיביות‬

‫‪a  A.aSa‬‬

‫‪ A.  A‬‬ ‫‪A  B  x x  A   x  B ‬‬

‫הפרש סימטרי‬

‫‪ a, b A. a, b  S  b , a  S ‬‬ ‫‪a, b, c  A. aSb  bSc  aSc‬‬

‫אנטי סימטרי חזק‬ ‫(גם לא עם עצמו)‬ ‫סדר חלקי‬

‫תורת הקבוצות הנאיבית‬ ‫שיוויון קבוצות‬

‫‪S 1  b, a‬‬ ‫‪1‬‬

‫‪A   B  C   A  B   A  C‬‬ ‫‪A   B  C   A  B  A  C‬‬

‫‪‬‬

‫‪a, b  S‬‬

‫‪A  B  A  B   B  A‬‬

‫גרירה‬

‫‪ x, y A. f  x  f  y  x y .3‬‬ ‫פונקציה על‬

‫‪ .1‬היחס ההפוך מלא‬

‫הרכבה‬

‫‪b  B. a A.  f  a   b  .2‬‬ ‫‪g : B C‬‬

‫‪‬‬

‫כלל‬

‫‪ g  f c‬‬

‫‪ g o f c‬‬

‫‪f : A B‬‬

‫‪g o f : A C‬‬

‫‪x. f  x   f‬‬

‫‪‬‬

‫פונקציה הפיכה‬

‫‪P  P    ,‬‬ ‫משפט‬

‫‪:‬‬

‫מכפלה‬

‫פונקציה חח" ע ו ‪-‬על‪ .‬נקראת גם פ' שקילות‬

‫הרכבת פונקציות‬

‫‪P  A  B  P A  P  B‬‬

‫‪f oh‬‬

‫הר כבת פונקציות היא אסוציאטיבית‬ ‫אם‬

‫‪g, f‬‬

‫חח"ע‬ ‫על‬

‫אז‬

‫‪gof‬‬

‫חח"ע‬

‫אז‬

‫‪gof‬‬

‫על‬

‫אם‬

‫‪g, f‬‬

‫אם‬

‫‪gof‬‬

‫חח"ע‬

‫אז‬

‫‪f‬‬

‫חח"ע‬

‫אם‬

‫‪gof‬‬

‫על‬

‫אז‬

‫‪g‬‬

‫על‬

‫אם‬

‫‪gof‬‬

‫חח"ע ו‪-‬‬

‫על‬

‫אז‬

‫‪g‬‬

‫חח"ע‬

‫אם‬

‫‪ g o f‬על ו‪g -‬‬

‫חח"ע‬

‫אז‬

‫‪f‬‬

‫על‬

‫‪f‬‬

‫משפט‪ f : A  B :‬הפיכה ‪‬‬ ‫כך ש‪g o f  I A  f og  IB :‬‬

‫‪ g o f  oh  g o‬‬

‫קיימת ‪, g : B  A‬‬

‫אם ‪ g‬קיימת היא יחידה ותסומן ‪:‬‬

‫‪g  f 1‬‬

‫חשבון עוצמות אינסופיות‬ ‫כללי האריתמטיקה הבסיסיים הנוגעים בחיבור ‪ ,‬כפל וחזקות של‬ ‫מספרים טבעיים תקפים גם לעוצמות אינסופיות‪.‬‬ ‫אי שויון חלש נשמר‪.‬‬ ‫אי שויון חזק אינו נשמר‬ ‫פעולות הפוכות – חיסור‪ ,‬חילוק ‪ ,‬שורש‪ ,‬לוגריתם אינן ניתנות להכללה‬ ‫עבור עוצמות אינסופיות‬

‫דף נוסחאות במתמטיקה בדידה (אוניברסיטת ת"א‪)2000 ,‬‬ ‫שיטת ברנולי לפתרון פולינומים‬ ‫מניה בסיסית‬ ‫נבנה נוסחת נסיגה כך ששורי הפולינום האופייני יהיו‬ ‫עקרון שובך היונים – אם מספר היונים גדול ממספר התאים ‪ ,‬יש שתי‬ ‫יונים באותו תא (ניסוח לא פורמאלי להגדרת "> ")‪.‬‬ ‫‪A ‬‬ ‫עקרון הסכום – חלוקה למקרים ‪ .‬אם ‪ A‬זרות אז‪A :‬‬ ‫‪i‬‬

‫‪i‬‬

‫‪‬‬

‫כאשר לכל ‪ n‬גדול מ ‪ Z n 1‬‬

‫איברים סמוכים תשאף להיות ‪Z1‬‬

‫‪i‬‬

‫עקרון הכפל – לניסוי רב שלבי‪ ,‬שבכל שלב אפשרויות בחירה‬

‫מעבר למשלים ‪A  B  A  A  B -‬‬ ‫אפשרויות לסדר ‪ n‬אנשים בשורה‪ , n ! :‬במעגל‪:‬‬ ‫‪n‬‬ ‫‪‬‬ ‫‪1‬‬ ‫!‬ ‫‪ ‬‬ ‫תמורות ללא‬ ‫חזרות‬

‫פ' חח"ע‬

‫תמורות עם‬ ‫חזרות‬

‫פונקציה‬

‫צרופים ללא‬ ‫חזרות‬

‫תת קבוצות בעוצמה ‪ k‬של‬ ‫קבוצה בעוצמה ‪n‬‬

‫צרופים עם‬ ‫חזרות‬

‫לחלק ‪ k‬כדורים ל ‪ n‬תאים‬

‫למשל חישוב‬

‫!‪n‬‬

‫‪f : 1..k  A‬‬

‫‪nk ‬‬ ‫‪k‬‬

‫‪f : 1..k  A‬‬

‫עבור סידרה‬

‫‪a 1, a 2 ,...‬‬

‫‪.‬‬

‫‪n‬‬

‫‪3‬‬

‫‪.‬‬

‫‪Z1  1  3 , Z2  1  3‬‬

‫נגדיר ‪:‬‬

‫‪ x  Z 1 x  Z 2  0‬‬ ‫‪x2   Z1  Z 2  x  Z1Z 2  0‬‬ ‫‪an 2   Z1  Z2  an 1  Z1 Z2 an‬‬

‫נפתח פולינום אופייני‬

‫סדרת הנסיגה תהיה‬

‫‪ n‬‬ ‫!‪n‬‬ ‫‪ ‬‬ ‫!‪ k   n k ! k‬‬ ‫‪ k  n  1‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪ k ‬‬

‫פונקציות יוצרות‬ ‫הפ' היוצרת תהיה ‪:‬‬

‫הכלה – הדחה‬

‫‪F   k 0 a kx‬‬

‫התכונה הבסיסית‬

‫‪n‬‬

‫כדי לחלץ את הסדרה מהפונקציה ‪ ,‬נשאל‪ :‬מה המקדם של ‪? x‬‬

‫‪S  S   S    S‬‬ ‫‪S  S   S    S‬‬ ‫‪  U‬‬

‫‪1‬‬ ‫‪1 x‬‬

‫נוסחת ההכלה הדחה‬ ‫תהי ‪ F‬משפחת תת ‪-‬קבוצות עם "תכונות רעות " של ‪ U‬סופית‬ ‫‪ - N‬מספר כל האיברים ללא " תכונות רעות" (שלא שייכים לקבוצות ‪)F‬‬

‫‪x‬‬

‫נוסחת ההכלה הדחה‬

‫‪S‬‬

‫‪N0    S   1‬‬

‫‪k 0‬‬ ‫‪‬‬

‫כאשר השימוש ב ‪ U‬אסור‬

‫‪ cx ‬‬

‫‪S 1‬‬

‫‪S    1‬‬

‫‪k 0‬‬

‫משפט הבינום‪:‬‬

‫סכום של סידרה הנדסית‪:‬‬

‫‪1 q 1‬‬ ‫‪a1  a1 q ... a1 q  a1‬‬ ‫‪1 q‬‬ ‫‪a1‬‬ ‫‪a1  a1 q ... ‬‬ ‫)‪( q  1‬‬ ‫‪1 q‬‬ ‫‪n‬‬

‫אם ‪ F‬יוצרת את‬

‫‪ak‬‬

‫‪‬‬

‫‪F ‬‬

‫‪S F ,s ‬‬

‫‪ n‬זוגי‬

‫‪Dn   n!/ e ‬‬

‫‪ n‬אי‪-‬זוגי‬

‫‪Dn   n!/ e ‬‬

‫גרף משלים‬

‫בהינתן גרף ‪ , G  V , E ‬הגרף המשלים הוא ‪ V , E ‬‬

‫אותם קודקודים כך שבין ‪ 2‬כל שני קודקודים יש קשת ב ‪ G‬‬ ‫ביניהם קשת ב ‪. G‬‬

‫נוסחת קיילי‬ ‫מספר העצים בעלי‬

‫קוד פריפר‬ ‫התאמת סדרה לעץ ‪:‬‬ ‫מורידים את העלה הכי נמוך‬ ‫‪.1‬‬ ‫רו שמים את הקודקוד המחובר אליו‬ ‫‪.2‬‬ ‫ממשיכים עד שנשארת קשת אחת ושני קודקודים‬ ‫‪.3‬‬ ‫כל קודקוד‬

‫‪x‬‬

‫‪‬‬

‫‪b k  a k‬‬

‫דיאגרמה מישורית‬ ‫גרף מישורי‬

‫משפט‬

‫נוסחאות נסיגה‬

‫גרף פשוט‬ ‫תת גרף‬

‫‪ak  2  5 ak 1  6 ak‬‬ ‫‪x 2  5x  6  0 ; x  3, 2‬‬ ‫‪ak  A 2 k  B 3k‬‬ ‫‪ a‬נמצא את ‪A,B‬‬

‫נוסחת נסיגה לא הומוגנית‬ ‫לדוגמא‪:‬‬

‫‪ak  1  ak  4k‬‬ ‫‪1‬‬ ‫‪F  a0‬‬ ‫‪ 2F ‬‬ ‫‪1 4x‬‬ ‫‪x‬‬

‫‪ .1‬נשתמש בפונקציות יוצרות‬ ‫‪ .2‬בד"כ נעזר בשברים חלקיים‬

‫)‪f ( x‬‬ ‫‪A‬‬ ‫‪B‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪(a  bx )c  dx  (a bx )  c dx‬‬ ‫‪ .3‬כדי לפרק את הביטוי לאיבר‬ ‫כללי נעזר בנוסחה‬

‫‪1‬‬ ‫‪1  cx‬‬

‫‪‬‬

‫‪k‬‬

‫‪‬‬

‫‪cx ‬‬

‫בכל גרף פשוט בעל ‪ 2‬קודקודים לפחות ‪ ,‬יש זוג קודקודים‬ ‫בעלי אותה דרגה‬ ‫סכום דרגות הקודקודים שווה כפלים מספר הקשתות‬

‫משפט‬ ‫משפט‬

‫‪d V   2 E‬‬

‫לדוגמא‪:‬‬

‫‪k .a k  F   x . ‬‬

‫‪ x.1  ex‬‬ ‫‪a2 x 2‬‬ ‫‪a x2‬‬ ‫‪...  F  a1  a2 x  3 ...‬‬ ‫!‪2‬‬ ‫!‪2‬‬

‫‪F  a0  a1 x ‬‬

‫‪e x‬‬

‫גרף ללא לולאות וללא קשתות מקבילות‬

‫‪ V , E‬‬

‫משפט‬

‫מסלול \ מסילה‬ ‫מסלול פשוט‬ ‫מעגל‬

‫מסלול שבו הקודקוד הראשון והאחרון זהים‬

‫מעגל פשוט‬

‫מסילה פשוטה סגורה בקשת בין הקצוות‬

‫קשירות‬ ‫רכיב קשירות‬

‫היחס על ‪" :v‬קיים מסלול בין קודקוד ‪ x‬ל ‪."y‬‬ ‫זהו יחס שקילות‪.‬‬ ‫כל תת גרף המושרה ע" י מחלקת השקילות של היחס‬

‫גרף קשיר‬

‫גרף בעל רכיב קשירות יחיד‬

‫עץ‬ ‫יער‬

‫גרף שאין בו מעגלים (ולכן גם פשוט)‬ ‫מספר קשתות ‪E  V  1‬‬

‫מעגל אוילר‬

‫מעגל הכולל את כל קשתות הגרף (כ"א פעם אחת)‪.‬‬ ‫ ניתן לצייר גרף אוילר במשיכת קולמוס אחת‪.‬‬‫גרף קשיר שיש בו מעגל אוילר‬ ‫גרף קשיר הוא גרף אוילר‬

‫‪‬‬

‫לכל קודקוד ‪,x‬‬

‫)‪d ( x‬‬

‫זוגי‪.‬‬

‫הגרף השלם‬

‫הגרף השלם על ‪ n‬קודקודים הוא הגרף שבו קיימת קשת בין‬ ‫כל זוג קודקודים שונים מסומן‪. K :‬‬

‫גרף דו צדדי‬

‫‪ V , E ‬‬

‫‪n‬‬

‫משפט‬

‫‪5‬‬

‫מספר הצביעה‬

‫של גרף הוא מספר הצבעים המינימאלי שבו ניתן לצבוע‬ ‫את כל הקודקודים בגרף כך שאין קודקודים סמוכים‬ ‫באותו צבע‬ ‫ניתן לצבוע את הגרף ב ‪ k‬צבעים כך ששתי קצוות של כל‬ ‫קשת צבועים בצבעים שונים‪ .‬כלומר‪ ,‬מספר הצביעה הוא‬ ‫‪ k‬לכל היותר‬

‫גרף דואלי‬

‫של גרף מישורי הוא בעל אותה קבוצת קשתות של הגרף‬ ‫המקורי ‪ .‬הקודקודים שלו הם הפאות של הגרף המקורי‬ ‫וקצות כל קשת הן הפאות משני צידיה‪.‬‬

‫משפט ארבעת‬ ‫הצבעים‬

‫בגרף מכוון‬

‫‪ G‬הוא דו צדדי אם ניתן לחלק את ‪ V‬לשתי‬ ‫‪V ,V‬כך שכל קשתות הגרף הם בין הקבוצות‬

‫גרף דו צדדי ‪‬‬

‫אי אפשר לכווץ אותו ל ‪ K‬או ל‬

‫‪3,3‬‬

‫‪.K‬‬

‫הגרף הדואלי לגרף אוילר הוא דו‪-‬צדדי – כל מפה‬ ‫מצוירת ב"משיכת קולמוס" אפשר לצבוע בשני צבעים‬

‫גרף קשיר מכוון הוא גרף אוילר אם לכל קודקוד ‪ ,x‬דרגת‬ ‫הכניסה שווה לדרגת היציאה ‪. d (x)   d ( x) ‬‬

‫‪2‬‬

‫משפט קורטובסקי‬ ‫גרף מישורי ‪‬‬

‫גרף ‪ k‬צביע‬

‫גרף קשיר שאין בו מעגלים מספר קשתות ‪E  V  1‬‬

‫קבוצות זרות‬

‫בגרף דו צדדי מישורי פשוט בעל לפחות ‪ 3‬קודקודים‪:‬‬

‫‪.V ‬‬

‫הילוך שבו אף קשת לא חוזרת יותר מפעם אחת‬

‫מ שפט‬

‫בגרף מישורי פשוט בעל לפחות ‪ 3‬קודקודים ‪:‬‬

‫‪m  3n  6‬‬

‫‪m  2n  4‬‬

‫הילוך שבו אף קודקוד פנימי לא חוזר יותר מפעם אחת‬

‫גרף אוילר‬

‫גרף מישורי בעל מספר מקסימלי של קשתות ו ‪3‬‬ ‫קודקודים לפחות הוא גרף משולשי‪.‬‬ ‫בגרף מישורי סכום ה יקפי הפאות הוא פעמיים מספר‬ ‫הקשתות ‪ .‬ובגרף משולשי‪. 2m  3 f :‬‬ ‫ביחד עם נוסחת אוילר ‪:‬‬

‫משפט‬

‫‪ G‬יקרא תת גרף של ‪ G‬אם‬

‫‪ V  E  E‬‬

‫‪ak 2  ak 1  ak  F F F‬‬ ‫פתרון‬

‫‪ V , E ‬‬

‫‪G‬גרף מישורי קשיר‪ .‬נסמן‪ n :‬מספר‬

‫‪m  3n  6‬‬

‫אם ‪ g‬מכיל קשת אז שתי קצותיה ימצאו גם ב ‪. g‬‬ ‫תת גרף מושרה תת גרף של ‪ ,G‬שקבוצת קודקודיו ‪ V‬ומכיל את כל הקשתות‬ ‫ב ‪ E‬ששני קודקודיהם ב ‪. V‬‬ ‫סדרת קודקודים ‪ ,‬שבין כל שני עוקבים בה‪ ,‬יש קשת‪.‬‬ ‫טיול \ הילוך‬

‫‪k 0‬‬

‫פונקציות יוצרות מעריכיות‬ ‫כאשר יש תמורות במקום צרופים‬ ‫פ' יוצרת מעריכית יוצרת את סידרת הנגזרות שלה ב ‪x=0‬‬

‫‪a kxk‬‬ ‫!‪k‬‬

‫של גרף היא דיאגרמה במישור שבו כל נקודת חיתוך היא‬ ‫קודקוד‬ ‫גרף שיש לו דיאגרמה מישורית‬

‫גרף מישורי משולשי גרף משורי שכל פאותיו משולשים‬

‫משפט‬

‫‪ .2‬נוסחא לאיבר כללי תהיה‬

‫מופיע ‪ d ( x) 1‬פעמים בסדרה‪ .‬אורך הסדרה ‪.n-2‬‬

‫התאמת עץ לסדרה ‪:‬‬ ‫יוצרים טבלה של כל הקודקודים ודרגותיהם בעץ‬ ‫‪.1‬‬ ‫עוברים על תווי הסדרה באותו כיוון שיצרנו אותה (שמאל לימין)‬ ‫‪.2‬‬ ‫מוצאים עלה בעל מספר מינימאלי ומחברים אותו לתו הנוכחי‬ ‫‪.3‬‬ ‫בסדרה‬ ‫מעדכנים את הדרגות (מחסירים ‪ 1‬פעמיים) ומוחקים את התו‪,‬‬ ‫‪.4‬‬ ‫שהשתמשנו בו ‪ .‬וחוזר חלילה‪...‬‬

‫‪i‬‬

‫‪ .3‬בעזרת תנאי התחלה ‪, a‬‬ ‫‪0 1‬‬

‫‪v  1, 2,..., n‬‬

‫קודקודים הוא‬

‫‪n 2‬‬

‫‪n‬‬

‫‪.‬‬

‫‪m  n  f 2‬‬

‫‪k 0‬‬

‫‪ .1‬מחלצים פולינום אופייני‬

‫אין‬

‫משפט העצים‬ ‫יהי ‪ T‬גרף בעל ‪ n‬קודקודים ‪ .‬הטענות הבאות שקולות ‪:‬‬ ‫‪ T‬הוא עץ‬ ‫‪.1‬‬ ‫‪ T‬קשיר מינימאלי‬ ‫‪.2‬‬ ‫‪ T‬חסר מעגלים מקסימלי‬ ‫‪.3‬‬ ‫‪ T‬קשיר בעל ‪ n-1‬קשתות‬ ‫‪.4‬‬ ‫‪ T‬חסר מעגלים בעל ‪ n-1‬קשתות‬ ‫‪.5‬‬ ‫לכל זוג קודקודים יש ב ‪ T‬מסילה יחידה‪ ,‬שהם קצותיה‬ ‫‪.6‬‬ ‫‪ T‬קשיר‪ ,‬ובכל תת גרף שלו יש קודקוד בדרגה ‪ 0‬או ‪.1‬‬ ‫‪.7‬‬

‫נוסחת אוילר‬

‫גרפים‬

‫נוסחת נסיגה הומוגנית‬ ‫לדוגמא‪:‬‬

‫‪ G‬על‬

‫הקודקודים‪ m ,‬מספר הקשתות ‪ f ,‬מספר הפאות‬

‫פונקציה יוצרת של סדרת סכומים חלקיים‬ ‫אז‬

‫‪.‬‬

‫בכמה תמורות של ‪ n‬איברים שום איבר אינו במקומו הטבעי?‬

‫‪n‬‬

‫‪1x‬‬

‫בגרפים איזומורפיים‪ E 1  E 2 :‬ו ‪V1  V 2‬‬

‫ב ‪G2‬‬

‫‪.‬‬

‫אי סדר טוטאלי‬

‫‪n‬‬ ‫‪n n k k‬‬ ‫‪n‬‬ ‫‪ a b     k a  b‬‬ ‫‪k  0 ‬‬

‫‪ F‬יוצרת את‬

‫פונקציה הפיכה ‪g : V1  V2‬‬ ‫ביניהם קשת ב ‪  G1‬יש קשת בין )‪ g ( a‬ל )‪g (b‬‬

‫‪S F‬‬

‫‪1‬‬ ‫‪1  cx‬‬ ‫‪‬‬ ‫‪ k  n1  k‬‬ ‫‪1‬‬ ‫‪ ‬‬ ‫‪x‬‬ ‫‪n‬‬ ‫‪1‬‬ ‫‪‬‬ ‫‪k‬‬ ‫‪x‬‬ ‫‪0‬‬ ‫‪‬‬ ‫‪ k ‬‬ ‫‪ ‬‬ ‫‪‬‬

‫‪k‬‬

‫‪1‬‬

‫‪1‬‬

‫‪0‬‬

‫‪‬‬

‫‪k‬‬

‫‪2‬‬

‫‪ V1 , E1  , G2  V2‬‬

‫‪ G‬הם איזומורפיים אם קיימת‬

‫עבורה לכל זוג קודקודים ‪a, b V‬יש‬

‫‪A  B  A  B  A B‬‬

‫חיתוך של קבוצה ריקה‬

‫‪‬‬

‫‪‬‬

‫‪Z1... Zn‬‬

‫‪ . Z‬ככל שנפתח את הסדר חלוקת‬

‫אופרטור האיחוד של כל האיברים של‬ ‫קבוצה‬ ‫‪k‬‬

‫‪‬‬

‫‪an 1 A  Z 1n 1  B  Z 2n 1‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪ Z1‬‬ ‫‪n ‬‬ ‫‪an‬‬ ‫‪A  Z 1n  B  Z 2n‬‬

‫‪A1  A2  ...  A1  A 2  ...‬‬

‫!‪n  k ‬‬

‫‪1‬‬

‫איזומורפיזם‬ ‫גרפים ‪, E‬‬

‫‪1‬‬

‫אין בו מעגל באורך אי זוגי‪.‬‬

‫כל גרף מישורי ללא לולאות הוא ‪- 4‬צביע‪ .‬בנוסח דואלי‪:‬‬ ‫אפשר לצבוע כל "מפה " בארבעה צבעים לכל היותר‪ ,‬כך‬ ‫שלמדינות גובלות צבעים שונים‪ .‬בכיתה הוכחנו גירסאות‬ ‫חלשות יותר – כל גרף משורי ללא לולאות הוא ‪-6‬צביע‪.‬‬ ‫כל גרף משורי ללא לולאות הוא ‪-5‬צביע‬...