লেখচিত্র বর্ণনা করা

সামাজিক নেটওয়ার্ক উপস্থাপনের একটি পন্থাঃ

দুজন মানুষের নামের মধ্যকার সরলরেখার মানে হল তারা অবশ্যই একজন আরেকজনকে চেনে। যদি দুইটি নামের মধ্যে কোন সরলরেখা না থাকে, তাহলে তারা একজন আরেকজনকে চেনেনা। "একজন আরেকজনকে জানা" সম্পর্কটি উভমুখী; উদাহরণস্বরূপ, যেহেতু Audrey Gayleকে চেনে, তাহলে Gayle ও Audrey কে চেনে।

সামাজিক নেটওয়ার্ক হল একটি লেখচিত্র। লেখচিত্রের চূড়াগুলো হল নামগুলো। ( যদি তুমি শুধুমাত্র একটি চূড়া নিয়ে কথা বলেন, তাহলে এটা হল vertex।) প্রতি লাইন হল একটি কিনারা, যা দুটো চূড়াকে সংযোগ ঘটাচ্ছে। আমরা কিনারা সংযোগকারী একটি চূড়াকে $u$‍ এবং $v$‍ দিয়ে নামাঙ্কিত করলাম এবং তাদের জোড়া হল $(u,v)$‍। কারণ "একে অপরকে চেনা" সম্পর্ক উভমুখী, এই লেখচিত্রটি অনির্দিষ্ট। একটি অনির্দিষ্ট কিনারা $(u,v)$‍ হল $(v,u)$‍ এর সমান। পরবর্তীতে আমরা দেখবো নির্দিষ্ট লেখচিত্র,যেখানে চূড়াগুলোর মধ্যকার সম্পর্ক অত্যাবশ্যকীয়ভাবে উভমুখী নয়। একটি অনির্দিষ্ট লেখচিত্রে, দুইটি চূড়ার মধ্যকার কিনারা, যেমন Audrey এবং Gayle এর মধ্যকার কিনারা, দুটো চূড়ার মধ্যকার ঘটনা,এবং আমরা বলি যে একটি কিনারা দিয়ে সংযোগকৃত চূড়াগুলো হল সংলগ্ন অথবা প্রতিবেশী। একটি চূড়ায় কিনারার ঘটনাগুলো হল চূড়ার ডিগ্রী।

Audrey এবং Frank কেউ কাউকে চেনেনা। ধরা যাক Frank চাচ্ছে Audrey এর সাথে পরিচিত হতে। সে কীভাবে পরিচিত হবে? বেশ, সে Emily কে চেনে, যে চেনে Bill কে, যে চেনে Audrey কে। আমরা বললাম যে এখানে Frank এবং Audrey এর মধ্যকার তিনটি পথ আছে । আসলে, ওটা হল সবচেয়ে সরাসরি পথ Frank এর জন্য Audrey এর সাথে দেখার করার; তাদের মধ্যকার তিন কিনারা ব্যতিত আর কোন কম দূরত্বের পথ নেই। দুটো চূড়ার মধ্যকার সর্বনিম্ন কিনারাকে আমরা সর্বনিম্ন পথ বলি। আমরা সর্বনিম্ন পথটি নিচে হাইলাইট করে দিয়েছিঃ

যখন একটি পথ একটি নির্দিষ্ট চূড়া হতে গিয়ে আবার ওটাতেই ফেরত যায়, তাহলে এটাকে বলে চক্র সামাজিক চক্র অনেকগুলো চক্র ধারণ করে থাকে; তাদের একটি Audrey এর কাছ থেকে Bill এর কাছে Emily এর কাছে Jeff এর কাছে Harry এর কাছে Ilana এর কাছে গিয়ে আবার Audrey এর কাছে ফিরে এসেছে। তুলনামূলক ছোট চক্র ধারন করছে Audrey, নিচে দেখানো হল: Audrey হতে Bill এর কাছে Gayle এর কাছে এবং Audrey এর কাছে ফিরে আসলো। তুমি কোন চক্রটি খুঁজে পেলে?

