|
|
עמוד:362
. H '' : £ - > { 1 , 2 , ..., | V |} הציעו אלגוריתם יעיל ככל האפשר , שבהינתן קבוצת קשתות , Sc £ מחליט אם קיים עץ פורש מינימלי שמכיל את . 5 אם קיים עץ פורש מינימלי , האלגוריתם מוצא אותו . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 23 נתון גרף G = ( V , E ) לא מכוון ונתונה קבוצת הקשתות . 5 £ E א . הציעו אלגוריתם יעיל , שמוצא את המספר המינימלי של הקשתות , 5-מ אשר מופיע בעץ הפורש המינימלי עבור , G כלומר , מהו המספר המינימלי x קשתות 5-מ כך שבכל עץ פורש מינימלי יהיו לפחות X קשתות ! 5-מ ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 24 נתון גרף G = ( V , E ) קשיר , שפונקציית המשקל שלו : w : £ - ?/? ( שימו לב שהמשקל לקשת כלשהי אינו בהכרח חיובי . ( עבור גרף H = ( U , F ) נסמן w { H ) - 1 את משקל הגרף , כלומר . w ( H ) = £ W { e ) eeF א . בנו אלגוריתם יעיל , שמוצא תת-גרף G ' - ( V , E ) קשיר של הגרף , G ופורש את כל קדקודי , ;'' כך | -ש י W { G' ) - | £ יהיה מינימלי . ב . מהי סיבוביות זמן ריצה של האלגוריתם שהצעתם ; שאלה 6 . 25 נתון גרף G- { V , E ) לא מכוון , קשיר , שפונקציית המשקל שלו . w . V- ^ R : שימו לב , פונקציית המשקל מוגדרת על קבוצת קדקודים , V והמשקל לכל קדקוד לא בהכרח חיובי . א . הציעו אלגוריתם יעיל , המוצא עץ ז , המביא למינימום את d ( v ) -u' ( v ) כאשר ^( v ) £ היא דרגת הקדקוד v בעץ . 7 ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ?
|
|