Degree (graph theory)
گراف تھیوری میں، گراف کے ورٹیکس کی ڈگری (یا ویلینسی) ان کناروں کی تعداد ہے جو ورٹیکس سے منسلک ہوتے ہیں۔ ملٹی گراف میں، ایک لوپ کنارے کے دو سروں کے لیے ورٹیکس کی ڈگری میں 2 کا حصہ ڈالتا ہے۔ کسی سرے کی ڈگری کو یا سے ظاہر کیا جاتا ہے۔ گراف کی زیادہ سے زیادہ ڈگری، جس سے ظاہر ہوتا ہے، اور گراف کی کم سے کم ڈگری، جس سے ظاہر ہوتا ہے، اس کے عمودی ڈگریوں کی زیادہ سے زیادہ اور کم سے کم ہوتی ہے۔ دائیں طرف دکھائے گئے ملٹی گراف میں زیادہ سے زیادہ ڈگری 5 اور کم سے کم ڈگری 0 ہے۔ باقاعدہ گراف میں، ہر سرے کی ڈگری ایک جیسی ہوتی ہے، اور اس لیے ہم گراف کی ڈگری کے بارے میں بات کر سکتے ہیں۔ ایک مکمل گراف (اشارہ شدہ، جہاں گراف میں عمودی حصوں کی تعداد ہے) ایک خاص قسم کا باقاعدہ گراف ہے جہاں تمام عمودی حصوں میں زیادہ سے زیادہ ممکنہ ڈگری ہوتی ہے۔ دستخط شدہ گراف میں، ورٹیکس سے منسلک مثبت کناروں کی تعداد کو مثبت ڈگری کہا جاتا ہے اور منسلک منفی کناروں کی تعداد منفی ڈگری کا حقدار ہے۔ ہینڈ شیکنگ لیما ڈگری سم فارمولا بیان کرتا ہے کہ، گراف کو دیکھتے ہوئے، فارمولے سے یہ ظاہر ہوتا ہے کہ کسی بھی غیر ہدایت شدہ گراف میں، طاق ڈگری والے عمودی حصوں کی تعداد یکساں ہوتی ہے۔ یہ بیان (نیز ڈگری سم فارمولا) ہاتھ ملانے والے لیما کے نام سے جانا جاتا ہے۔ مؤخر الذکر نام ایک مقبول ریاضیاتی مسئلہ سے آیا ہے، جو یہ ثابت کرنے کے لیے ہے کہ لوگوں کے کسی بھی گروہ میں، گروپ کے دوسرے لوگوں کی عجیب تعداد سے ہاتھ ملانے والے لوگوں کی تعداد یکساں ہے۔ ڈگری ترتیب غیر ہدایت شدہ گراف کی ڈگری ترتیب اس کے عمودی ڈگریوں کی غیر بڑھتی ہوئی ترتیب ہے۔ مندرجہ بالا گراف کے لیے یہ ہے (5، 3، 3، 2، 2، 1، 0)۔ ڈگری کی ترتیب ایک غیر متغیر گراف ہے، اس لیے آئسومورفک گراف کی ڈگری کی ترتیب ایک جیسی ہوتی ہے۔ تاہم، ڈگری کی ترتیب، عام طور پر، گراف کی منفرد شناخت نہیں کرتی ہے۔ کچھ معاملات میں، غیر آئسومورفک گراف کی ڈگری کی ترتیب ایک جیسی ہوتی ہے۔ ڈگری ترتیب کا مسئلہ کچھ یا تمام گرافوں کو تلاش کرنے کا مسئلہ ہے جس میں ڈگری ترتیب مثبت عددوں کی دی گئی غیر بڑھتی ہوئی ترتیب ہے۔ (ٹریلنگ صفر کو نظر انداز کیا جا سکتا ہے کیونکہ گراف میں الگ تھلگ عمودی کی مناسب تعداد شامل کر کے ان کا معمولی احساس ہوتا ہے۔) ایک ترتیب جو کسی گراف کی ڈگری ترتیب ہے، یعنی۔ جس کے لیے ڈگری ترتیب کے مسئلے کا حل ہوتا ہے، اسے گرافک یا گرافیکل ترتیب کہا جاتا ہے۔ ڈگری سم فارمولے کے نتیجے میں، عجیب رقم کے ساتھ کسی بھی ترتیب کو، جیسے (3، 3، 1)، گراف کی ڈگری ترتیب کے طور پر محسوس نہیں کیا جا سکتا۔ الٹا بھی درست ہے: اگر کسی ترتیب میں یکساں مجموعہ ہے، تو یہ ملٹی گراف کی ڈگری ترتیب ہے۔ اس طرح کے گراف کی تعمیر سیدھی ہے: عمودی حصوں کو جوڑوں میں عجیب ڈگریوں سے جوڑیں (مماثل بنائیں)، اور بقیہ یکساں ڈگری گنتی کو سیلف لوپس سے پر کریں۔ یہ سوال کہ آیا دی گئی ڈگری کی ترتیب کو سادہ گراف کے ذریعے حاصل کیا جا سکتا ہے، زیادہ مشکل ہے۔ اس مسئلے کو گراف کے احساس کا مسئلہ بھی کہا جاتا ہے اور اسے ایرڈس-گلائی تھیوریم یا حویل-ہکیمی الگورتھم کے ذریعے حل کیا جا سکتا ہے۔ دی گئی ڈگری کی ترتیب کے ساتھ گراف کی تعداد کو تلاش کرنے یا اندازہ لگانے کا مسئلہ گراف گنتی کے میدان سے ایک مسئلہ ہے۔ زیادہ عام طور پر، ہائپر گراف کی ڈگری ترتیب اس کے ورٹیکس ڈگریوں کی غیر بڑھتی ہوئی ترتیب ہے۔ ایک ترتیب-گرافک ہوتی ہے اگر یہ کسی یکساں ہائپر گراف کی ڈگری ترتیب ہو۔ خاص طور پر، ایک گرافک ترتیب گرافک ہے۔ یہ فیصلہ کرنا کہ آیا کوئی دی گئی ترتیب-گرافک ہے، ایرڈس-گلائی تھیوریم کے ذریعے کثیر الجہتی وقت میں قابل عمل ہے لیکن سب کے لیے این پی مکمل ہے۔ خصوصی اقدار 0 ڈگری والے ورٹیکس کو الگ تھلگ ورٹیکس کہا جاتا ہے۔ ڈگری 1 والے ورٹیکس کو لیف ورٹیکس یا اینڈ ورٹیکس یا لاکٹ ورٹیکس کہا جاتا ہے، اور اس ورٹیکس کے ساتھ کنارے کے واقعے کو لاکٹ ایج کہا جاتا ہے۔ دائیں طرف کے گراف میں، {3,5} لاکٹ کا کنارہ ہے۔ یہ اصطلاحات گراف تھیوری میں درختوں اور خاص طور پر اعداد و شمار کے ڈھانچے کے طور پر درختوں کے مطالعہ میں عام ہیں۔ ایک ورٹیکس جس کی ڈگری n-1 ہو، n ورٹیکس پر گراف میں غالب ورٹیکس کہلاتا ہے۔ عالمی خصوصیات اگر گراف کے ہر ایک سرے کی ڈگری k ہوتی ہے، تو گراف کو k-ریگولر گراف کہا جاتا ہے اور خود گراف کو ڈگری k کہا جاتا ہے۔ اسی طرح، ایک دو طرفہ گراف جس میں دو طرفہ تقسیم کے ایک ہی طرف ہر دو عمودی ایک دوسرے کے برابر ڈگری رکھتے ہیں، اسے بائریگولر گراف کہا جاتا ہے۔ ایک غیر ہدایت شدہ، منسلک گراف کا یولیرین راستہ ہوتا ہے اگر اور صرف اس صورت میں جب اس میں 0 یا 2 عمودی طاق ہوں۔ اگر اس میں طاق ڈگری کے 0 عمودی ہیں، تو یولیرین راستہ ایک یولیرین سرکٹ ہے۔ ایک ڈائریکٹڈ گراف ایک ڈائریکٹڈ سیوڈو فاریسٹ ہے اگر اور صرف اس صورت میں جب ہر ورٹیکس میں زیادہ سے زیادہ 1 آؤٹ ڈگری ہو۔ فنکشنل گراف ایک فرضی جنگل کا ایک خاص معاملہ ہے جس میں ہر سرے کی آؤٹ ڈگری بالکل 1 ہوتی ہے۔ بروکس تھیوریم کے مطابق، کلیک یا عجیب سائیکل کے علاوہ کسی بھی گراف G میں زیادہ سے زیادہ کرومیٹک نمبر ہوتا ہے، اور وائزنگ کے تھیوریم کے مطابق کسی بھی گراف میں زیادہ سے زیادہ کرومیٹک انڈیکس ہوتا ہے۔ کے-ڈیجینریٹ گراف ایک ایسا گراف ہے جس میں ہر ذیلی گراف میں زیادہ سے زیادہ کے پر ڈگری کا ایک ورٹیکس ہوتا ہے۔ یہ بھی دیکھیں انڈیگری، دو طرفہ گراف نوٹ حوالہ جات کے لیے ڈگری تقسیم ڈگری ترتیب کے لیے آؤٹ ڈگری۔ ۔ ۔ گراف تھیوری