מספר לובאס

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

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

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

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

 הגדרות שקולות 
יהי  גרף בעל  צמתים. תהי  מטריצה שנבחרת מתוך מטריצות סימטריות בגודל , כך ש  בְּכָל פַּעַם ש- או שהצמתים  ו- אינם סמוכים, ויהי  הערך העצמי הגדול ביותר של . דרך חלופית לחישוב מספר לובאס של  הוא כדלקמן:  

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

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

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

 תכונות 
נגדיר את  בתור גרף המכפלה החזקה של הגרפים  ו-, אז:  

אִם  הוא המשלים של , אז:  כאשר שוויון מתקיים אם  הוא טרנזיטיבי בצמתים.

 "משפט הסנדוויץ'" של לובאס 
"משפט הסנדוויץ'" של לובאס קובע שמספר לובאס תמיד נמצא בין שני הגדלים הבאים, שהם NP-שלמים לחישוב: כאשר  הוא גודל הקליק המקסימלי ו- הוא המספר הכרומטי של  (מספר הצבעים הקטן ביותר הדרוש לצביעת קודקודי  כך ששני קודקודים סמוכים לא יקבלו את אותו הצבע).

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

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

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

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

קישורים חיצוניים









 הערות שוליים


קטגוריה:תורת האינפורמציה
קטגוריה:דפים עם תרגומים שלא נסקרו
קטגוריה:תורת הגרפים
קטגוריה:קומבינטוריקה
קטגוריה:אלגוריתמים בתורת הגרפים