Partial cube
گراف تھیوری میں، جزوی مکعب ایک ایسا گراف ہے جو ہائپر مکعب کے ذیلی گراف کے لیے آئسومیٹرک ہوتا ہے۔ دوسرے لفظوں میں، جزوی مکعب کی شناخت ہائپر مکعب کے ذیلی گراف سے اس طرح کی جا سکتی ہے کہ جزوی مکعب میں کسی بھی دو عمودی حصوں کے درمیان فاصلہ ہائپر مکعب میں ان عمودی حصوں کے درمیان فاصلے کے برابر ہو۔ مساوی طور پر، ایک جزوی مکعب ایک گراف ہے جس کے عمودی حصوں کو مساوی لمبائی کے بٹ تاروں کے ساتھ اس طرح سے لیبل کیا جا سکتا ہے کہ گراف میں دو عمودی حصوں کے درمیان فاصلہ ان کے لیبل کے درمیان ہیمنگ فاصلے کے برابر ہو۔ اس طرح کی لیبلنگ کو ہیمنگ لیبلنگ کہا جاتا ہے۔ یہ ہائپر مکعب میں جزوی مکعب کے آئسومیٹرک سرایت کی نمائندگی کرتا ہے۔ ہائپر کیوب میں گراف کے آئسومیٹرک سرایت کا مطالعہ کرنے والی تاریخ پہلی تھی۔ وہ گراف جو اس طرح کے سرایت کو تسلیم کرتے ہیں ان کی خصوصیت اور تھی، اور بعد میں انہیں جزوی کیوب کا نام دیا گیا۔ گراف کے ہائپر کیوب لیبلنگ کے بجائے سیٹوں کے خاندانوں کی اصطلاحات میں، ایک ہی ڈھانچے پر تحقیق کی ایک علیحدہ لائن کے بعد، اور، دوسروں کے درمیان۔ مثال ہر درخت ایک جزوی مکعب ہے۔ کیونکہ، فرض کریں کہ کسی درخت کے کنارے ہوتے ہیں، اور ان کناروں کو (من مانی طور پر) سے نمبر دیں۔ درخت کے لیے روٹ ورٹیکس کا انتخاب کریں، من مانی طور پر، اور ہر ورٹیکس پر بٹس کی ایک تار کے ساتھ لیبل لگائیں جس کی پوزیشن 1 ہو جب بھی کنارے راستے سے اندر کی طرف ہو۔ مثال کے طور پر، خود ایک لیبل ہوگا جو تمام صفر بٹس کا ہوگا، اس کے پڑوسیوں کے پاس ایک 1 بٹ وغیرہ کے ساتھ لیبل ہوں گے۔ پھر کسی بھی دو لیبل کے درمیان ہیمنگ کا فاصلہ درخت میں دو عمودی حصوں کے درمیان کا فاصلہ ہے، لہذا یہ لیبلنگ ظاہر کرتی ہے کہ یہ ایک جزوی مکعب ہے۔ ہر ہائپر کیوب گراف خود ایک جزوی کیوب ہوتا ہے، جسے ہائپر کیوب کے طول و عرض کے برابر لمبائی کے تمام مختلف بٹ سٹرنگز کے ساتھ لیبل کیا جا سکتا ہے۔ مزید پیچیدہ مثالوں میں درج ذیل شامل ہیں: اس گراف پر غور کریں جس کے ورٹیکس لیبل تمام ممکنہ ہندسوں کے بٹ سٹرنگ پر مشتمل ہوتے ہیں جن میں یا تو غیر صفر بٹس ہوتے ہیں، جہاں جب بھی ان کے لیبل ایک بٹ سے مختلف ہوتے ہیں تو دو عمودی ملحقہ ہوتے ہیں۔ یہ لیبلنگ ان گرافوں کو ایک ہائپر کیوب (ایک دی گئی لمبائی کے تمام بٹ سٹرنگز کا گراف، اسی ملحقہ حالت کے ساتھ) میں سرایت کرنے کی وضاحت کرتی ہے جو فاصلہ برقرار رکھنے والا ثابت ہوتا ہے۔ نتیجے میں آنے والا گراف ایک دو طرفہ کنیسر گراف ہے ؛ اس طرح سے تشکیل پانے والے گراف میں 20 عمودی اور 30 کنارے ہوتے ہیں، اور اسے ڈیسرگز گراف کہا جاتا ہے۔ تمام میڈین گراف جزوی کیوب ہوتے ہیں۔ درخت اور ہائپر کیوب گراف میڈین گراف کی مثالیں ہیں۔ چونکہ میڈین گراف میں مربع گراف، سمپلیکس گراف، اور فبونیکی کیوب کے ساتھ ساتھ محدود تقسیم شدہ جالی کے کورنگ گراف شامل ہیں، یہ تمام جزوی کیوب ہیں۔ یوکلڈین سطح میں لکیروں کی ترتیب کا طیارہ دوہری گراف ایک جزوی مکعب ہے۔ زیادہ عام طور پر، یوکلڈین جگہ میں کسی بھی تعداد میں طول و عرض کے کسی بھی ہائپرپلین ترتیب کے لیے، وہ گراف جس میں ترتیب کے ہر خلیے کے لیے ایک ورٹیکس اور ہر دو ملحقہ خلیوں کے لیے ایک کنارے ہوتا ہے، ایک جزوی مکعب ہوتا ہے۔ ایک جزوی مکعب جس میں ہر سرے کے بالکل تین پڑوسی ہوتے ہیں کیوبک جزوی مکعب کے نام سے جانا جاتا ہے۔ اگرچہ کیوبک جزوی کیوب کے کئی لامحدود خاندانوں کو جانا جاتا ہے، لیکن بہت سی دوسری چھٹپٹ مثالوں کے ساتھ، واحد معلوم کیوبک جزوی کیوب جو پلانر گراف نہیں ہے وہ ڈیسرگس گراف ہے۔ کسی بھی اینٹی میٹرائڈ کا بنیادی گراف، جس میں اینٹی میٹرائڈ میں ہر سیٹ کے لیے ایک ورٹیکس ہوتا ہے اور ہر دو سیٹوں کے لیے ایک کنارہ ہوتا ہے جو ایک عنصر سے مختلف ہوتا ہے، ہمیشہ ایک جزوی مکعب ہوتا ہے۔ جزوی کیوب کے کسی بھی محدود سیٹ کا کارٹیشین پروڈکٹ ایک اور جزوی کیوب ہے۔ مکمل گراف کی ذیلی تقسیم جزوی مکعب ہوتی ہے اگر اور صرف اس صورت میں جب یا تو ہر مکمل گراف کے کنارے کو دو کنارے والے راستے میں تقسیم کیا جائے، یا ایک مکمل گراف ورٹیکس ہو جس کے واقعے کے کنارے تمام غیر منقسم ہوں اور تمام غیر حادثاتی کناروں کو یکساں لمبائی والے راستوں میں تقسیم کیا گیا ہو۔ ڈوکوویچ-ونکلر تعلق جزوی کیوب کے بارے میں بہت سے نظریات براہ راست یا بالواسطہ طور پر گراف کے کناروں پر بیان کردہ ایک مخصوص بائنری تعلق پر مبنی ہیں۔ یہ رشتہ، جسے پہلے بیان کیا گیا ہے اور فاصلے کے لحاظ سے مساوی تعریف دی گئی ہے، کی طرف سے ظاہر کیا جاتا ہے۔ دو کناروں اور تعلقات میں ہونے کی وضاحت کی گئی ہے، لکھا ہوا، اگر۔ یہ تعلق اضطراری اور ہم آہنگ ہے، لیکن عام طور پر یہ عارضی نہیں ہے۔ ونکلر نے دکھایا کہ منسلک گراف ایک جزوی مکعب ہے اگر اور صرف اس صورت میں جب یہ دو طرفہ ہو اور رشتہ عارضی ہو۔ اس صورت میں، یہ ایک مساوات کا رشتہ بناتا ہے اور ہر مساوات کلاس گراف کے دو منسلک ذیلی گراف کو ایک دوسرے سے الگ کرتی ہے۔ ڈوکوویچ-ونکلر تعلق کی مساوات کی کلاسوں میں سے ہر ایک کو ہر لیبل کا ایک بٹ تفویض کرکے ہیمنگ لیبلنگ حاصل کی جا سکتی ہے۔ کناروں کی مساوات کی کلاس سے الگ ہونے والے دو منسلک ذیلی گرافوں میں سے ایک میں، تمام عمودی حصوں میں ان کے لیبل کی اس پوزیشن میں 0 ہوتا ہے، اور دوسرے منسلک ذیلی گراف میں تمام عمودی حصوں میں ایک ہی پوزیشن میں 1 ہوتا ہے۔ شناخت جزوی کیوب کو پہچانا جا سکتا ہے، اور وقت کے ساتھ ہیمنگ لیبلنگ بنائی جاتی ہے، جہاں گراف میں عمودی حصوں کی تعداد ہوتی ہے۔ جزوی کیوب کو دیکھتے ہوئے، ڈوکوویچ-ونکلر تعلق کی مساوات کی کلاسوں کی تعمیر کرنا سیدھا ہے، کل وقت میں، ہر سرے سے چوڑائی کی پہلی تلاش کرکے۔-ٹائم ریکگنیشن الگورتھم گراف کے ذریعے ایک ہی پاس میں ایک سے زیادہ چوڑائی کی پہلی تلاشوں کو انجام دینے کے لیے بٹ لیول متوازی کا استعمال کرکے اسے تیز کرتا ہے، اور پھر اس بات کی تصدیق کے لیے ایک علیحدہ الگورتھم کا اطلاق کرتا ہے کہ اس حساب کا نتیجہ ایک درست جزوی کیوب لیبلنگ ہے۔ طول و عرض جزوی مکعب کا آئسومیٹرک طول و عرض ایک ہائپر مکعب کا کم از کم طول و عرض ہے جس پر اسے آئسومیٹرک طور پر سرایت کیا جا سکتا ہے، اور یہ ڈوکوویچ-ونکلر تعلقات کی مساوات کی کلاسوں کی تعداد کے برابر ہے۔ مثال کے طور پر، ایک-ورٹیکس درخت کا آئسومیٹرک طول و عرض اس کے کناروں کی تعداد ہے۔ اس طول و عرض کے ہائپر مکعب پر جزوی مکعب کا سرایت کرنا منفرد ہے، ہائپر مکعب کی ہم آہنگی تک۔ ہر ہائپر کیوب اور اس لیے ہر جزوی کیوب کو آئسومیٹرک طور پر ایک انٹیجر لیٹس میں سرایت کیا جا سکتا ہے۔ گراف کا جالی طول و عرض ایک عدد جالی کا کم از کم طول و عرض ہے جس میں گراف کو آئسومیٹرک طور پر سرایت کیا جا سکتا ہے۔ جالی کا طول و عرض آئسومیٹرک طول و عرض سے نمایاں طور پر چھوٹا ہو سکتا ہے ؛ مثال کے طور پر، کسی درخت کے لیے یہ درخت میں موجود پتوں کی تعداد کا نصف ہوتا ہے (قریب ترین عدد تک گول)۔ کسی بھی گراف کا جالی طول و عرض، اور کم از کم طول و عرض کا جالی سرایت، معاون گراف میں زیادہ سے زیادہ ملاپ پر مبنی الگورتھم کے ذریعے کثیر الجہتی وقت میں پایا جا سکتا ہے۔ جزوی کیوب کے طول و عرض کی دیگر اقسام کی بھی وضاحت کی گئی ہے، جو زیادہ مخصوص ڈھانچوں میں سرایت کرنے پر مبنی ہیں۔ کیمیائی گراف تھیوری پر اطلاق ہائپر کیوب میں گراف کے آئسومیٹرک سرایت کا کیمیائی گراف تھیوری میں ایک اہم اطلاق ہوتا ہے۔ بینزینائڈ گراف ایک ایسا گراف ہے جو تمام عمودی اور کناروں پر مشتمل ہوتا ہے جو ایک ہیکساگونل جالی میں سائیکل کے اندرونی حصے پر اور اس میں پڑے ہوتے ہیں۔ اس طرح کے گراف بینزینائڈ ہائیڈرو کاربن کے مالیکیولر گراف ہیں، جو نامیاتی مالیکیولز کی ایک بڑی کلاس ہے۔ اس طرح کا ہر گراف ایک جزوی مکعب ہے۔ اس طرح کے گراف کی ہیمنگ لیبلنگ کو متعلقہ مالیکیول کے وینر انڈیکس کا حساب لگانے کے لیے استعمال کیا جا سکتا ہے، جسے پھر اس کی بعض کیمیائی خصوصیات کی پیش گوئی کے لیے استعمال کیا جا سکتا ہے۔ کاربن سے بنی ایک مختلف سالماتی ساخت، ڈائمنڈ کیوبک، بھی جزوی کیوب گراف بناتی ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ خاص طور پر باب 5، "جزوی کیوب"، پی پی دیکھیں۔ 127-181۔ ۔ گراف خاندان ریاضیاتی کیمسٹری بپارٹائٹ گراف