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

৬টি শীর্ষবিন্দু ও ৭টি ধারবিশিষ্ট একটি লেবেলকৃত গ্রাফ

বাস্তব জীবনের বিভিন্ন সমস্যা গ্রাফের সাহায্যে সমাধান করা যায়। উদাহরণ স্বরুপ প্রতিটি শহরকে নোড হিসাবে কল্পনা করে এবং তাদের মধ্যকার রাস্তাকে এজ কল্পনা করে এক শহর থেকে অন্য শহরে যাবার সব থেকে ছোট পথ নির্ণয় করতে যায়। এভাবে বিভিন্ন সমস্যাকে গ্রাফে নোড এবং এজ হিসাবে "মডেলিং" করে অনেক সমস্যা সমাধান করা যায়।

গণিতবিদ লিওনার্দ ইউলারকে গ্রাফ তত্বের জনক বলা হয়। ১৭৭৬ সালে তিনি "Seven Bridges of Königsberg" নামক একটি পেপার প্রকাশ করেন।

বহিঃসংযোগ

সম্পাদনা