אפשר לקבל הסבר לשאלה

[JohnnyPiloni]

אפשר לקבל הסבר לשאלה

בהינתן גרף (G=(V,E לא מכוון סופי וקשיר ופונקצית משקל שאינה חח"ע על הקשתות W:E->R (כלומר יש 2 קשתות המקבלות את אותו המשקל). הוכיחו/הפריכו: בהכרח קיימים לפחות 2 עצים פורשים מינימום.

 

[HaifaMan]

הסבר לשאלה עצמה?

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

 

[JohnnyPiloni]

צירפתי גרף

הגרף שצירפתי חוקי? אם כן, הוא שולל?

 

[HaifaMan]

לא, כי יש לו 2 עפ"מים.