חידה יפה באלגוריתמים

[nautilus7791]

חידה יפה באלגוריתמים

נתונה מטריצה ריבועית A n*n שמכילה אפסים ואחדים.נאמר שמטריצה A היא "מוזרה" אם קיים k שלם וחיובי כך ש A בחזקת k שווה לאפס,כלומר קיימת חזקה של מטריצה A שהיא מטריצה עם כל האפסים.בהינתן מטריצה A n*n יש לגלות בזמן O(n^2 האים היא מטריצה מוזרה

 

[עריסטו]

הערות

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

 

[מספר6]

../images/Emo62.gif

אפשר להתייחס למטריצה של 0 ו-1 כאל גרף מכוון. במקרה כזה, הטענה שחזקת k שלה היא 0 שקולה לטענה שאין בגרף מסלולים באורך k. מכאן נובע שאין מעגלים (כולל לולאות עצמיות וקשתות דו-כיווניות), כי על מעגל אפשר לעשות מסלול באיזה אורך שרוצים. לכן, תנאי הכרחי הוא ש-A "מוזרה" חייבת להיות גרף ללא מעגלים. זה גם תנאי מספיק, כי בגרף ללא מעגלים אין מסלולים באורך n ומעלה. לבדוק שגרף הוא חסר מעגלים אפשר לעשות ב-O(n^2)zz, למשל, ע"י DFS.

 

[מספר6]

טוב

אני רואה שהחידה כבר נפתרה...