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

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

شاخه‌های نظریه گراف جبری

با استفاده از جبر خطی

شاخهٔ اول نظریه گراف جبری شامل مطالعه گراف‌ها با استفاده از جبر خطی است که آن را مطالعه طیف ماتریس مجاورت، یا ماتریس لاپلاس از یک گراف (این بخش از نظریه گراف جبری نظریه گراف طیفی نیز نامیده می‌شود) می‌نامند. برای گراف پترسن، برای مثال، طیف ماتریس مجاورت برابر با (۳, ۱, ۱, ۱, ۱, ۱, ۲-, ۲-, ۲-, ۲-) است.

با استفاده از نظریه گروه

شاخهٔ دوم نظریه گراف جبری شامل مطالعه گراف در ارتباط با نظریه گروه، به خصوص گروه آتومورفیزم (automorphism groups) و نظریه گروه هندسی (Geometric group theory) است.

بررسی ویژگیهای گراف

در نهایت، سومین شاخه از گراف جبری مربوط به نظریهٔ ویژگی‌های جبری گراف، به خصوص چند جمله‌ای رنگی یا چند جمله‌ای کروماتیک (Chromatic polynomial)، چند جمله‌ای تآت (Tutte polynomial)و ویژگی‌های گره (Knot invariant) است. چند جمله‌ای رنگی از یک گراف، شمارش تعداد رنگهای راس‌های مناسب آن است. برای گراف پترسون، این چند جمله‌ای به گونهٔ زیر است: ${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$