אקדמי חמישי

Regalia

New member
תורת הגרפים

שלום לכולם,
אשמח ואודה לעזרה או רמז:

הוכיחו כי אם בגרף פשוט (G = (V,E מתקיים:
d(x) + d(y) >=
- 1 לכל שני צמתים לא סמוכים x,y אז הגרף קשיר.


אז ניסיתי להוכיח ישירות ולא הגעתי כל כך רחוק, אז אני מנסה בשלילה.

נניח בשלילה ש- G אינו קשיר.
כלומר קיימים צמתים x,y ששייכים ל V כך שלא קיים מסלול בינהם.
בפרט x,y אינם סמוכים, לכן d(x) + d(y) >=
- 1 מתקיים ע"פי הנתון.

האם מתחבאת כאן סתירה שאני לא רואה?
או שאני ממש לא בכיוון...
 

Regalia

New member
תיקון לנוסחא


d(x) + d(y) >= | v | - 1

הוכיחו כי אם בגרף פשוט (G = (V,E מתקיים:
d(x) + d(y) >= | v | - 1 לכל שני צמתים לא סמוכים x,y אז הגרף קשיר.
 

אורי769

New member
היא לא ממש מתחבאת...

היא מתחבאת בערך כמו שהבת שלי בת ה-3 מתחבאת מתחת לשמיכה עם הרגליים והשיער מציצים.

נניח יש 10 קודקודים בגרף. כמה שכנים יכול להיות לקודקוד x? כמה ל-y? נניח שאין להם שכנים משותפים - כמה שכנים יש להם יחד?
 

Regalia

New member


אם יש 10 קודקודים בגרף (פשוט)

אז ל x ול- y יכולים להיות לכל היותר 1 - 10 שכנים
(הגרף פשוט אז לא יהיו לולאות כלומר x או y לא יכולים להיות שכנים של עצמם)

אם אין להם שכנים משותפים, אז יכולים להיות להם לכל היותר 2 - 10 שכנים יחד?

אני לא מצליח להצדיק את זה.
 

Regalia

New member
הספירה של המקרה השני

למה בעצם יורדים 2?
אני לא מצליח לנסח את זה לעצמי
 

אורי769

New member
בא נראה

נניח x,y קודקודים שאינם שכנים ושאין להם שכנים משותפים. נסמן ב-(N(x ו-(N(y את השכנים של כל אחד מהם. אנחנו יודעים שהקבוצות האלה לא נחתכות, לכן
q |N(x)| + |N(y)| = |N(x) U N(y)| q
כמו כן, x,y לא מוכלים בקבוצות האלה. אז מה אתה יכול להגיד על
q |N(x) U N(y)| q
 

אורי769

New member
ודאי

האם הסימן שאלה בסוף מעיד שאתה לא בטוח בתשובה הזאת? יש לך תת קבוצה של V שלא מכילה לפחות שני איברים של V. מה גודלה?
 

שושהXD

New member
בסיס ומימד

אשמח לקבל עזרה לשאלה המצורפת
הדרך שבה ניסיתי לפתור את זה
הייתה ליצור פולינום כללי בX^4
עם מקדמים a,b,c,d,e
להציב x=-1 ולהשוות את הפולינום לאפס
אחר כך לגזור פעמיים, להציב X=-1 ולהשוות שוב לאפס
הגעתי לכך שהמימד הוא 3, ולפולינומים שהם אל התשובה הנכונה

אודה לעזרה
 

איייייל

New member
מה זה "התשובה הנכונה"?

נראה לי שיש כאן אינסוף תשובות אפשריות.
אם תכתוב מה הבסיס שקיבלת, אפשר יהיה לבדוק האם הוא נכון או לא (כדי ששלושת הפולינומים יהוו בסיס צריך ששלושתם יהיו שייכים למרחב, וגם שהם יהיו בלתי תלויים לינארית)
 

togi12341

New member
הוכחת טענה באלגברה לינארית (תלות לינארית)

היי,

אני צריך עזרה לגביי הוכחת ג'.

אני לא בטוח איך אפשר להוכיח את זה ישירות אז ניסיתי ע"י הנחה בשלילה.

נניח ש {u,v,z} ת"ל

==> קיים a_1 סקלר שונה מאפס
ועבור a_i מתקיים zz 2<= i <=3 zz (הכוונה ש i הוא ערך בין 2 ל -3 )

בה"כ (כי אם a_i שונה מאפס אפשר להחליף תפקידים עם a_1) נקבל:

zz a_1 *u + a_2*v + a_3*z =0 zz

נסדר את המשוואה ונחלק ב a_1 (מותר כי הוא שונה מאפס)
zz u = - (a_2/a_1)*v - (a_3/a_1)*z zz

קיבלנו ש u הוא צירוף לינארי של v ו z.

נתון ש {v,w,z} בת"ל

מכאן שקיימים סקלרים b,c,d כך שאם:
bv + cw + dz = 0
אז b=c=d=0.

אני לא מצליח למצוא את הדרך להגיע לסתירה בעזרת הנתון.
ניסיתי גם ע"י קונטרה פוזיציה אבל הסתבכתי.

אשמח לעזרה.
 

אורי769

New member
רמז

לא צריך שלילה.

מה נתון לך?
נתון ש-u,v בת"ל וש-u צירוף של v,w. כלומר קיימים a1,a2 כך ש-u=a1*v+a2*w. האם תוכל להוכיח ש-a1 ו-a2 שניהם שונים מ-0?
כמו כן נתון ש-v,w,z בת"ל. כלומר - אם b1*v+b2*w+b3*z = 0 אז b1=b2=b3=0.
מה צריך להוכיח? שאם c1*u+c2*v+c3*z = 0 אז c1=c2=c3=0.

עד כאן אני מניח (או מקווה) שלא חידשתי לך. איך ממשיכים מכאן? נניח שאתה שף. אתה פותח את המקרר ומוצא שם רק מלפפון ועגבניה. מה תכין? אין הרבה אפשרויות. גם כאן, יש לך רק שני נתונים ופשוט צריך להשתמש בהם. תציב את במקום u את הביטוי שלו כסכום של v,w ותשתמש בנתון הנוסף.
 

togi12341

New member
הבנתי, הכנתי סלט ירקות :)

שכחתי שיש לי עוד נתונים.
הבנתי אותך.

הוכחה:
נתון ש-u,v בת"ל וש-u צירוף של v,w. כלומר קיימים a1,a2 כך ש-u=a1*v+a2*w.
נתון ש-v,w,z בת"ל. כלומר - אם b1*v+b2*w+b3*z = 0 אז b1=b2=b3=0.
מה צריך להוכיח? שאם c1*u+c2*v+c3*z = 0 אז c1=c2=c3=0.

נניח ש:
c1*u+c2*v+c3*z = 0

נציב את u ונקבל:
c1*(a1*v+a2*w)+c2*v+c3*z = 0

נפתח סוגריים:
c1*a1*v+c1*a2*w+c2*v+c3*z = 0

נסדר ונקבל:

zz v(c1*a1+c2) + (c1*a2)*w +c3*z =0 zz

ומהנתון ש v,w,z בת"ל נקבל ש:
c1*a1+c2 = c1*a2 = c3 = 0

נחזור למשוואה הראשונה:
c1*u+c2*v+c3*z = 0

נציב c3=0 ונקבל
c1*u+c2*v = 0

מהנתון ש u,v בת"ל נקבל ש:
c1 = c2 = 0

מש"ל

תודה רבה אורי!
 

fortus

New member
תת חבורות

שלום לכולם
אם A הינה תת חבורה מאינדקס סופי של חבורה B
אם אני לוקח איבר a מחבורה B
האם בהכרח קיים מספר טבעי n כך ש-
a^b in A?

כאשר החבורה היא לא ציקלית?

תודה מראש
 

1ca1

New member
כן

[נתעלם מהתשובה הברורה של b=0 כמובן].

יש לך קוסטים של B מהצורה xA.
עכשיו נניח שיש לך k קוסטים כאלו.
הרבה יותר הגיוני לקרוא לאיבר ב-B בשם b אם הוא לא ב-A.
אז בקיצור אתה מסתכל על b,b^2,b...,b^(k+1).
כל אחד מהם מתאים לקוסט b^iA.
מכאן ע"פ שובך היונים, יש שני קוסטים זהים, b^iA=b^jA כלומר b^(j-i) שייך ל-AA שווה ל-A כי A תת-חבורה.
 

אורי769

New member
רמז

נניח A,B מטריצות כך שהכפל AB מוגדר. מה אתה יודע להגיד על (rank(AB?
 
למעלה