গ্রাফ তত্ত্ব

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
৬টি শীর্ষবিন্দু (vertex) এবং ৭টি ধার (edge) সম্বলিত একটি গ্রাফ

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

ইতিহাস[সম্পাদনা]

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

তথ্যসূত্র[সম্পাদনা]

  1. Biggs, N.; Lloyd, E. and Wilson, R. (1986)। Graph Theory, 1736-1936। Oxford University Press। 
  2. Cauchy, A.L. (1813)। "Recherche sur les polyèdres - premier mémoire"। Journal de l'Ecole Polytechnique। 9 (Cahier 16): 66–86। 
  3. L'Huillier, S.-A.-J. (1861)। "Mémoire sur la polyèdrométrie"। Annales de Mathématiques 3: 169–189।