גרפים

Question 1

בגרף לא מכוון, מתי בטוח יש מעגל?

Answer 1

אם מספר הצלעות גדול או שווה למספר הקודקודים (זה לא אמ”מ)

Question 2

dfs אלגוריתם וזמן הריצה + שימושים

Answer 2

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

Question 3

BFS אלגוריתם וזמן ריצה + שימושים

Answer 3

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

Question 4

הגדרה לעץ

Answer 4

גרף קשיר חסר מעגלים

Question 5

הגדרה למסלול\מעגל אוילר

Answer 5

בגרף, מסלול\מעגל שעובר בכל צלע בדיוק פעם אחת.

Question 6

משפט מתי יש מעגל אוילר + אלגוריתם למציאתו

Answer 6

בגרף לא מכוון וקשיר יש מעגל אוילר
אמ”מ הדרגה של כל קודקוד זוגית.
בגרף מכוון, דרגה זוגית = דרגת כניסה שווה לדרגת יציאה
בגרף לא מכוון וקשיר יש מסלול אוילר אמ”מ יש בו 0 או 2 קודקודים עם דרגה אי זוגית.

Question 7

הגדרה למסלול\מעגל המילטון

Answer 7

שמבקר בכל הקודקודים פעם אחת בדיוק

Question 8

משפט מתי יש מעגל המילטון + אלגוריתם למציאות

Answer 8

אם לכל 2 קודקודים שאינם שכנים סכום דרגותם גדול שוה ל מספר הקודקודים. לא טענת אמ”מ.

Question 9

מיון טפולוגי

Answer 9

אפשר להריץ רק על גרף DAG - גרף מכוון חסר מעגלים.
נותן לנו סדר לינארי שבו לכל קשת
(u.v)
u מופיע לפני
v
האלגוריתם: נייצר רשימת צמתים ריקה. נבצע DFS ובריצצתו כאשר אנו הופכים צומת לשחור (כלומר עברנו על כל השכנים שלו) נכניס אותו לראש רשימת הצמתים.