Folded cube graph
گراف تھیوری میں، فولڈڈ کیوب گراف ایک غیر ہدایت شدہ گراف ہے جو ہائپر کیوب گراف سے تشکیل پاتا ہے جس میں ایک کامل ملاپ شامل کیا جاتا ہے جو ہائپر کیوب عمودی کے مخالف جوڑوں کو جوڑتا ہے۔ طول و عرض k (2k−1 عمودی پر مشتمل) کا فولڈ کیوب گراف طول و عرض k−1 کے ہائپر کیوب گراف میں عمودی کے مخالف جوڑوں کے درمیان کناروں کو شامل کرکے بنایا جا سکتا ہے۔ (2n عمودی ہائپر کیوب میں، عمودی کا ایک جوڑا مخالف ہوتا ہے اگر ان کے درمیان مختصر ترین راستے کی لمبائی n ہو۔) یہ، مساوی طور پر، طول و عرض k کے ہائپر کیوب گراف (بھی) سے تشکیل پایا جا سکتا ہے، جس میں دوگنا عمودی ہوتا ہے، عمودی کے ہر مخالف جوڑے کو ایک ساتھ شناخت کرکے (یا سکڑ کر)۔ خصوصیات ایک طول و عرض-k فولڈڈ کیوب گراف 2k−1 عمودی اور 2k−2k کناروں کے ساتھ ایک k-ریگولر ہے۔ طول و عرض-k فولڈڈ کیوب گراف کا کرومیٹک نمبر دو ہوتا ہے جب k یکساں ہوتا ہے (یعنی، اس معاملے میں، گراف دو طرفہ ہوتا ہے) اور چار جب k عجیب ہوتا ہے۔ عجیب طول و عرض کے فولڈڈ کیوب کا عجیب گرتھ k ہے، لہذا تین سے بڑے عجیب k کے لیے فولڈڈ کیوب گراف کرومیٹک نمبر چار اور من مانی طور پر بڑے عجیب گرتھ کے ساتھ مثلث سے پاک گراف کی ایک کلاس فراہم کرتے ہیں۔ عجیب گرتھ k اور قطر (k−1)/2 کے ساتھ فاصلے کے باقاعدہ گراف کے طور پر، عجیب طول و عرض کے فولڈ کیوب عمومی عجیب گراف کی مثالیں ہیں۔ جب k عجیب ہوتا ہے، تو طول و عرض-k فولڈ کیوب کا دو طرفہ ڈبل کور طول و عرض-k کیوب ہوتا ہے جس سے یہ تشکیل پایا تھا۔ تاہم، جب k یکساں ہوتا ہے، تو طول و عرض-k کیوب ایک ڈبل کور ہوتا ہے لیکن دو طرفہ ڈبل کور نہیں ہوتا ہے۔ اس صورت میں، فولڈڈ کیوب خود پہلے سے ہی دو طرفہ ہے۔ فولڈڈ کیوب گراف اپنے ہائپر کیوب سب گراف سے ہیملٹنین سائیکل ہونے کی خاصیت حاصل کرتے ہیں، اور ہائپر کیوب سے جو ان کا دوگنا احاطہ کرتے ہیں وہ فاصلاتی منتقلی گراف ہونے کی خاصیت رکھتے ہیں۔ جب k عجیب ہوتا ہے، تو طول و عرض-k فولڈ کیوب ذیلی گراف کے طور پر 2k−1 نوڈس کے ساتھ ایک مکمل بائنری ٹری پر مشتمل ہوتا ہے۔ تاہم، جب k یکساں ہوتا ہے، تو یہ ممکن نہیں ہے، کیونکہ اس صورت میں فولڈڈ کیوب ایک دو طرفہ گراف ہے جس میں دو طرفہ کے ہر طرف عمودی کی مساوی تعداد ہوتی ہے، جو مکمل بائنری ٹری کے دو طرفہ تناسب کے لیے تقریبا دو سے ایک کے تناسب سے بہت مختلف ہے۔ مثالیں طول و عرض تین کا فولڈڈ کیوب گراف ایک مکمل گراف K4 ہے۔ طول و عرض چار کا فولڈڈ کیوب گراف مکمل دو طرفہ گراف K4,4 ہے۔ طول و عرض پانچ کا فولڈڈ کیوب گراف کلیبش گراف ہے۔ طول و عرض چھ کا فولڈڈ کیوب گراف کمر گراف ہے، یعنی۔ کمر پوائنٹ طیارہ ترتیب کا لیوی گراف۔ متوازی کمپیوٹنگ میں، فولڈ کیوب گراف کا مطالعہ ہائپر کیوب کے متبادل کے طور پر ممکنہ نیٹ ورک ٹوپولوجی کے طور پر کیا گیا ہے۔ ہائپر کیوب کے مقابلے میں، نوڈس کی ایک ہی تعداد کے ساتھ ایک فولڈ کیوب میں تقریبا ایک ہی ورٹیکس ڈگری ہوتی ہے لیکن صرف آدھا قطر ہوتا ہے۔ موثر تقسیم شدہ الگورتھم (ہائپر کیوب کے مقابلے میں) فولڈ کیوب میں معلومات نشر کرنے کے لیے جانے جاتے ہیں۔ نصف کیوب گراف نوٹس حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ بیرونی روابط گراف کے پیرامیٹرک خاندان باقاعدہ گراف