1 of 58

רקורסיות

צביקה ברגר

תגבור אלגוריתמים - 3

MST

צביקה ברגר

בס"ד

2 of 58

MST – עץ פורש מינימאלי

  • עץ פורש מינימליMinimum spanning tree) ) הוא עץ המורכב מתת-קבוצה של קשתות בגרף נתון ומקיים את התכונות:
    1. פורש את הגרף - כלומר, כולל את כל הצמתים בגרף.
    2. סכום משקלי הקשתות שלו מינימלי, הקטן ביותר מכל העצים הפורשים של הגרף.

​

​

בס"ד

3 of 58

קרוסקל

  • האלגוריתם של קרוסקל הוא אלגוריתם חמדן לפתרון בעיית מציאת עץ פורש מינימלי בגרף ממושקל קשיר לא מכוון.
  • הרעיון: נמיין את כל הקשתות בגרף.

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

אם הגענו לכל הקודקודים נעצור.

​

  • האלגוריתם הוא חמדן, כיוון שבכל צעד נבחרת הפעולה הנראית אופטימלית באותו שלב - נוטלים את הקשת שמשקלה הקטן ביותר.

​

בס"ד

4 of 58

קרוסקל

בס"ד

5 of 58

קרוסקל

בס"ד

6 of 58

קרוסקל

בס"ד

7 of 58

קרוסקל

בס"ד

8 of 58

קרוסקל

בס"ד

9 of 58

קרוסקל

בס"ד

10 of 58

קרוסקל

בס"ד

11 of 58

קרוסקל

בס"ד

12 of 58

Prim

  • האלגוריתם של פרים הוא אלגוריתם חמדן המשמש למציאת עץ פורש מינימלי בגרף ממושקל לא מכוון. 
  • הרעיון: האלגוריתם מתחיל את בניית העץ מקודקוד פתיחה שנבחר באופן שרירותי.

בכל צעד האלגוריתם מוסיף לעץ את הצלע בעלת המשקל המינימלי מבין אלה היוצאות מקודקודי העץ ולא סוגרות מעגל.

בס"ד

13 of 58

Prim

בס"ד

14 of 58

Prim

בס"ד

15 of 58

Prim

בס"ד

16 of 58

Prim

בס"ד

17 of 58

Prim

בס"ד

18 of 58

Prim

בס"ד

19 of 58

סיכום

בס"ד

20 of 58

Question 1

בס"ד

21 of 58

מבחן 2020 מועד א

בס"ד

22 of 58

פתרון

בס"ד

23 of 58

Question 2

בס"ד

24 of 58

מבחן 2016 מועד א

בס"ד

25 of 58

פתרון

בס"ד

26 of 58

Question 3

בס"ד

27 of 58

מבחן 2012 מועד א

בס"ד

28 of 58

פתרון

בס"ד

29 of 58

Question 4

בס"ד

30 of 58

מבחן 2014 קיץ מועד א

בס"ד

31 of 58

פתרון

בס"ד

32 of 58

Question 5

בס"ד

33 of 58

מבחן 2019 מועד ב

בס"ד

34 of 58

פתרון

בס"ד

35 of 58

פתרון

בס"ד

36 of 58

Question 6

בס"ד

37 of 58

מבחן 2021 סמסטר א מועד ב

בס"ד

38 of 58

פתרון

בס"ד

39 of 58

Question 7

בס"ד

40 of 58

מבחן 2018 מועד א

בס"ד

41 of 58

פתרון

בס"ד

42 of 58

Question 8

בס"ד

43 of 58

מבחן 2018 מועד ב

בס"ד

44 of 58

פתרון

בס"ד

45 of 58

פתרון

בס"ד

46 of 58

Question 9

בס"ד

47 of 58

מבחן 2017 מועד ב

בס"ד

48 of 58

פתרון

בס"ד

49 of 58

Question 10

בס"ד

50 of 58

מבחן 2013 מועד א

בס"ד

51 of 58

פתרון

בס"ד

52 of 58

Question 11

בס"ד

53 of 58

מבחן 2016 קיץ מועד א

בס"ד

54 of 58

פתרון

בס"ד

55 of 58

Question 12

בס"ד

56 of 58

עץ פורש מינימלי עם דרגה מזערית לקודקוד נבחר

בס"ד

57 of 58

פתרון

בס"ד

58 of 58

Questions?

בס"ד