গ্রাফ তত্ত্ব

গণিতে এবং কম্পিউটার বিজ্ঞানে গ্রাফ তত্ত্ব (ইংরেজি: Graph Theory) এমন একটি বিষয় যা গ্রাফ সম্পর্কিত বিষয়াদি আলোচনা করে। "গ্রাফ" হচ্ছে কতগুলো ভার্টেক্স বা শীর্ষবিন্দুর সমষ্টি এবং কতগুলো এজ বা রেখার সমষ্টি যারা বিভিন্ন ভার্টেক্সের মধ্যে সংযোগ স্থাপন করে। গ্রাফ দিকঅনির্দেশিত বা অদিক হতে পারে যার অর্থ হচ্ছে দুটি ভার্টেক্সের সংযোজক রেখার কোন দিক নেই। দিকসংবলিত বা সদিক গ্রাফের এজগুলোর নির্দিষ্ট দিক রয়েছে। বিস্তারিত সংজ্ঞার জন্য দেখুন গ্রাফ (গণিত)।

৬টি শীর্ষবিন্দু (vertex) এবং ৭টি ধার (edge) সংবলিত একটি গ্রাফ

ইতিহাস

লিওনার্ট অয়লার কনিংসবার্গের সাত সেতু সমস্যার উপরে যে নিবন্ধ লিখেছিলেন তা ১৭৩৬ সালে প্রকাশিত হয়, এবং এটিকে গ্রাফ তত্ত্বের ইতিহাসের প্রথম প্রকাশনা হিসেবে গ্রহণ করা হয়েছে।^[১] এই নিবন্ধ এবং ভ্যান্ডারমোন্ডের নাইটের ভ্রমণ সমস্যার উপর লিখিত আরেকটি নিবন্ধে লিবনিজের দেখানো পথে গবেষণা ও বিশ্লেষণ করা হয়। এজ, ভারটেক্স এবং উত্তল পলিহেড্রনের ফেসের সংখ্যার উপর অয়লার সূত্র প্রদান করেন এবং কোশি^[২] ও এল'হুইলিয়ের^[৩] এটির ওপর গবেষণা করে সূত্রগুলোর সাধারণ বর্ণনা দেন। এভাবেই টপোলজির জন্ম হয়।