מציג תוצאות 1 עד 2 מתוך 2

אשכול: גרפים

  1. #1
    משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל גרפים

    בס''ד

    אשמח לפתרון , תודה רבה !
    קבצים מצורפים קבצים מצורפים
    אהבתי גרפיםam12348 אהב \ אהבו את התגובה
     

  2. #2
    מדריך ויועץ חבר Emath

    פרטי משתמש

    התשובה הטובה ביותר

    ברירת מחדל הוכחת קשירות של גרף

    שבוע טוב,

    נניח בשלילה כי הגרף G אינו קשיר. אז קיימים שני קדקודים u,v t, אשר ביניהם אין מסלול
    שמקשר אותם. בפרט אין קשת המחברת רותם.

    נתון כי כל אחד מהקדקודים u ו-v עם דרגה k, אז קיימים k קדקודים המחוברים בקשת כל אחד ל-u
    נקרא לקבוצה הזאת U, ו-k קדקודים המחוברים בקשת כל אחד ל-v. נקרא לקבוצה הזאת V

    יתכנו שני מצבים:

    1. קיים קדקוד המשותף ל-U ול-V דהיינו
    $U \cap V \neq \emptysetִִִ$

    נקרא לקדקוד הזה w

    במצב זה קיים מסלול מ-u ל-v העובר דרך w, בסתירה להנחה שאין בין u לבין v מסלול המקשר אותם

    2. אין אף קדקוד המשותף בין U ו-V, דהינו
    $U \cap V = \emptysetִִִ$

    אם הדרגה של כל קדקוד היא k, אז יש לנו את קדקוד u יחד עם k קדקודים המקושרים אליו ,סה"כ k+1 קדקודים
    וכן את קדקוד v יחד עם k קדקודים המקושרים אליו, סה"כ k+1 קדקודים

    סה"כ
    $k+1+k+1=2k+2$
    מכאן שמספר הקדקודים בגרף גדול/שווה ל- 2k+2

    אבל שים לב מה נתון לנו: מספר הקדקודים בגרף 2k+1,

    $2k+2>2k+1$
    שוב סתירה

    מכאן שההנחה בשלילה אינה נכונה והגרף קשיר. מש"ל

    בברכה,
    עמוס
    אהבתי אריאל, מיכאל אהב \ אהבו את התגובה
     

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 9

הרשאות

  • אתה לא יכול לפרסם אשכולות חדשים
  • אתה לא יכול לפרסם תגובות
  • אתה לא יכול לצרף קבצים להודעותיך
  • אתה לא יכול לערוך את הודעותיך
  •  
אודות Emath
האתר Emath הינו יוזמה פרטית והוקם בתחילת שנת 2008 .
מטרתנו הינה למנף את הישגי התלמידים למתמטיקה ופיסיקה בארץ בכלל ובפרט בקרב תלמידי התיכון .
אנו מספקים מספר שירותים לתלמיד, ביניהם גישה למאות אלפי פתרונות איכותיים לתרגילים, פורום עזרה במתמטיקה ופיסיקה הגדול מסוגו בארץ, מאגר סיכומים, מרתונים בוידאו, פתרונות לבגרויות ועוד.
כלים אלו, מאפשרים לכל אחד, ללא תלות במיקומו, ללמוד, לתרגל ולהתמקצע על-מנת להתכונן בצורה מיטבית לבגרות במתמטיקה או פיסיקה .

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו