אלגוריתמים
יהא (G = (V,E גרף לא מכוון וקשיר עם פונקציית משקל: +w : E -->R.
תאר אלגוריתם יעיל ככל האפשר אשר בהינתן צומת u in V, מוצא מבין העצים הפורשים המינימליים, עץ T שעבורו הדרגה של u בעץ T היא מקסימלית.
האם ניתן לבצע כאן את האלגוריתם של קרוסקל, עם שינוי קטן בשלב הראשון של קרוסקל - שלב המיון:
המיון יהיה מיון של הקשתות בסדר עולה, אלא שאם יש שתי צלעות e1,e2 , כך ש-e1 חלה ב-u ו-e2 לא חלה ב-u, אז e1 תופיע לפני e2 במיון.
מכאן ואילך, נבצע את האלגוריתם של קרוסקל בדיוק כפי שהוא.
1. האם הפתרון הזה נכון?
2. איך אני מוכיח שפתרון זה מבטיח שמבין כלל העצים הפורשמים המינימליים, נקבל כאן עץ פורש מינימלי שהדרגה של u בו, היא מקסימלית?
תודה מראש!
יהא (G = (V,E גרף לא מכוון וקשיר עם פונקציית משקל: +w : E -->R.
תאר אלגוריתם יעיל ככל האפשר אשר בהינתן צומת u in V, מוצא מבין העצים הפורשים המינימליים, עץ T שעבורו הדרגה של u בעץ T היא מקסימלית.
האם ניתן לבצע כאן את האלגוריתם של קרוסקל, עם שינוי קטן בשלב הראשון של קרוסקל - שלב המיון:
המיון יהיה מיון של הקשתות בסדר עולה, אלא שאם יש שתי צלעות e1,e2 , כך ש-e1 חלה ב-u ו-e2 לא חלה ב-u, אז e1 תופיע לפני e2 במיון.
מכאן ואילך, נבצע את האלגוריתם של קרוסקל בדיוק כפי שהוא.
1. האם הפתרון הזה נכון?
2. איך אני מוכיח שפתרון זה מבטיח שמבין כלל העצים הפורשמים המינימליים, נקבל כאן עץ פורש מינימלי שהדרגה של u בו, היא מקסימלית?
תודה מראש!