কখনো কখনো আমরা কিনারায় সাংখ্যিক মান রাখি। উদাহরণস্বরূপ, সামাজিক যোগাযোগ মাধ্যমে, আমরা মানের ব্যবহার করতে পারি এটা নির্দেশ করার জন্য যে কীভাবে দুজন মানুষ একজন অন্য জনকে চিনে থাকে। আরেকটি উদাহরণ আনার জন্য, চল একটি রোড ম্যাপকে লেখচিত্রের মাধ্যমে উপস্থাপন করা যাক। ধারনা করা যাচ্ছে যে এখানে কোন একমুখী রাস্তা নেই, একটি রোড ম্যাপ একটি অনির্দিষ্ট রাস্তাও, যেখানে শহরগুলো আছে চূড়ার মতো, রোডগুলো আছে কিনারার মতো এবং কিনারার মানগুলো নির্দেশ করছে প্রত্যেকটি রাস্তার দূরত্ব। উদাহরণস্বরূপ, এখানে একটি রোড ম্যাপ আছে, মাপানুসারে নয়,ইউ এস এর উত্তরপূর্বাঞ্চলীয় কিছু আন্তঃরাজ্য হাইওয়ের কিনারার সন্নিকটের দূরত্বসহঃ

একটি সংখ্যার জন্য আমরা যে সাধারণ টার্মটি ব্যবহার করি যা আমরা একটি কিনারায় বসাই তা হল weight এবং একটি লেখচিত্র যার কিনারায় ওজন আছে তাকে বলা হয় weighted graph। রোড ম্যাপের ক্ষেত্রে, দুইটি অবস্থানের মধ্যে যাওয়ার জন্য সবচেয়ে ছোট পথটি যদি তুমি খুঁজে বের করতে চাও, তোমাকে তাহলে এমন একটি পথ খুঁজে বের করতে হবে যার মধ্যে দুইটি শীর্ষবিন্দু রয়েছে এবং সবগুলো পথের শীর্ষবিন্দুর মধ্যে প্রান্তবিন্দুর মান সবচেয়ে কম। মানবিহীন লেখচিত্রের জন্য, এরকম একটি পথকে আমরা সবচেয়ে ছোট পথ বলে থাকি। উদাহরণস্বরূপ,লেখচিত্রের সবচেয়ে ছোট রাস্তাটি হল নিউইয়র্ক হতে কনকর্ড যাবার পথটি যা নিউইয়র্ক হতে নিউহাভেন হতে হার্টপোর্ট হতে স্টারব্রিজ হতে ওয়েস্টোন হতে রিডিং হয়ে কনকর্ড পৌঁছায়,সর্বমোট 289 মাইল।

চূড়াগুলোর মধ্যকার দূরত্ব সবসময় উভমুখী নয়। রোড মাপে,উদাহরণস্বরূপ একমুখি রাস্তাও থাকতে পারে। অথবা এখানে একটি লেখচিত্র আছে যা দেখাচ্ছে আইস হকির একজন গোলকিপার কীভাবে পোশাক পরিধিত হবে:

এখন প্রান্তবিন্দুর ক্ষেত্রে, যে প্রান্তবিন্দুগুলো অ্যারো চিহ্ন দিয়ে নির্দেশ করা হয়েছে, সেগুলো হল দিকনির্দেশক এবং তাহলে আমাদের কাছে একটি দিকনির্দেশক লেখচিত্র আছে। এখানে, দিক নির্দেশকটি আমাদের দেখাচ্ছে যে অন্যান্য উপাদানগুলো ব্যবহার করার পূর্বে কোন উপাদানগুলো এখানে ব্যবহার করতে হবে। উদাহরণস্বরূপ, চেস্ট প্যাড থেকে সোয়েটারের দিকে যাওয়া প্রান্তবিন্দুটি এটাই নির্দেশ করে যে চেস্ট প্যাড অবশ্যই সোয়েটারের আগে রাখতে হবে। শীর্ষবিন্দুর পাশে থাকা সংখ্যা উপকরণে রাখস্র মত অনেকগুলো সম্ভাব্য ক্রমের মধ্যে একটি ক্রম প্রকাশ করছে, যাতে সম্ভাব্য ক্রমটি যেমন প্রথমে নিচে পরার পোশাকটি যাবে, তারপরে মোজা, তারপরে প্যান্ট এভাবে শেষ পর্যন্ত ক্রমটি যাবে। তুমি হয়তো এখানে খেয়াল করে দেখবে যে নির্দিষ্ট এই লেখচিত্রে কোন চক্র নেই; আমরা এই ধরনের একটি লেখচিত্রকে দিকনির্দেশক অ্যাসিলিক লেখচিত্র অথবা ড্যাগও বলতে পারি। অবশ্যই, আমাদের কাছে মানসহ দিকনির্দেশক লেখচিত্র আছে, যেমন রোড ম্যাপ যেখানে একমুখী রাস্তার নির্দেশ এবং পথের দূরত্ব উল্লেখ করা আছে।

