نظرية الرسم البياني الجبرية

يتناول الفرع الأول من نظرية الرسوم البيانية الجبرية دراسة الرسوم البيانية في سياق الجبر الخطي . ويركز هذا الفرع تحديدًا على دراسة طيف مصفوفة التجاور ، أو مصفوفة لابلاس للرسم البياني (ويُطلق على هذا الجزء من نظرية الرسوم البيانية الجبرية أيضًا اسم نظرية الرسوم البيانية الطيفية ). فعلى سبيل المثال، بالنسبة لرسم بيترسن البياني ، يكون طيف مصفوفة التجاور هو (−2,  −2,  −2,  −2,  1,  1,  1,  1,  1,  3). تربط العديد من النظريات خصائص الطيف بخصائص أخرى للرسم البياني . كمثال بسيط، يحتوي الرسم البياني المتصل ذو القطر D على D + 1 قيمة مميزة على الأقل في طيفه. ^{[ 1 ]} وقد استُخدمت جوانب من أطياف الرسوم البيانية في تحليل قابلية تزامن الشبكات .

يتناول الفرع الثاني من نظرية المخططات الجبرية دراسة المخططات في سياق نظرية الزمر ، وتحديدًا زمر التماثل الذاتي ونظرية الزمر الهندسية . وينصب التركيز على عائلات مختلفة من المخططات بناءً على التناظر (مثل المخططات المتناظرة ، والمخططات المتعدية الرؤوس ، والمخططات المتعدية الحواف ، والمخططات المتعدية المسافات ، والمخططات المنتظمة المسافات ، والمخططات المنتظمة بقوة )، وعلى علاقات الاحتواء بين هذه العائلات. بعض هذه الفئات من المخططات متفرقة بما يكفي لإمكانية إنشاء قوائم بها. وبحسب نظرية فروخت ، يمكن تمثيل جميع الزمر كزمرة التماثل الذاتي لمخطط متصل (بل لمخطط مكعب ). ^{[ 2 ]} ثمة صلة أخرى بنظرية الزمر، وهي أنه عند إعطاء أي زمرة، يمكن توليد مخططات متناظرة تُعرف بمخططات كايلي ، وهذه المخططات لها خصائص مرتبطة ببنية الزمرة. ^{[ 1 ]}

يرتبط هذا الفرع الثاني من نظرية المخططات الجبرية بالفرع الأول، إذ تنعكس خصائص التناظر للمخطط في طيفه. وعلى وجه الخصوص، يحتوي طيف المخطط عالي التناظر، مثل مخطط بيترسن، على عدد قليل من القيم المميزة ^{[ 1 ]} (يحتوي مخطط بيترسن على 3، وهو الحد الأدنى الممكن بالنظر إلى قطره). أما بالنسبة لمخططات كايلي، فيمكن ربط الطيف مباشرةً ببنية المجموعة، وتحديدًا بخصائصها غير القابلة للاختزال . ^{[ 1 ] [ 3 ]}

أخيرًا، يتناول الفرع الثالث من نظرية المخططات الجبرية الخصائص الجبرية لثوابت المخططات، وخاصة متعددة الحدود اللونية ، ومتعددة حدود توت، وثوابت العقد . على سبيل المثال، تحسب متعددة الحدود اللونية للمخطط عدد تلوينات رؤوسه الصحيحة . بالنسبة لمخطط بيترسن، فإن هذه المتعددة الحدود هي${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$^{[ 1 ]} على وجه الخصوص ، هذا يعني أنه لا يمكن تلوين مخطط بيترسن بشكل صحيح بلون واحد أو لونين، ولكن يمكن تلوينه بـ 120 طريقة مختلفة باستخدام 3 ألوان. وقد استُلهمت العديد من الدراسات في هذا المجال من نظرية المخططات الجبرية من محاولات إثبات نظرية الألوان الأربعة . ومع ذلك، لا تزال هناك العديد من المشكلات المفتوحة ، مثل توصيف المخططات التي لها نفس متعددة الحدود اللونية، وتحديد أي متعددات الحدود لونية.