רוטר - עזרה בגרפים (מתמטיקה בדידה).

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עזרה בגרפים (מתמטיקה בדידה)."

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #15244	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15244

shay86
חבר מתאריך 13.5.06
197 הודעות, דרג אמינות חבר זה

13:32 13.06.09

עזרה בגרפים (מתמטיקה בדידה).

http://rotter.name/User_files/nor/4a3380077f554a99.jpg
הבעיה היא אני לא ממש יודע מאיפה להתחיל בכלל.
אפשר אולי הדרכה איך להתחיל פה?

תודה מראש

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אתה מניח בשלילה כי עדיין נותר רכיב קשירות יחיד,	ldan192	13.06.09 14:24	1
מי אמר שאין למשל 3 רכיבי קשירות?	Deuce	13.06.09 16:06	2
כמו רוב הטענות על עצים - באינדוקציה.	Deuce	13.06.09 16:12	3
תודה לכולם :)	shay86	13.06.09 18:06	4

ldan192
חבר מתאריך 14.9.08
95119 הודעות

14:24 13.06.09

1. אתה מניח בשלילה כי עדיין נותר רכיב קשירות יחיד,
בתגובה להודעה מספר 0

כלומר קיימת קשת אחת לפחות שמחברת בין שני הרכיבים.
==> יש מעגל בסתירה לנתון שהגרף הוא עץ.

כמובן שזה צריך להיות הרבה יותר פורמלי, אבל זו האינטואיציה.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

16:06 13.06.09

2. מי אמר שאין למשל 3 רכיבי קשירות?
בתגובה להודעה מספר 1

ערכתי לאחרונה בתאריך 13.06.09 בשעה 16:13 בברכה, Deuce

אם אתה מניח בשלילה שאין 2 רכיבי קשירות, זה לא נכון לבדוק רק את המקרה שעדיין יש לך רכיב קשירות אחד. אפשר בדרך הזאת, אבל צריך לציין את זה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

16:12 13.06.09

3. כמו רוב הטענות על עצים - באינדוקציה.
בתגובה להודעה מספר 0

מקרה הבסיס נניח שיש קשת אחד וברור שניתוק מביא לך גרף עם 0 קשתות ו-2 צמתים, כלומר 2 רכיבי קשירות.
הנחת האינדוקציה: נניח שהטענה נכונה על עץ באורך n ונראה מעבר על n+1:
יהי T עץ באורך n+1.
אתה יודע שמתקיים:
אם r שורש של עץ אז גם הבן השמאלי של r והבן הימיני של r מייצגים עץ.
נפריד לשני מקרים:
א. ניתוק קשת בין שורש לאחד מבניו - נותרים עם 2 עצים שאין ביניהם חיבור.
ב. ניתוק קשת אשר שייכת לתת העץ השמאלי או לתת העץ הימיני. בפרט תת העץ השמאלי והימיני, גובהם קטן שווה ל-n ולכן אפשר להפעיל את הנחת האינדוקציה על אחד תת העץ המתאים. ניתוק הקשת גורמת לתת העץ השמאלי נניח לאחר הניתוק להיות עם 2 רכיבי קשירות. ובלבד ניתן להגיע לתת העץ השמאלי רק דרך שורש העץ, לכן סה"כ נותרת עם 2 רכיבי קשירות.

טיפה יותר פורמלי צריך, רציתי להסביר בקצרה את הנקודה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

shay86
חבר מתאריך 13.5.06
197 הודעות, דרג אמינות חבר זה

18:06 13.06.09

4. תודה לכולם :)
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד