שאלה באלגוריתמים
(G=(V,E גרף לא מכוון עם פונקציית משקל אי-שלילית w:E-->R שמוגדרת על קשתותיו.
תאר אלגוריתם יעיל ככל האפשר למציאת קבוצת קשתות 'E שסכום משקליהן מינימלי, כך שבגרף שמתקבל מ-G ע"י זריקת קשתות 'E, אין מעגלים.
שאלה:
האם כאשר אני מוצא עץ פורש מינימלי/מקסימלי של גרף, מובטח לי שבמידה ויש מעגלים בגרף, אז עבור כל מעגל C תיהיה לפחות צלע אחת e in C
כך ש e שייכת לקבוצת הצלעות של העץ הפורש?
אם כן, מה ההסבר לכך? (האמת שזו שאלה שצצה אצלי כבר יותר מפעם אחת ולכן חשוב לי במיוחד לדעת מה ההסבר לכך. במידה וזה נכון).
ולגבי השאלה המקורית:
נניח שאני רוצה ללכת על פתרון כזה:
נמצא עץ פורש מקסימלי T לגרף G.
כעת, במידה והתשובה לשאלה הקודמת היא כן, אז בהכרח אם אסתכל על קבוצת הצלעות של הגרף G, שאינן שייכות לקבוצת הצלעות של העץ הפורש T (נסמן אותה ב-'E), הרי שמדובר בקבוצת צלעות ללא מעגלים (כי במידה והיו מעגלים בגרף, אז מכל מעגל יש לפחות צלע אחת ששייכת לעץ הפורש המקסימלי T).
אם נזרוק את צלעות 'E מהגרף, אז הגרף שנקבל הוא פשוט העץ הפורש המקסימלי T. מאחר וזהו עץ, כמובן שאין בו מעגלים.
אם סכום משקלי הקשתות של 'E הוא x.
מי מבטיח שלא קיים אלגוריתם אחר, שמוצא קבוצת קשתות ''E שסכום משקליהן y, וגם y<x, כך שאם זורקים את קשתות הקבוצה ''E, מתקבל גרף
ללא מעגלים?
אודה על עזרתכם!
(G=(V,E גרף לא מכוון עם פונקציית משקל אי-שלילית w:E-->R שמוגדרת על קשתותיו.
תאר אלגוריתם יעיל ככל האפשר למציאת קבוצת קשתות 'E שסכום משקליהן מינימלי, כך שבגרף שמתקבל מ-G ע"י זריקת קשתות 'E, אין מעגלים.
שאלה:
האם כאשר אני מוצא עץ פורש מינימלי/מקסימלי של גרף, מובטח לי שבמידה ויש מעגלים בגרף, אז עבור כל מעגל C תיהיה לפחות צלע אחת e in C
כך ש e שייכת לקבוצת הצלעות של העץ הפורש?
אם כן, מה ההסבר לכך? (האמת שזו שאלה שצצה אצלי כבר יותר מפעם אחת ולכן חשוב לי במיוחד לדעת מה ההסבר לכך. במידה וזה נכון).
ולגבי השאלה המקורית:
נניח שאני רוצה ללכת על פתרון כזה:
נמצא עץ פורש מקסימלי T לגרף G.
כעת, במידה והתשובה לשאלה הקודמת היא כן, אז בהכרח אם אסתכל על קבוצת הצלעות של הגרף G, שאינן שייכות לקבוצת הצלעות של העץ הפורש T (נסמן אותה ב-'E), הרי שמדובר בקבוצת צלעות ללא מעגלים (כי במידה והיו מעגלים בגרף, אז מכל מעגל יש לפחות צלע אחת ששייכת לעץ הפורש המקסימלי T).
אם נזרוק את צלעות 'E מהגרף, אז הגרף שנקבל הוא פשוט העץ הפורש המקסימלי T. מאחר וזהו עץ, כמובן שאין בו מעגלים.
אם סכום משקלי הקשתות של 'E הוא x.
מי מבטיח שלא קיים אלגוריתם אחר, שמוצא קבוצת קשתות ''E שסכום משקליהן y, וגם y<x, כך שאם זורקים את קשתות הקבוצה ''E, מתקבל גרף
ללא מעגלים?
אודה על עזרתכם!
