Hasse diagram
ক্রম তত্ত্বে, একটি হাস রেখাচিত্র (;) হল এক ধরনের গাণিতিক রেখাচিত্র যা একটি সসীম আংশিকভাবে ক্রমযুক্ত সেটকে তার ক্ষণস্থায়ী হ্রাসের অঙ্কনের আকারে উপস্থাপন করতে ব্যবহৃত হয়। সুনির্দিষ্টভাবে, একটি আংশিকভাবে ক্রমযুক্ত সেটের জন্য একটি সমতলে প্রতিটি উপাদানকে একটি শীর্ষ হিসাবে উপস্থাপন করে এবং একটি রেখা বিভাগ বা বক্ররেখা আঁকে যা যখনই আচ্ছাদিত হয় (অর্থাৎ, যখনই, এবং এর থেকে এবং এর সাথে কোনও পার্থক্য নেই) তখন এক শীর্ষ থেকে অন্য শীর্ষে উপরের দিকে যায়। এই বক্ররেখা একে অপরকে অতিক্রম করতে পারে তবে তাদের শেষ বিন্দু ব্যতীত অন্য কোনও শীর্ষকে স্পর্শ করা উচিত নয়। এই ধরনের একটি রেখাচিত্র, লেবেলযুক্ত শীর্ষগুলি সহ, অনন্যভাবে এর আংশিক ক্রম নির্ধারণ করে। হ্যাসি রেখাচিত্রগুলি হেলমুট হাসের (1898-1979) নামে নামকরণ করা হয়েছে; গ্যারেট বারখফের মতে, এগুলির কার্যকর ব্যবহারের কারণে এগুলি বলা হয়। যাইহোক, হাস এই চিত্রগুলি প্রথম ব্যবহার করেননি। হাসের পূর্ববর্তী একটি উদাহরণ পাওয়া যেতে পারে। যদিও হাস রেখাচিত্রগুলি মূলত হাতে আংশিকভাবে সাজানো সেটগুলির অঙ্কন করার কৌশল হিসাবে তৈরি করা হয়েছিল, তবে সম্প্রতি গ্রাফ অঙ্কন কৌশল ব্যবহার করে সেগুলি স্বয়ংক্রিয়ভাবে তৈরি করা হয়েছে। "হাস ডায়াগ্রাম" বাক্যাংশটি সেই গ্রাফের যে কোনও অঙ্কন থেকে স্বাধীনভাবে একটি বিমূর্ত নির্দেশিত অ্যাসাইক্লিক গ্রাফ হিসাবে ট্রানজিটিভ হ্রাসকেও বোঝাতে পারে, তবে এই ব্যবহারটি এখানে বাদ দেওয়া হয়েছে। যদিও হাসের রেখাচিত্রগুলি সহজ, সেইসাথে স্বজ্ঞাত, সীমাবদ্ধ অবস্থান নিয়ে কাজ করার সরঞ্জাম, তবে "ভাল" রেখাচিত্র আঁকা বরং কঠিন বলে প্রমাণিত হয়। কারণটি হল, সাধারণভাবে, একটি প্রদত্ত অবস্থানের জন্য একটি হাস রেখাচিত্র আঁকার বিভিন্ন সম্ভাব্য উপায় রয়েছে। একটি ক্রমের ন্যূনতম উপাদানগুলি দিয়ে শুরু করার এবং তারপরে ক্রমবর্ধমানভাবে বৃহত্তর উপাদানগুলি আঁকার সহজ কৌশলটি প্রায়শই বেশ খারাপ ফলাফল তৈরি করেঃ ক্রমের প্রতিসাম্য এবং অভ্যন্তরীণ কাঠামো সহজেই হারিয়ে যায়। নিচের উদাহরণটি সমস্যাটি দেখায়। অন্তর্ভুক্তি দ্বারা অর্ডার করা একটি 4-উপাদান সেটের পাওয়ার সেট বিবেচনা করুন। এই আংশিক ক্রমের জন্য নীচে চারটি ভিন্ন হাস রেখাচিত্র দেওয়া হল। প্রতিটি উপসেটে বাইনারি এনকোডিং সহ লেবেলযুক্ত একটি নোড থাকে যা দেখায় যে একটি নির্দিষ্ট উপাদান উপসেটে (1) রয়েছে কি না (0): প্রথম চিত্রটি স্পষ্ট করে দেয় যে পাওয়ার সেটটি একটি গ্রেডেড পজিট। দ্বিতীয় চিত্রটির একই শ্রেণীবদ্ধ কাঠামো রয়েছে, তবে কিছু প্রান্ত অন্যদের তুলনায় দীর্ঘ করে, এটি জোর দেয় যে 4-মাত্রিক ঘনক্ষেত্রটি দুটি 3-মাত্রিক ঘনক্ষেত্রের একটি সমন্বিত মিলন, এবং একটি টেট্রাহেড্রন (বিমূর্ত 3-পলিটোপ) একইভাবে দুটি ত্রিভুজকে (বিমূর্ত 2-পলিটোপ) একত্রিত করে। তৃতীয় রেখাচিত্রটি কাঠামোর কিছু অভ্যন্তরীণ প্রতিসাম্য দেখায়। চতুর্থ রেখাচিত্রে শীর্ষগুলি একটি 4×4 গ্রিডে সাজানো হয়েছে। যদি একটি আংশিক ক্রম একটি হাস রেখাচিত্র হিসাবে আঁকা যায় যেখানে কোনও দুটি প্রান্ত অতিক্রম করে না, তবে এর আচ্ছাদন গ্রাফকে ঊর্ধ্বমুখী সমতলীয় বলা হয়। ঊর্ধ্বমুখী সমতলতার উপর এবং ক্রসিং-মুক্ত হাস রেখাচিত্র নির্মাণের উপর বেশ কয়েকটি ফলাফল জানা যায়ঃ যদি আঁকা আংশিক ক্রমটি একটি জাল হয়, তবে এটি ক্রসিং ছাড়াই আঁকা যেতে পারে যদি এবং কেবলমাত্র যদি এটির ক্রমের মাত্রা সর্বাধিক দুই হয়। এই ক্ষেত্রে, দুটি রৈখিক ক্রমে উপাদানগুলির অবস্থান থেকে ক্রমের মাত্রা উপলব্ধি করে এবং তারপরে অঙ্কনকে 45 ডিগ্রি কোণ দ্বারা ঘড়ির কাঁটার বিপরীত দিকে ঘোরানোর মাধ্যমে একটি অ-ক্রসিং অঙ্কন পাওয়া যেতে পারে। যদি আংশিক ক্রমে সর্বাধিক একটি ন্যূনতম উপাদান থাকে, অথবা এটিতে সর্বাধিক একটি সর্বাধিক উপাদান থাকে, তবে এটির একটি নন-ক্রসিং হাস রেখাচিত্র আছে কিনা তা রৈখিক সময়ে পরীক্ষা করা যেতে পারে। একাধিক উৎস এবং সিঙ্ক সহ একটি আংশিক ক্রম ক্রসিং-মুক্ত হাস রেখাচিত্র হিসাবে আঁকা যেতে পারে কিনা তা নির্ধারণ করা এনপি-সম্পূর্ণ। যাইহোক, একটি ক্রসিং-মুক্ত হাস রেখাচিত্র খুঁজে পাওয়া স্থির-পরামিতি ট্র্যাক্টেবল হয় যখন আংশিক ক্রমের ট্রানজিটিভ হ্রাসের আর্টিকুলেশন পয়েন্ট এবং ট্রাইকানেক্টেড উপাদানগুলির সংখ্যা দ্বারা প্যারামিটাইজ করা হয়। যদি একটি আংশিক ক্রমের উপাদানগুলির y-স্থানাঙ্ক নির্দিষ্ট করা হয়, তবে সেই স্থানাঙ্ক বরাদ্দগুলির সাথে সম্পর্কিত একটি ক্রসিং-মুক্ত হাস রেখাচিত্র রৈখিক সময়ে পাওয়া যেতে পারে, যদি এই ধরনের একটি রেখাচিত্র বিদ্যমান থাকে। বিশেষত, যদি ইনপুট পজিটটি একটি শ্রেণীবদ্ধ পজিট হয়, তবে রৈখিক সময়ে নির্ধারণ করা সম্ভব যে কোনও ক্রসিং-মুক্ত হাস রেখাচিত্র রয়েছে কিনা যেখানে প্রতিটি শীর্ষের উচ্চতা তার র্যাঙ্কের সাথে আনুপাতিক। ইউ. এম. এল নোটেশন সফ্টওয়্যার ইঞ্জিনিয়ারিং-এ, একটি সফ্টওয়্যার সিস্টেমের শ্রেণী এবং এই শ্রেণীগুলির মধ্যে উত্তরাধিকারের সম্পর্ক প্রায়শই একটি শ্রেণী চিত্র ব্যবহার করে চিত্রিত করা হয়, হ্যাশ চিত্রের একটি রূপ যেখানে শ্রেণীগুলিকে সংযুক্তকারী প্রান্তগুলি সুপারক্লাস প্রান্তে একটি খোলা ত্রিভুজ সহ কঠিন রেখা বিভাগ হিসাবে আঁকা হয়। নোটস রেফারেন্স বাহ্যিক লিঙ্ক রেখাচিত্র নির্দেশিত অ্যাসাইক্লিক গ্রাফ গ্রাফ অঙ্কন সেট তত্ত্বে গ্রাফিক্যাল ধারণাগুলি ক্রম তত্ত্ব