Algebraic graph theory
বীজগাণিতিক গ্রাফ তত্ত্ব হল গণিতের একটি শাখা যেখানে বীজগাণিতিক পদ্ধতিগুলি গ্রাফ সম্পর্কিত সমস্যাগুলিতে প্রয়োগ করা হয়। এটি জ্যামিতিক, সমন্বিত বা অ্যালগরিদমিক পদ্ধতির বিপরীতে। বীজগাণিতিক গ্রাফ তত্ত্বের তিনটি প্রধান শাখা রয়েছে, যার মধ্যে রৈখিক বীজগণিতের ব্যবহার, গোষ্ঠী তত্ত্বের ব্যবহার এবং গ্রাফের অপরিবর্তনীয়তার অধ্যয়ন জড়িত। বীজগাণিতিক গ্রাফ তত্ত্বের শাখাগুলি রৈখিক বীজগণিত ব্যবহার করে বীজগাণিতিক গ্রাফ তত্ত্বের প্রথম শাখায় রৈখিক বীজগণিতের সাথে সম্পর্কিত গ্রাফগুলির অধ্যয়ন জড়িত। বিশেষত, এটি সংলগ্ন ম্যাট্রিক্সের বর্ণালী বা একটি গ্রাফের ল্যাপলেসিয়ান ম্যাট্রিক্স অধ্যয়ন করে (বীজগাণিতিক গ্রাফ তত্ত্বের এই অংশটিকে বর্ণালী গ্রাফ তত্ত্বও বলা হয়)। উদাহরণস্বরূপ, পিটারসেন গ্রাফের জন্য, সংলগ্ন ম্যাট্রিক্সের বর্ণালী হল (−2, −2, −2, −2,1,1,1,1,3)। বেশ কয়েকটি উপপাদ্য বর্ণালীর বৈশিষ্ট্যগুলিকে অন্যান্য গ্রাফ বৈশিষ্ট্যের সাথে সম্পর্কিত করে। একটি সহজ উদাহরণ হিসাবে, ডি ব্যাস সহ একটি সংযুক্ত গ্রাফের বর্ণালীতে কমপক্ষে ডি + 1 স্বতন্ত্র মান থাকবে। নেটওয়ার্কগুলির সমন্বয়যোগ্যতা বিশ্লেষণে গ্রাফ বর্ণালীর দিকগুলি ব্যবহার করা হয়েছে। বীজগাণিতিক গ্রাফ তত্ত্বের দ্বিতীয় শাখায় গ্রুপ তত্ত্ব, বিশেষত অটোমরফিজম গ্রুপ এবং জ্যামিতিক গ্রুপ তত্ত্বের সাথে সম্পর্কিত গ্রাফের অধ্যয়ন জড়িত। প্রতিসাম্যের উপর ভিত্তি করে গ্রাফের বিভিন্ন পরিবারের উপর দৃষ্টি নিবদ্ধ করা হয় (যেমন প্রতিসম গ্রাফ, ভার্টেক্স-ট্রানজিটিভ গ্রাফ, প্রান্ত-ট্রানজিটিভ গ্রাফ, দূরত্ব-ট্রানজিটিভ গ্রাফ, দূরত্ব-নিয়মিত গ্রাফ এবং দৃঢ়ভাবে নিয়মিত গ্রাফ) এবং এই পরিবারগুলির মধ্যে অন্তর্ভুক্তির সম্পর্কের উপর। এই ধরনের কয়েকটি বিভাগের গ্রাফ এতটাই বিরল যে গ্রাফের তালিকা তৈরি করা যেতে পারে। ফ্রুক্টের উপপাদ্য অনুসারে, সমস্ত গোষ্ঠীকে একটি সংযুক্ত গ্রাফের অটোমরফিজম গ্রুপ হিসাবে উপস্থাপন করা যেতে পারে (প্রকৃতপক্ষে, একটি ঘন গ্রাফের)। গোষ্ঠী তত্ত্বের সাথে আরেকটি সংযোগ হল যে, যে কোনও গোষ্ঠীর ক্ষেত্রে, কাইলি গ্রাফ নামে পরিচিত প্রতিসম গ্রাফ তৈরি করা যেতে পারে এবং এগুলির গোষ্ঠীর কাঠামোর সাথে সম্পর্কিত বৈশিষ্ট্য রয়েছে। বীজগাণিতিক গ্রাফ তত্ত্বের এই দ্বিতীয় শাখাটি প্রথমটির সাথে সম্পর্কিত, কারণ একটি গ্রাফের প্রতিসাম্য বৈশিষ্ট্যগুলি তার বর্ণালীতে প্রতিফলিত হয়। বিশেষত, পিটারসেন গ্রাফের মতো একটি অত্যন্ত প্রতিসম গ্রাফের বর্ণালীর কয়েকটি স্বতন্ত্র মান রয়েছে (পিটারসেন গ্রাফের 3 রয়েছে, যা তার ব্যাসের পরিপ্রেক্ষিতে সর্বনিম্ন সম্ভাব্য)। কাইলি গ্রাফের জন্য, বর্ণালী সরাসরি গোষ্ঠীর কাঠামোর সাথে সম্পর্কিত হতে পারে, বিশেষ করে এর অপরিবর্তনীয় অক্ষরগুলির সাথে। পরিশেষে, বীজগাণিতিক গ্রাফ তত্ত্বের তৃতীয় শাখাটি গ্রাফের অপরিবর্তনীয়গুলির বীজগাণিতিক বৈশিষ্ট্য এবং বিশেষত ক্রোমাটিক পলিনোমিয়াল, টুটে পলিনোমিয়াল এবং গিঁট অপরিবর্তনীয়গুলির সাথে সম্পর্কিত। উদাহরণস্বরূপ, একটি গ্রাফের ক্রোমাটিক পলিনোমিয়াল তার সঠিক শীর্ষ রঙের সংখ্যা গণনা করে। পিটারসেন গ্রাফের জন্য, এই বহুপদীটি হল। বিশেষত, এর অর্থ হল যে পিটারসেন গ্রাফটি এক বা দুটি রঙের সাথে সঠিকভাবে রঙ করা যায় না, তবে 3 টি রঙের সাথে 120 টি ভিন্ন উপায়ে রঙ করা যেতে পারে। বীজগাণিতিক গ্রাফ তত্ত্বের এই ক্ষেত্রে অনেক কাজ চার রঙের উপপাদ্য প্রমাণ করার প্রচেষ্টার দ্বারা অনুপ্রাণিত হয়েছিল। যাইহোক, এখনও অনেক উন্মুক্ত সমস্যা রয়েছে, যেমন একই ক্রোমাটিক পলিনোমিয়ালযুক্ত গ্রাফগুলি চিহ্নিত করা এবং কোন পলিনোমিয়ালগুলি ক্রোমাটিক তা নির্ধারণ করা। আরও দেখুন বর্ণালী গ্রাফ তত্ত্ব বীজগাণিতিক সমন্বয় বীজগাণিতিক সংযোগ ডুলমেজ-মেন্ডেলসন পচন গ্রাফ সম্পত্তি অ্যাডজাসেন্সি ম্যাট্রিক্স রেফারেন্স। বাইরের লিঙ্ক