גרף קיילי – הבדלי גרסאות

ב[[תורת החבורות]], '''גרף קיילי''' של [[חבורה (מבנה אלגברי)|חבורה]] הוא [[גרף מכוון]] וצבוע, המהווה תאור גרפי של החבורה, ומאפשר לחקור אותה בכלים גאומטריים, טופולוגיים והסתברותיים. הגרף נקרא על שם המתמטיקאי [[ארתור קיילי]].

גרף קייליהגרף אינו מוגדר עבור חבורה G בפני עצמה, אלא רק ביחס לקבוצת יוצרים שלה, S. '''גרף קיילי''' של G ביחס ל-S הוא הגרף שקודקודיו הם אברי החבורה, ולכל יוצר <math>\ s\in S</math> יש בו קשת בצבע s מכל קודקוד <math>\ g\in G</math> למכפלה <math>\ gs</math>. באופן הזה מתקבל [[גרף רגולרי|גרף מכוון רגולרי]]: מכל קודקוד יוצאות ונכנסות בדיוק |S| קשתות. באיור משמאל מוצג גרף קיילי של החבורה <math>\ A_4</math> ביחס ליוצרים <math>\ a=(12)(34)</math>, באדום, ו- <math>\ b=(123)</math>, בכחול. מקובל להשמיט את הכיוונים עבור היוצרים מסדר 2, כפי שעשינו לעיל.

בחבורות קטנות הגרף מאפשר לבצע חישובים במהירות. בגרף שלנו אפשר לחשב כי <math>\ (ab)^3=e</math>, משום שאם יוצאים מאיבר היחידה וצועדים בכיוון אדום-כחול-אדום-כחול-אדום-כחול, חוזרים לנקודת ההתחלה. אותה תוצאה נקבל מכל נקודת התחלה, דבר המדגים את מידת ה[[סימטריה]] של הגרף. אכן, [[חבורת סימטריות|חבורת הסימטריות]] של גרף קיילי צבוע היא בדיוק החבורה שאותה הוא מתאר. על הגרף אפשר להגדיר את '''מטריקת המלה''', שלפיה המרחק מקודקוד g לקודקוד h שווה למספר הקטן ביותר של יוצרים (והאיברים ההפוכים להם) הדרוש לכתיבת היחס <math>\ g^{-1}h</math>. למעשה, אפשר להפוך את הגרף ל[[מרחב גאודזי]], אם מתאימים כל קשת <math>\ g \mapsto gs</math> ל[[קטע (מתמטיקה)|קטע היחידה]] <math>\ [0,1]</math> (עם המטריקה הרגילה עליו). באופן הזה, כל גרפי קיילי של חבורה נוצרת סופית G (ביחס לכל קבוצת יוצרים סופית) הם [[קוואזי-איזומטריה|קוואזי-איזומטריים]] זה לזה, וכך מתקבל העקרון היסודי של [[תורת החבורות הגאומטרית]]: גרף קיילי הוא אינווריאנט קוואזי-איזומטרי של החבורה.