দিকনির্দেশক প্রান্তবিন্দুর জন্য আমরা ভিন্ন পরিভাষা ব্যবহার করে থাকি। আমরা এখানে বলতে পারি যে একটি দিকনির্দেশক প্রান্তবিন্দু, একটি শীর্ষবিন্দু রেখে যায় এবং অন্য আরেকটির ভিতরে প্রবেশকরে। উদাহরণস্বরূপ, একদিকে নির্দেশিত প্রান্তবিন্দু চেস্ট প্যাডের শীর্ষবিন্দু থেকে বের হয়ে সোয়েটারের শীর্ষবিন্দুর মধ্যে প্রবেশ করছে। যদি দিকনির্দেশক একটি প্রান্তবিন্দু শীর্ষবিন্দু $u$‍ থেকে বের হয়ে শীর্ষবিন্দু $v$‍ এর ভিতরে প্রবেশ করে, আমরা এটাকে $(u,v)$‍ দিয়ে চিহ্নিত করব এবং শীর্ষবিন্দুর ক্রম জোড়াতে থাকা এখানে বেশ গুরুত্বপূর্ণ। একটি শীর্ষবিন্দু থেকে কতগুলো প্রান্তবিন্দু বের হয়ে আসছে তার সংখ্যা হল আউট-ডিগ্রি এবং একটি শীর্ষবিন্দুতে কতগুলো প্রান্তবিন্দু প্রবেশ করছে তার সংখ্যাটি ইন-ডিগ্রি।

তুমি হয়তো এখানে ধারণা করতে পারবে যে, লেখচিত্র—দিকনির্দেশক এবং অদিকনির্দেশক উভয়—ধরনের লেখচিত্রের জন্য বাস্তব বিশ্বে অনেক ধরনের অ্যাপ্লিকেশন রয়েছে।

যখন আমরা লেখচিত্র নিয়ে কাজ করব, শীর্ষবিন্দুর সেট এবং প্রান্তবিন্দুর সেট নিয়ে কথা বলা বেশ সাহায্য করে থাকে। সাধারনত আমরা $V$‍ দিয়ে শীর্ষবিন্দু এবং $E$‍ দিয়ে প্রান্তবিন্দু চিহ্নিত করে থাকি। যখন আমরা লেখচিত্রে একটি অ্যালগোরিদম প্রকাশ করব অথবা লেখচিত্রে একটি অ্যালগোরিদম রান করব, মাঝে মধ্যে আমরা এ্যাসিম্প্টোটিক নোটেশানে শীর্ষবিন্দুর আকার এবং প্রান্তবিন্দুর সেট ব্যবহার করতে চাইব। উদাহরণস্বরূপ, মনে করা যাক আমরা এখানে রান করার একটি সময় নিয়ে কথা বলতে চাইছি যেটা হল শীর্ষবিন্দুর সংখ্যার লিনিয়ার। যথাযথভাবে বললে, আমরা এখানে বলতে পারি যে সেটের আকারটি চিহ্নিত করার জন্য $\mathrm{\Theta }(|V|)$‍, $|\cdot |$‍ চিহ্নটি ব্যবহার করছে। কিন্তু এ্যাসিম্প্টোটিক নোটেশানে, সেট-সাইজ নোটেশন ব্যবহার করা বেশ অসুবিধাজনক এবং তাই আমরা এ্যাসিম্প্টোটিক নোটেশানের নিয়ম-কানুনগুলো এখানে নিয়ে আসব এবং শুধুমাত্র এ্যাসিম্প্টোটিক নোটেশানে, আমরা সেট-সাইজ নোটেশনটি নিয়ে কাজ করা বাদ দিয়ে দিব যাতে আমরা বুঝতে পারি যে আমরা সেট সাইজ নিয়ে কথা বলছি। তাহলে, $\mathrm{\Theta }(|V|)$‍ লেখার পরিবর্তে, আমরা এখানে শুধু লিখতে পারি $\mathrm{\Theta }(V)$‍। একইরকমভাবে, $\mathrm{\Theta }(\lg |E|)$‍ লেখার পরিবর্তে, আমরা এখানে লিখব $\mathrm{\Theta }(\lg E)$‍।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।