מספר לובאס

בתורת הגרפים, מספר לובאס של גרף הוא מספר ממשי המהווה חסם עליון על קיבולת שאנון של הגרף. הוא ידוע גם כפונקציית תטא של לובאס ומסומן בדרך כלל על ידי <math>\vartheta(G)</math>, תוך שימוש בצורת כתיב זו של האות היוונית תטא כדי להבדיל אותו מהתטא הגדולה המשמשת לקיבולת שאנון. גודל זה הוצג לראשונה על ידי לסלו לובאס במאמרו משנת 1979.

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

הַגדָרָה

יהי <math>G=(V,E)</math> גרף על <math>n</math> צמתים. קבוצה סדורה של <math>n</math> וקטורי יחידה <math>U=(u_i\mid i\in V)\subset\mathbb{R}^N</math> נקרא ייצוג אורתונורמלי של <math>G</math> ב <math>\mathbb{R}^N</math>, אם <math>u_i</math> ו <math>u_j</math> אורתוגונליים בכל פעם שהצמתים <math>i</math> ו <math>j</math> אינם סמוכים ב <math>G</math>: <math display="block">

u_i^\mathrm{T} u_j =
\begin{cases}
1, & \text{if }i = j, \\
0, & \text{if }ij \notin E.
\end{cases}

</math>לכל גרף קיים ייצוג אורתונורמלי עם <math>N=n</math>: ניתן לייצג את הצמתים על ידי וקטורי הבסיס הסטנדרטי של <math>\mathbb{R}^N</math> . בהתאם למבנה הגרף, ייתכן שניתן יהיה לקחת <math>N</math> קטן משמעותית ממספר הקודקודים <math>n</math> .

מספר לובאס <math>\vartheta</math> של גרף <math>G</math> מוגדר כך: <math display="block">

\vartheta(G) = \min_{c, U} \max_{i \in V} \frac{1}{(c^\mathrm{T} u_i)^2},

</math> כאשר <math>c</math> הוא וקטור יחידה ב-<math>\mathbb{R}^N</math>, ו-<math>U</math> הוא ייצוג אורתונורמלי של <math>G</math> ב <math>\mathbb{R}^N</math>. המינימום נלקח באופן משתמע גם על פני הממד <math>N</math>, אולם ללא הגבלת הכלליות די לשקול את המקרה בו <math>N=n</math>. באופן אינטואיטיבי, זה מתאים לבחירת המינימום של חצי-הזווית של חרוט המכיל את כל הווקטורים המייצגים ייצוג אורתונורמלי של <math>G</math>. אם הזווית האופטימלית היא <math>\phi</math>, אז <math>\vartheta(G)=1/\cos^2\phi</math> ו-<math>c</math> מתאים לציר הסימטריה של החרוט.

הגדרות שקולות

יהי <math>G=(V,E)</math> גרף בעל <math>n</math> צמתים. תהי <math>A</math> מטריצה שנבחרת מתוך מטריצות סימטריות בגודל <math>n\times n</math>, כך ש <math>a_{ij}=1</math> בְּכָל פַּעַם ש-<math>i=j</math> או שהצמתים <math>i</math> ו-<math>j</math> אינם סמוכים, ויהי <math>\lambda_{\max}(A)</math> הערך העצמי הגדול ביותר של <math>A</math>. דרך חלופית לחישוב מספר לובאס של <math>G</math> הוא כדלקמן: <math display="block">

\vartheta(G) = \min_A \lambda_{\max}(A).

</math>

השיטה הבאה היא דואלית לקודמתה. <math>B</math> טווח על פני הכל <math>n\times n</math> מטריצות סימטריות חיוביות למחצה כך ש-<math>b_{ij}=0</math> בכל פעם שהצמתים <math>i</math> ו-<math>j</math> שכנים, וכך שהעקבה (סכום הערכים האלכסוניים) של <math>B</math> היא <math>\operatorname{Tr}(B)=1</math>. נגדיר את <math>J</math> להיות מטריצה של אחדות בגודל <math>n\times n</math>. אז <math display="block">

\vartheta(G) = \max_B \operatorname{Tr}(BJ).

</math>נשים לב כי <math>\operatorname{Tr}(BJ)</math> הוא פשוט סכום כל הערכים של <math>B</math>.

ניתן לחשב את מספר לובאס גם במונחים של הגרף המשלים <math>\bar G</math>. יהי <math>d</math> להיות וקטור יחידה ו-<math>U=(u_i\mid i\in V)</math> ייצוג אורתונורמלי של <math>\bar G</math>. אזי: <math display="block">

