Question

spring_5_b
edge_coloring
matching

אינדקס הצביעה של גרף לא מכוון G=(V,E)G = (V, E) הוא המספר הקטן ביותר של צבעים הדרוש לצביעת כל קשתות GG כך שכל זוג קשתות בעלות צומת קצה משותף צבועות בצבעים שונים.

הוכיחו/הפריכו כל אחת מהטענות הבאות:

א. האלגוריתם החמדן הבא מוצא שידוך מקסימום בגרף דו צדדי: בוחרים קשת, מסירים את קצותיה (כולל הקשתות הנוגעות) מהגרף, חוזרים על הפעולה כל עוד נותרו קשתות.

ב. האלגוריתם החמדן הבא מחשב את אינדקס הצביעה של גרף דו צדדי: מוצאים שידוך מקסימום, מסירים את הקשתות בשידוך, חוזרים על הפעולה כל עוד יש קשתות. אינדקס הצביעה הוא מספר השידוכים שנמצאו.

1

Answers

א. הטענה לא נכונה, למשל בגרף הבא האלגוריתם החמדן עלול לבחור את הקשת האלכסונית ולסיים בעוד שקיים שידוך בגודל 2:

ב. הטענה לא נכונה, למשל בגרף הבא אינדקס הצביעה הוא 2, אבל האלגוריתם החמדן עלול לבחור את שתי הקשתות התחתונות לשידוך מקסימום הראשון וכתוצאה להחזיר 3 שידוכים:

1
Feedback