Colin de Verdière graph invariant
کولن ڈی ورڈیئر کا غیر متغیر کسی بھی گراف جی کے لیے ایک گراف پیرامیٹر ہے، جسے 1990 میں یویس کولن ڈی ورڈیئر نے متعارف کرایا تھا۔ یہ بعض شروڈنگر آپریٹرز کے دوسرے آئجن ویلیو کی زیادہ سے زیادہ کثرت کے مطالعہ سے متاثر ہوا۔ تعریف آئیے ورٹیکس سیٹ کے ساتھ ایک لوپ لیس سادہ گراف ہو۔ پھر کسی بھی سمیٹرک میٹرکس کا سب سے بڑا کورانک ایسا ہوتا ہے کہ: (M1) سب کے لیے: اگر، اور اگر ؛ (M2) کی ضرب 1 کی بالکل ایک منفی آئگن ویلیو ہوتی ہے ؛ (M3) کوئی غیر صفر میٹرکس ایسا نہیں ہوتا ہے اور ایسا نہیں ہے کہ اگر یا تو ہو یا ہو۔ معروف گراف خاندانوں کی خصوصیت گراف کے کئی معروف خاندانوں کو ان کے کولن ڈی ورڈیئر غیر متغیرات کے لحاظ سے نمایاں کیا جا سکتا ہے: اگر اور صرف اس صورت میں جب G کے کنارے نہ ہوں ؛ اگر اور صرف اس صورت میں جب G ایک لکیری جنگل ہو (راستوں کا ایک جداگانہ اتحاد) ؛ اگر اور صرف اس صورت میں جب G بیرونی طیارہ ہو ؛ اگر اور صرف اس صورت میں جب G طیارہ ہو ؛ اگر اور صرف اس صورت میں جب G R3 میں بغیر کسی ربط کے سرایت پذیر ہو۔ گراف کے یہی خاندان گراف کے کولن ڈی ورڈیئر غیر متغیر اور اس کی تکمیل کی ساخت کے درمیان رابطوں میں بھی ظاہر ہوتے ہیں: اگر کسی n-ورٹیکس گراف کی تکمیل ایک لکیری جنگل ہے، تو ؛ اگر n-ورٹیکس گراف کی تکمیل بیرونی طیارہ ہے، تو ؛ اگر n-ورٹیکس گراف کی تکمیل طیارہ ہے، تو۔ گراف کا ایک چھوٹا سا گراف ایک اور گراف ہے جو کناروں کو سکڑ کر اور کناروں اور عمودی حصوں کو حذف کر کے بنایا جاتا ہے۔ کولن ڈی ورڈیئر غیر متغیر معمولی مونوٹون ہے، جس کا مطلب ہے کہ گراف کا ایک معمولی حصہ لینا صرف اس کے غیر متغیر کو کم یا غیر تبدیل کر سکتا ہے: اگر H G کا معمولی ہے تو۔ رابرٹسن-سیمور تھیوریم کے مطابق، ہر k کے لیے گراف کا ایک محدود سیٹ H موجود ہے جیسے کہ زیادہ سے زیادہ k پر غیر متغیر گراف ان گرافوں کے برابر ہوتے ہیں جن میں H کا کوئی ممبر معمولی نہیں ہوتا ہے۔ ممنوعہ نابالغوں کے ان سیٹوں کو k ≤ 3 کے لیے درج کرتا ہے۔ k = 4 کے لیے ممنوعہ نابالغوں کا مجموعہ پیٹرسن خاندان کے سات گرافوں پر مشتمل ہوتا ہے، جس کی وجہ لنک لیس ایمبیڈ ایبل گراف کی دو خصوصیات ہیں جو کہ گراف کے طور پر μ ≤ 4 کے ساتھ اور گراف کے طور پر جن میں پیٹرسن خاندان معمولی نہیں ہے۔ k = 5 کے لیے ممنوعہ نابالغوں کے سیٹ میں ہیووڈ خاندان کے 78 گراف شامل ہیں، اور یہ قیاس کیا جاتا ہے کہ مزید نہیں ہیں۔ کرومیٹک نمبر نے اندازہ لگایا کہ کولن ڈی ورڈیئر غیر متغیر μ کے ساتھ کوئی بھی گراف زیادہ سے زیادہ μ + 1 رنگوں سے رنگین ہو سکتا ہے۔ مثال کے طور پر، لکیری جنگلات میں غیر متغیر 1 ہوتا ہے، اور یہ 2 رنگ کے ہو سکتے ہیں۔ بیرونی طیارہ گراف میں غیر متغیر دو ہوتے ہیں، اور یہ 3 رنگ کے ہو سکتے ہیں۔ طیارہ گراف میں غیر متغیر 3 ہوتے ہیں، اور (چار رنگوں کے نظریہ کے مطابق) 4 رنگ کے ہو سکتے ہیں۔ کولن ڈی ورڈیئر کے ساتھ زیادہ سے زیادہ چار غیر متغیر گرافوں کے لیے، قیاس درست رہتا ہے۔ یہ بغیر کسی ربط کے سرایت شدہ گراف ہیں، اور یہ حقیقت کہ ان کے پاس زیادہ سے زیادہ پانچ کرومیٹک نمبر ہیں، کے 6-مائنر فری گرافوں کے لیے ہاڈوگر قیاس کے ثبوت کا نتیجہ ہے۔ دیگر خصوصیات اگر کسی گراف میں کراسنگ نمبر ہے، تو اس میں زیادہ سے زیادہ کولن ڈی ورڈیئر غیر متغیر ہے۔ مثال کے طور پر، دو کوراتووسکی گراف اور دونوں کو ایک کراسنگ کے ساتھ کھینچا جا سکتا ہے، اور کولن ڈی ورڈیئر میں زیادہ سے زیادہ چار غیر متغیر ہیں۔ اثر کولن ڈی ورڈیئر غیر متغیر کی تعریف صرف ایک میٹرکس کے بجائے گراف سے مطابقت رکھنے والے میٹرکس کی ایک کلاس کے ذریعے کی جاتی ہے۔ اسی خطوط پر گراف کے دیگر پیرامیٹرز کی وضاحت اور مطالعہ اسی خطوط پر کیا جا سکتا ہے، جیسے کہ کم از کم درجہ، کم از کم سیمی فائنائٹ درجہ اور کم از کم سکیو درجہ۔ حوالہ جات نوٹ کریں۔ ترجمہ نیل جے کالکن نے کیا ہے۔ ۔ ۔ ۔ گراف غیر متغیر گراف معمولی نظریہ