מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה - הגדרות/תרגילים

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים | זרימה - הגדרות

מבני נתונים ואלגוריתמים - מחברת קורס

הדף נמצא בשלבי עבודה
דף זה נמצא כעת בשלבי עריכה. הנכם מתבקשים שלא לערוך אותו בטרם תוסר הודעה זו.
במקרה שדף זה לא נערך במשך שבוע או יותר, רשאי כל משתמש להסיר הודעה זו.

תוכן עניינים

1 זרימה וקיבולים בין קבוצות
- 1.1 שאלה
- 1.2 תשובה
  - 1.2.1 1
  - 1.2.2 2
  - 1.2.3 3
  - 1.2.4 4

[עריכה] זרימה וקיבולים בין קבוצות

[עריכה] שאלה

הגדרה:

נתונים רשת זרימה וזרימה חוקית עליה. $\displaystyle X, Y, Z \subseteq V$ הן תתי-קבוצות צמתים כלשהן.

נגדיר את קיבול בין תתי-קבוצות כ $\displaystyle c_{X, Y} = \sum_{x \in X}\sum_{y \in Y}c_{x, y}$ .
נגדיר את זרימה בין תתי-קבוצות כ $\displaystyle f_{X, Y} = \sum_{x \in X}\sum_{y \in Y}f_{x, y}$ .

אנא הוכח את הכללים הבאים:

$\displaystyle f_{X, X} = 0$
$\displaystyle f_{X, Y} = -f_{Y, X}$
$\displaystyle f_{X \bigcup Y, Z} = f_{X, Z} + f_{Y, Z}$
$\displaystyle f_{Z, X \bigcup Y} = f_{Z, X} + f_{Z, Y}$

[עריכה] תשובה

[עריכה] 1

טענה זו למעשה נובעת מהטענה השנייה: אם $\displaystyle f_{X, Y} = -f_{X, Y} =$ , אז בפרט, $\displaystyle f_{X, X} = -f_{X, X}$ . אבל האפשרות היחידה לכך היא ש $\displaystyle f_{X, X} = 0$ .

$\displaystyle f_{X, Y} =$
$\displaystyle \sum_{u \in X}\sum_{v \in Y}f_{u, v} =$
$\displaystyle \sum_{u \in X}\sum_{v \in Y}-f_{v, u} =$
$\displaystyle \sum_{v \in Y}\sum_{u \in X}-f_{v, u} =$
$\displaystyle -f_{Y, X}$

[עריכה] 3

הטענה נובעת מהמעברים הבאים:

$\displaystyle f_{X \bigcup Y, Z} =$
$\displaystyle \sum_{u \in X \bigcup Y}\sum_{v \in Z}f_{u, v} =$
$\displaystyle (\sum_{u \in X} + \sum_{u \in Y})\sum_{v \in Z}f_{u, v} =$
$\displaystyle f_{X, Z} + f_{Y, Z}$