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