Partial cube
গ্রাফ তত্ত্বে, একটি আংশিক ঘনক হল একটি গ্রাফ যা একটি হাইপারকিউবের উপ-গ্রাফের সমমিতিযুক্ত। অন্য কথায়, একটি আংশিক ঘনককে একটি হাইপারকিউবের সাবগ্রাফ দিয়ে এমনভাবে চিহ্নিত করা যেতে পারে যে আংশিক ঘনকের যে কোনও দুটি শীর্ষের মধ্যে দূরত্ব হাইপারকিউবের সেই শীর্ষগুলির মধ্যে দূরত্বের সমান হয়। সমতুল্যভাবে, একটি আংশিক ঘনক হল এমন একটি গ্রাফ যার শীর্ষগুলিকে সমান দৈর্ঘ্যের বিট স্ট্রিং দিয়ে এমনভাবে লেবেল করা যেতে পারে যে গ্রাফের দুটি শীর্ষের মধ্যে দূরত্ব তাদের লেবেলগুলির মধ্যে হ্যামিং দূরত্বের সমান হয়। এই ধরনের লেবেলিংকে হ্যামিং লেবেলিং বলা হয়; এটি একটি হাইপারকিউবে আংশিক ঘনক্ষেত্রের একটি আইসোমেট্রিক এম্বেডিংকে উপস্থাপন করে। ইতিহাসই প্রথম হাইপারকিউবে গ্রাফের আইসোমেট্রিক এম্বেডিং নিয়ে গবেষণা করেছিল। যে গ্রাফগুলি এই জাতীয় এম্বেডিং স্বীকার করে সেগুলি এবং দ্বারা চিহ্নিত করা হয়েছিল এবং পরে আংশিক কিউব নামকরণ করা হয়েছিল। গ্রাফের হাইপারকিউব লেবেলিংয়ের পরিবর্তে সেটের পরিবারের পরিভাষায় একই কাঠামোর উপর গবেষণার একটি পৃথক লাইন অনুসরণ করা হয়েছিল এবং, অন্যদের মধ্যে। উদাহরণস্বরূপ, প্রতিটি গাছ একটি আংশিক ঘনক্ষেত্র। কারণ, ধরুন যে একটি গাছের প্রান্ত রয়েছে এবং এই প্রান্তগুলিকে (নির্বিচারে) থেকে পর্যন্ত গণনা করুন। গাছের জন্য একটি মূল শীর্ষ বেছে নিন, নির্বিচারে, এবং প্রতিটি শীর্ষকে বিটের একটি স্ট্রিং দিয়ে লেবেল করুন যার অবস্থানে 1 থাকে যখনই প্রান্তটি পথ থেকে ভিতরে থাকে। উদাহরণস্বরূপ, নিজের একটি লেবেল থাকবে যা সমস্ত শূন্য বিট, এর প্রতিবেশীদের একটি একক 1-বিট সহ লেবেল থাকবে, ইত্যাদি। তারপর যে কোনও দুটি লেবেলের মধ্যে হ্যামিং দূরত্ব হল গাছের দুটি শীর্ষের মধ্যে দূরত্ব, তাই এই লেবেলিং দেখায় যে এটি একটি আংশিক ঘনক। প্রতিটি হাইপারকিউব গ্রাফ নিজেই একটি আংশিক ঘনক্ষেত্র, যা হাইপারকিউবের মাত্রার সমান দৈর্ঘ্যের সমস্ত বিভিন্ন বিটস্ট্রিং দিয়ে লেবেল করা যেতে পারে। আরও জটিল উদাহরণগুলির মধ্যে নিম্নলিখিতগুলি অন্তর্ভুক্ত রয়েছেঃ সেই গ্রাফটি বিবেচনা করুন যার ভার্টেক্স লেবেলগুলি সমস্ত সম্ভাব্য-অঙ্কের বিটস্ট্রিং নিয়ে গঠিত যার মধ্যে একটি বা অ-শূন্য বিট রয়েছে, যেখানে দুটি শীর্ষ সংলগ্ন থাকে যখনই তাদের লেবেলগুলি একটি বিট দ্বারা পৃথক হয়। এই লেবেলিং একটি হাইপারকিউবে (একটি নির্দিষ্ট দৈর্ঘ্যের সমস্ত বিটস্ট্রিংয়ের গ্রাফ, একই সংলগ্নতা-শর্ত সহ) এই গ্রাফগুলির একটি এম্বেডিংকে সংজ্ঞায়িত করে যা দূরত্ব-সংরক্ষণকারী হিসাবে পরিণত হয়। ফলস্বরূপ গ্রাফটি একটি দ্বিদলীয় নেসার গ্রাফ; এইভাবে গঠিত গ্রাফটিতে 20টি শীর্ষ এবং 30টি প্রান্ত রয়েছে এবং এটিকে ডেসারগস গ্রাফ বলা হয়। সমস্ত মধ্যমা গ্রাফগুলি আংশিক কিউব। গাছ এবং হাইপারকিউব গ্রাফগুলি মধ্যমা গ্রাফের উদাহরণ। যেহেতু মধ্যমা গ্রাফের মধ্যে রয়েছে স্কোয়ারগ্রাফ, সিম্প্লেক্স গ্রাফ এবং ফিবোনাচি কিউব, সেইসাথে সীমাবদ্ধ বিতরণমূলক জালকের আচ্ছাদন গ্রাফ, এগুলি সবই আংশিক কিউব। ইউক্লিডীয় সমতলে রেখাগুলির বিন্যাসের সমতলীয় দ্বৈত গ্রাফটি একটি আংশিক ঘনক। আরও সাধারণভাবে, ইউক্লিডীয় স্থানে যে কোনও সংখ্যক মাত্রার যে কোনও হাইপারপ্লেন বিন্যাসের জন্য, বিন্যাসের প্রতিটি কোষের জন্য একটি শীর্ষ এবং প্রতিটি দুটি সংলগ্ন কোষের জন্য একটি প্রান্ত রয়েছে এমন গ্রাফটি একটি আংশিক ঘনক্ষেত্র। একটি আংশিক ঘনক যেখানে প্রতিটি শীর্ষে ঠিক তিনটি প্রতিবেশী থাকে তাকে ঘন আংশিক ঘনক বলা হয়। যদিও ঘন আংশিক কিউবগুলির বেশ কয়েকটি অসীম পরিবার জানা যায়, অন্যান্য অনেক বিক্ষিপ্ত উদাহরণের সাথে, একমাত্র পরিচিত ঘন আংশিক কিউব যা একটি সমতলীয় গ্রাফ নয় তা হল ডেসারগস গ্রাফ। যে কোনও অ্যান্টিম্যাট্রয়েডের অন্তর্নিহিত গ্রাফ, যার অ্যান্টিম্যাট্রয়েডের প্রতিটি সেটের জন্য একটি শীর্ষ এবং প্রতিটি দুটি সেটের জন্য একটি প্রান্ত থাকে যা একটি একক উপাদান দ্বারা পৃথক হয়, সর্বদা একটি আংশিক ঘনক হয়। আংশিক কিউবগুলির যে কোনও সীমাবদ্ধ সেটের কার্টেসিয়ান পণ্য হল আরেকটি আংশিক কিউব। একটি সম্পূর্ণ গ্রাফের একটি উপবিভাগ আংশিক ঘনক হয় যদি এবং শুধুমাত্র যদি প্রতিটি সম্পূর্ণ গ্রাফ প্রান্তকে দ্বি-প্রান্তের পথে বিভক্ত করা হয়, অথবা একটি সম্পূর্ণ গ্রাফ শীর্ষ থাকে যার আপতিত প্রান্তগুলি সমস্ত অবিভক্ত এবং সমস্ত অ-দুর্ঘটনা প্রান্তগুলি জোড় দৈর্ঘ্যের পথে বিভক্ত করা হয়েছে। জকোভিচ-উইঙ্কলার সম্পর্ক আংশিক কিউব সম্পর্কে অনেক উপপাদ্য গ্রাফের প্রান্তে সংজ্ঞায়িত একটি নির্দিষ্ট বাইনারি সম্পর্কের উপর প্রত্যক্ষ বা পরোক্ষভাবে ভিত্তি করে তৈরি। এই সম্পর্কটি, প্রথমে দ্বারা বর্ণিত এবং দ্বারা দূরত্বের পরিপ্রেক্ষিতে একটি সমতুল্য সংজ্ঞা দেওয়া হয়েছে, দ্বারা চিহ্নিত করা হয়। দুটি প্রান্ত এবং সম্পর্ক হিসাবে সংজ্ঞায়িত করা হয়, লিখিত, যদি। এই সম্পর্কটি প্রতিফলিত এবং প্রতিসম, তবে সাধারণভাবে এটি ক্ষণস্থায়ী নয়। উইঙ্কলার দেখিয়েছেন যে একটি সংযুক্ত গ্রাফ একটি আংশিক ঘনক হয় যদি এবং শুধুমাত্র যদি এটি দ্বিদলীয় হয় এবং সম্পর্কটি ক্ষণস্থায়ী হয়। এই ক্ষেত্রে, এটি একটি সমতুল্য সম্পর্ক গঠন করে এবং প্রতিটি সমতুল্য শ্রেণী গ্রাফের দুটি সংযুক্ত উপগ্রাফকে একে অপরের থেকে পৃথক করে। জকোভিচ-উইঙ্কলার সম্পর্কের সমতুল্য শ্রেণীর প্রত্যেকটিতে প্রতিটি লেবেলের একটি বিট বরাদ্দ করে একটি হ্যামিং লেবেলিং প্রাপ্ত করা যেতে পারে; সমতুল্য শ্রেণীর প্রান্ত দ্বারা পৃথক করা দুটি সংযুক্ত সাবগ্রাফগুলির মধ্যে একটিতে, সমস্ত শীর্ষে তাদের লেবেলের সেই অবস্থানে 0 থাকে এবং অন্য সংযুক্ত সাবগ্রাফে সমস্ত শীর্ষে একই অবস্থানে 1 থাকে। শনাক্তকরণ আংশিক কিউবগুলি শনাক্ত করা যেতে পারে এবং সময়ের সাথে সাথে একটি হ্যামিং লেবেলিং তৈরি করা হয়, যেখানে গ্রাফের শীর্ষগুলির সংখ্যা কোথায়। একটি আংশিক ঘনক দেওয়া হলে, প্রতিটি শীর্ষ থেকে মোট সময়ে একটি প্রস্থ প্রথম অনুসন্ধান করে জকোভিচ-উইঙ্কলার সম্পর্কের সমতুল্য শ্রেণী তৈরি করা সোজা;-সময় স্বীকৃতি অ্যালগরিদম বিট-স্তরের সমান্তরালতা ব্যবহার করে একাধিক প্রস্থ প্রথম অনুসন্ধানগুলি গ্রাফের মধ্য দিয়ে একক পাসে সম্পাদন করে এবং তারপরে এই গণনার ফলাফলটি একটি বৈধ আংশিক ঘনক লেবেলিং কিনা তা যাচাই করার জন্য একটি পৃথক অ্যালগরিদম প্রয়োগ করে। একটি আংশিক ঘনক্ষেত্রের আইসোমেট্রিক মাত্রা হল একটি হাইপারকিউবের ন্যূনতম মাত্রা যার উপর এটি আইসোমেট্রিকভাবে এম্বেড করা যেতে পারে এবং এটি জকোভিচ-উইঙ্কলার সম্পর্কের সমতুল্য শ্রেণীর সংখ্যার সমান। উদাহরণস্বরূপ, একটি-ভার্টেক্স গাছের আইসোমেট্রিক মাত্রা হল এর প্রান্তের সংখ্যা। হাইপারকিউবের প্রতিসাম্য পর্যন্ত এই মাত্রার হাইপারকিউবে একটি আংশিক ঘনক্ষেত্রের সংযোজন অনন্য। প্রতিটি হাইপারকিউব এবং তাই প্রতিটি আংশিক কিউবকে একটি পূর্ণসংখ্যা জালিতে আইসোমেট্রিকভাবে এম্বেড করা যেতে পারে। একটি গ্রাফের জালের মাত্রা হল একটি পূর্ণসংখ্যা জালের সর্বনিম্ন মাত্রা যার মধ্যে গ্রাফটি আইসোমেট্রিকভাবে এম্বেড করা যেতে পারে। জালের মাত্রা আইসোমেট্রিক মাত্রার তুলনায় উল্লেখযোগ্যভাবে ছোট হতে পারে; উদাহরণস্বরূপ, একটি গাছের জন্য এটি গাছের পাতার সংখ্যার অর্ধেক (নিকটতম পূর্ণসংখ্যা পর্যন্ত বৃত্তাকার)। যে কোনও গ্রাফের জালের মাত্রা এবং ন্যূনতম মাত্রার একটি জাল এম্বেডিং, একটি সহায়ক গ্রাফের সর্বাধিক মিলনের উপর ভিত্তি করে একটি অ্যালগরিদম দ্বারা বহুপদী সময়ে পাওয়া যেতে পারে। আরও বিশেষ কাঠামোর মধ্যে এম্বেডিংয়ের উপর ভিত্তি করে আংশিক কিউবগুলির অন্যান্য ধরনের মাত্রাও সংজ্ঞায়িত করা হয়েছে। রাসায়নিক গ্রাফ তত্ত্বের প্রয়োগ হাইপারকিউবে গ্রাফের আইসোমেট্রিক এম্বেডিংয়ের রাসায়নিক গ্রাফ তত্ত্বে একটি গুরুত্বপূর্ণ প্রয়োগ রয়েছে। একটি বেনজেনয়েড গ্রাফ একটি ষড়ভুজাকার জালের মধ্যে একটি চক্রের উপর এবং অভ্যন্তরে অবস্থিত সমস্ত শীর্ষ এবং প্রান্ত নিয়ে গঠিত একটি গ্রাফ। এই ধরনের গ্রাফগুলি বেনজেনয়েড হাইড্রোকার্বনের আণবিক গ্রাফ, যা জৈব অণুর একটি বড় শ্রেণী। এই ধরনের প্রতিটি গ্রাফ একটি আংশিক ঘনক্ষেত্র। এই ধরনের গ্রাফের একটি হ্যামিং লেবেলিং সংশ্লিষ্ট অণুর উইনার সূচক গণনা করতে ব্যবহার করা যেতে পারে, যা পরে এর কিছু রাসায়নিক বৈশিষ্ট্যের পূর্বাভাস দিতে ব্যবহার করা যেতে পারে। কার্বন থেকে গঠিত একটি ভিন্ন আণবিক কাঠামো, ডায়মন্ড কিউবিক, আংশিক কিউব গ্রাফও তৈরি করে। উল্লেখগুলি উল্লেখ করুন। । । । । । । । যেমনটি উল্লেখ করা হয়েছে। । যেমনটি উল্লেখ করা হয়েছে। । । । যেমনটি উল্লেখ করা হয়েছে। । বিশেষ করে 5ম অধ্যায়, "পার্শিয়াল কিউব", পৃষ্ঠা দেখুন। 127-181। । গ্রাফ পরিবার গাণিতিক রসায়ন দ্বিদলীয় গ্রাফ