\vartheta(G) = \max_{d,U} \sum_{i \in V} (d^\mathrm{T} u_i)^2.

</math>

ערך עבור גרפים ידועים

מספר לובאס חושב עבור הגרפים הבאים:

גרָף	מספר לובאס
הגרף המלא	<math> \vartheta(K_n) = 1 </math>
הגרף הריק	<math> \vartheta(\bar{K}_n) = n </math>
גרף המחומש	<math> \vartheta(C_5) = \sqrt{5} </math>
מעגל כללי	<math> \vartheta(C_n) = \begin{cases} \frac{n \cos(\pi/n)}{1 + \cos(\pi/n)} & \text{for odd } n, \\ \frac{n}{2} & \text{for even } n \end{cases} </math>
גרף פיטרסן	<math> \vartheta(KG_{5,2}) = 4 </math>
גרפי קנזר	<math> \vartheta(KG_{n,k}) = \binom{n-1}{k-1} </math>
גרפים מרובי חלקים מלאים	<math> \vartheta(K_{n_1,\dots,n_k}) = \max_{1 \leq i \leq k} n_i </math>

תכונות

נגדיר את <math>G \boxtimes H</math> בתור גרף המכפלה החזקה של הגרפים <math>G</math> ו-<math>H</math>, אז: <math display="block"> \vartheta(G \boxtimes H) = \vartheta(G) \vartheta(H) </math>

אִם <math>\bar G</math> הוא המשלים של <math>G</math>, אז: <math display="block"> \vartheta(G) \vartheta(\bar{G}) \geq n </math> כאשר שוויון מתקיים אם <math>G</math> הוא טרנזיטיבי בצמתים.

"משפט הסנדוויץ'" של לובאס

"משפט הסנדוויץ'" של לובאס קובע שמספר לובאס תמיד נמצא בין שני הגדלים הבאים, שהם NP-שלמים לחישוב: <math display="block"> \omega(G) \leq \vartheta(\bar{G}) \leq \chi(G), </math>כאשר <math>\omega(G)</math> הוא גודל הקליק המקסימלי ו-<math>\chi(G)</math> הוא המספר הכרומטי של <math>G</math> (מספר הצבעים הקטן ביותר הדרוש לצביעת קודקודי <math>G</math> כך ששני קודקודים סמוכים לא יקבלו את אותו הצבע).

הערך של <math>\vartheta(G)</math> ניתן לנסח כתוכנית חיובית למחצה, ולקרב אותה באופן נומרי בשיטת האליפסואיד בזמן המוגבל על ידי פולינום במספר הקודקודים של G. עבור גרפים מושלמים, המספר הכרומטי שווה לגודל הקליק המקסימלי, ולכן שניהם שווים ל-<math>\vartheta(\bar{G})</math>. על ידי חישוב קירוב של <math>\vartheta(\bar{G})</math> ולאחר מכן עיגול לערך השלם הקרוב ביותר, ניתן לחשב את המספר הכרומטי ומספר הקליקות של גרפים אלה בזמן פולינומי.

קשר לקיבולת שאנון

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

קיבולת שאנון של הגרף <math>G</math> מוגדרת כך: <math display="block">

\Theta(G)
= \sup_k \sqrt[k]{\alpha(G^k)}
= \lim_{k \rightarrow \infty} \sqrt[k]{\alpha(G^k)},

</math>כאשר <math>\alpha(G)</math> הוא גודל הקבוצה הבלתי תלויה המקסימלית של הגרף <math>G</math>, ו-<math>G^k</math> הוא גרף המכפלה החזקה של <math>G</math> עם עצמו <math>k</math> פעמים (המייצג שליחה של מחרוזת סמלים באורך <math>k</math> דרך הערוץ). ברור כי <math>\Theta(G)\ge\alpha(G)</math>, ומצד שני מספר לובאס מספק גבול עליון על קיבולת שאנון של הגרף:<math display="block"> \alpha(G) \leq \Theta(G) \leq \vartheta(G). </math>

קובץ:Cycle graph C5.png

גרף המחומש

נניח כי גרף הבלבול של ערוץ תקשורת הוא <math>C_5</math>, כלומר המחומש. מאז המאמר המקורי של שאנון הייתה זו בעיה פתוחה לקבוע את הקיבולת <math>\Theta(C_5)</math>. באמצעות חישוב מספר לובאס, לאסלו לובאס מצא כי <math>\Theta(C_5)=\sqrt5</math>.

שימוש בפיזיקה קוונטית

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

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

• מספר לובאס, באתר MathWorld (באנגלית)