نظریه طیفی گراف‌ها

در ریاضیات، نظریه طیفی گراف‌ها مطالعه خواص یک گراف در رابطه با چندجمله‌ای مشخصه، مقادیر ویژه و بردارهای ویژه ماتریس‌های مرتبط با گراف، مانند ماتریس مجاورت آن یا ماتریس لاپلاس است.

ماتریس مجاورت یک گراف ساده بدون جهت، یک ماتریس متقارن حقیقی است و بنابراین به صورت متعامد قطری‌پذیر است. مقادیر ویژه آن اعداد جبری حقیقی هستند؛ در حالی که ماتریس مجاورت به برچسب گذاری رأس بستگی دارد، طیف آن یک ناوردا از آن دسته گراف است، اگرچه کامل نیست.

نظریه گراف طیفی همچنین به پارامترهای گراف مربوط می شود که از طریق چندگانه مقادیر ویژه ماتریس های مرتبط با گراف، مانند عدد کالین دو وردیر، تعریف می شوند.

گراف‌های هم‌طیف

اگر ماتریس‌های مجاورت گراف‌ها هم‌طیفی باشند، یعنی اگر ماتریس‌های مجاورت آن‌ها دارای مجموعه‌ای یکسان از مقادیر ویژه باشد، آن دو گراف هم‌طیفی نامیده می‌شوند.

نیازی نیست که گراف‌های هم‌طیفی، یک‌ریخت باشند، اما گراف‌های یک‌ریخت همیشه هم‌طیفی هستند.

مشخص کردن گراف با طیف آن

گراف G را مشخص توسط طیف گوییم هرگاه هر گراف دیگر هم‌طیف با G، یکریخت با G باشد.

برخی از اولین نمونه‌های خانواده گراف‌هایی که با طیف آنها تعیین می‌شوند عبارتند از:

• گراف‌های کامل
• گراف ستاره(متناهی)

جفت‌های هم‌طیف‌

به یک جفت گراف گفته می شود که هم‌طیف باشند، اما غیر یکریخت باشند.

برای مثال، کوچکترین جفت هم‌طیفی {K_1,4, C₄ ∪ K₁} است که شامل ستاره ۵-راس و اجتماع دو گراف دور ۴-راسی و گرافی تک راسی است. این جفت توسط کولاتز و سینوگوویتز در ۱۹۵۷ معرفی شده‌است.

جستارهای وابسته

• نظریه گراف جبری

مطالعه بیشتر

• Chung, Fan (1997). American Mathematical Society (ed.). Spectral Graph Theory. Providence, R. I. ISBN 0-8218-0315-8. MR 1421568[first 4 chapters are available in the website]{{cite book}}: نگهداری CS1: پست اسکریپت (link)

پیوند به بیرون

• Brouwer, Andries; Haemers, Willem H. (2011). "Spectra of Graphs" (PDF).
• Spielman, Daniel (2011). "Spectral Graph Theory" (PDF). [chapter from Combinatorial Scientific Computing]
• Spielman, Daniel (2007). "Spectral Graph Theory and its Applications". [presented at FOCS 2007 Conference]
• Spielman, Daniel (2004). "Spectral Graph Theory and its Applications". [course page and lecture notes]