טוען...
טוען...
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.
נתון גרף G = (V,E) מכוון, המיוצג על ידי רשימת הסמיכויות הבאה:
(1) שרטטו את הגרף G המיוצג על ידי רשימת הסמיכויות.
(2) הפעילו אלגוריתם סריקה לעומק (DFS) על הגרף G החל בצומת a. סרטטו את העץ הפורש DFS.
(3) הפעילו אלגוריתם סריקה לרוחב (BFS) על הגרף G החל בצומת c. סרטטו את העץ הפורש BFS.
גרף דו-צדדי הוא גרף בו ניתן לחלק את הצמתים שבו לשתי קבוצות זרות, כך שלא קיימת קשת בין שני צמתים השייכים לאותה הקבוצה.
(1) לפניכם 2 גרפים דו צדדיים. הראו את שתי קבוצות הצמתים עבור כל גרף.
(2) לפניכם גרף שאינו דו צדדי. מהו מספר הקשתות המינימלי שיש להסיר כדי שהגרף יהיה דו צדדי? כתבו אילו קשתות יש להסיר והציגו את שתי הקבוצות.
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.
נתון גרף G = (V,E) מכוון, המיוצג על ידי רשימת הסמיכויות הבאה:
(1) שרטטו את הגרף G המיוצג על ידי רשימת הסמיכויות.
(2) הפעילו אלגוריתם סריקה לעומק (DFS) על הגרף G החל בצומת a. סרטטו את העץ הפורש DFS.
(3) הפעילו אלגוריתם סריקה לרוחב (BFS) על הגרף G החל בצומת c. סרטטו את העץ הפורש BFS.
גרף דו-צדדי הוא גרף בו ניתן לחלק את הצמתים שבו לשתי קבוצות זרות, כך שלא קיימת קשת בין שני צמתים השייכים לאותה הקבוצה.
(1) לפניכם 2 גרפים דו צדדיים. הראו את שתי קבוצות הצמתים עבור כל גרף.
(2) לפניכם גרף שאינו דו צדדי. מהו מספר הקשתות המינימלי שיש להסיר כדי שהגרף יהיה דו צדדי? כתבו אילו קשתות יש להסיר והציגו את שתי הקבוצות.