MOR (guest) 05 Sep 2012 08:26
שלום לכולם,
השאלה היא כזו:
נתונים גרף קשיר ולא מכוון G=(V,E)
פונקציית משקל מקבוצת הקשתות לממשיים
קשת **e in E
ומספר שלם k>0
לתאר אלגוריתם יעיל ככל האפשר, שיקבע האם ניתן להסיר מהגרף לכל היותר
k קשתות
כך שהקשת e
תהיה שייכת לעץ פורש מינימלי כלשהו של הגרף שיתקבל**
הפתרון שחשבתי עליו רץ בזמן לינארי, אך אני לא בטוחה לגביו כי יש לי חור בידע לגבי קבלת רכיבי דו-קשירות ע"י האלגוריתם חיפוש לרוחב BFS
First check whether k relevant for the size of the tree ( if it will be V-1)
then we do BFS to get all thr circuits in the graph
then i Look for the circuits which e in them , and search the one with the minimum number of edges.
if e has the maximum Weight in the circuit that we found (the one that hass less edges) - we return FALSE
else we return TRUE
אוקי, אני אשמח לביקורת על הפתרון
אני פשוט לא יודעת האם כאפשר מריצים חיפוש לרוחב מקבלים את כל רכיביי הדו קשירות, כלומר את כל המעגלים, גם את הקטנים שמוכלים לפעמים בגדולים.
תודה!
