זרימות ברשת...

[nocgod]

זרימות ברשת...

זה קצת לא קשור לנושא הפורום אבל בכל זאת...
תהי רשת N וזרימות f ו g ברשת N.
נגדיר פונקציה h לכל צלע (u,v) ככה:
h(u,v) = f(u,v) - g(u,v)

החיכו או הפריכו h היא זרימה על f.

לדעתי היא לא אבל אני לא מצליח להוכיח את זה (או למצוא דוגמא נגדית לצורך העניין)

עזרה...?

 

[טרול המתכנן]

Well if the flow capacity is defined

To satisfy f(e) >= 0, as it should be (but not always stated for some reason) - a counter example is trivial

 

[טרול המתכנן]

The word 'capacity' should be dropped

 

[nocgod]

well actually

a flow could be negative since once i flow x from u to v i flow -x from v to u as well
this is the skew symmetry part of flows... i think I proved it, and my lecturer said the math seems solid...

thanks though

 

[טרול המתכנן]

In short, that's not correct

In general, one cannot reach correct results using sound math, if started with correct assumptions and definitions


So either:

1. The math isn't sound.
2. The assumptions/definitions are OR of your teachers.

 

[טרול המתכנן]

should say *incorrect* z

 

[selalerer]

correctless

 

[nocgod]

למען האמת...

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

אגב אתה שולל תשובה של מישהו מבלי לראות אותה...אהבתי...מצד שני אתה טרול...

 

[bmno]

מרפרוף קל ייתכן שזה לא נכון

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

 

[bmno]

*לא אחד מיותר

 

[nocgod]

בגדול אתה צודק...זה לא נכון...

לפי מה שהמרצים אמרו שבגלל שאפשר להזרים זרימה שלילית אז קל מאוד להראות שעל צלע (u,v) עם קיבול 3, בזרימה f מזרימים 2 ובזרימה g מזרימים 2- אז קל לראות ש f-g נותן 4...שזה מעל לקיבול על הצלע כלומר אילוץ הקיבול לא נשמר...

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

 

[bmno]

ע"פ ההגדרה של זרימה חייב להיות אפשרי זרימה

שלילית בהינתן קיום של זרימה חיובית (לפי התנאי של הסימטריות). אם לא היינו מאפשרים זרימה שלילית, אז הכל היה 0.
בנוגע להבנה אינטואיטיבית של העניין של השליליות, יש הסבר קטן בערך בויקיפדיה:
http://he.wikipedia.org/wiki/רשת_זרימה

בכל אופן אם לא מצליחים לתפוס את המהות של מצבים מסויימים, תמיד כדאי להתעלם מהמשמעות ולהתמקד בהגדרה המתמטית גרידה (לפחות עד אחרי המבחן

).

מקווה שהלך טוב במבחן, ושיהיה בהצלחה.

 

[nocgod]

למען האמת הלך טוב

טפו טפו טפו... תמיד אפשר יותר טוב...