Rooted graph
ریاضی میں، اور، خاص طور پر، گراف تھیوری میں، جڑا ہوا گراف ایک ایسا گراف ہے جس میں ایک سرے کو جڑ کے طور پر ممتاز کیا گیا ہے۔ جڑوں والے گراف کے ہدایت شدہ اور غیر ہدایت شدہ دونوں ورژنوں کا مطالعہ کیا گیا ہے، اور مختلف تعریفیں بھی ہیں جو متعدد جڑوں کی اجازت دیتی ہیں۔ جڑوں والے گراف کو (ان کے اطلاق کے لحاظ سے) نکیلی گراف یا بہاؤ گراف کے طور پر بھی جانا جا سکتا ہے۔ ان گرافوں کی کچھ ایپلی کیشنز میں، ایک اضافی ضرورت ہے کہ پورا گراف جڑ کے سرے سے قابل رسائی ہو۔ تغیرات ٹپوولوجیکل گراف تھیوری میں، جڑوں والے گراف کے تصور کو متعدد عمودی یا متعدد کناروں کو جڑوں کے طور پر سمجھنے کے لیے بڑھایا جا سکتا ہے۔ سابقہ کو بعض اوقات ورٹیکس روٹڈ گراف کہا جاتا ہے تاکہ اس تناظر میں انہیں ایج روٹڈ گراف سے ممتاز کیا جا سکے۔ جڑوں کے طور پر نامزد متعدد نوڈس والے گراف بھی بے ترتیب گراف کے علاقے میں امتزاج میں کچھ دلچسپی رکھتے ہیں۔ ان گرافوں کو ملٹی پلائی روٹڈ گراف بھی کہا جاتا ہے۔ جڑے ہوئے ڈائریکٹڈ گراف یا جڑے ہوئے ڈیگراف کی اصطلاحات میں بھی تعریفوں میں تغیر نظر آتا ہے۔ واضح ٹرانسپلانٹ یہ ہے کہ کسی خاص نوڈ کو جڑ کے طور پر شناخت کرکے جڑ والے ڈیگراف پر غور کیا جائے۔ تاہم، کمپیوٹر سائنس میں، یہ اصطلاحات عام طور پر ایک تنگ تصور کی طرف اشارہ کرتی ہیں۔ یعنی، جڑوں سے جڑا ہوا ڈائریکٹڈ گراف ایک ڈیگراف ہے جس میں ایک ممتاز نوڈ r ہوتا ہے، جیسے کہ r سے r کے علاوہ کسی بھی نوڈ تک جانے کا ایک ہدایت شدہ راستہ ہوتا ہے۔ زیادہ عمومی تعریف دینے والے مصنفین منسلک جڑوں والے ڈیگراف یا قابل رسائی جڑوں والے گراف (دیکھیں) کے طور پر حوالہ دے سکتے ہیں۔ آرٹ آف کمپیوٹر پروگرامنگ جڑے ہوئے ڈیگراف کی قدرے زیادہ وسیع پیمانے پر وضاحت کرتا ہے، یعنی، ایک ہدایت شدہ گراف کو جڑا ہوا کہا جاتا ہے اگر اس میں کم از کم ایک نوڈ ہو جو دوسرے تمام نوڈس تک پہنچ سکے۔ نوتھ نوٹ کرتے ہیں کہ اس طرح بیان کردہ تصور مضبوطی سے جڑے ہوئے اور جڑے ہوئے ڈیگراف کے تصورات کے درمیان ایک قسم کا انٹرمیڈیٹ ہے۔ ایپلی کیشنز فلو گراف کمپیوٹر سائنس میں، جڑے ہوئے گراف جن میں جڑ کا عمودی حصہ دیگر تمام عمودی حصوں تک پہنچ سکتا ہے، فلو گراف یا فلو گراف کہلاتے ہیں۔ بعض اوقات ایک اضافی پابندی شامل کی جاتی ہے جس میں یہ واضح کیا جاتا ہے کہ بہاؤ کے گراف میں ایک واحد اخراج (سنک) ورٹیکس ہونا ضروری ہے۔ فلو گراف کو فلو چارٹ کے خلاصہ کے طور پر دیکھا جا سکتا ہے، جس میں غیر ساختی عناصر (نوڈ کے مندرجات اور اقسام) کو ہٹا دیا جاتا ہے۔ شاید فلو گراف کی سب سے مشہور ذیلی کلاس کنٹرول فلو گراف ہیں، جو مرتب کرنے والوں اور پروگرام کے تجزیے میں استعمال ہوتے ہیں۔ ایک من مانی بہاؤ گراف کو ہر کنارے پر کنارے کا سنکچن انجام دے کر کنٹرول فلو گراف میں تبدیل کیا جا سکتا ہے جو اس کے منبع سے واحد باہر جانے والا کنارہ ہے اور اس کے ہدف میں آنے والا واحد کنارہ ہے۔ عام طور پر استعمال ہونے والا ایک اور قسم کا فلو گراف کال گراف ہے، جس میں نوڈس پورے سبروٹینز سے مطابقت رکھتے ہیں۔ فلو گراف کے عمومی تصور کو پروگرام گراف کہا گیا ہے، لیکن یہی اصطلاح صرف کنٹرول فلو گراف کو ظاہر کرنے کے لیے بھی استعمال کی گئی ہے۔ بہاؤ کے گراف کو غیر لیبل شدہ فلو گراف اور مناسب فلو گراف بھی کہا جاتا ہے۔ یہ گراف بعض اوقات سافٹ ویئر ٹیسٹنگ میں استعمال ہوتے ہیں۔ جب ایک ہی اخراج کی ضرورت ہوتی ہے تو، بہاؤ گراف کی دو خصوصیات ہوتی ہیں جو عام طور پر ہدایت شدہ گراف کے ساتھ مشترک نہیں ہوتی ہیں: بہاؤ گراف کو نیسٹ کیا جا سکتا ہے، جو کہ سبروٹین کال کے مساوی ہے (حالانکہ پاسنگ پیرامیٹرز کا کوئی تصور نہیں ہے)، اور بہاؤ گراف کو بھی ترتیب دیا جا سکتا ہے، جو کوڈ کے دو ٹکڑوں کے ترتیب وار نفاذ کے مساوی ہے۔ پرائم فلو گراف کی تعریف فلو گراف کے طور پر کی جاتی ہے جسے ذیلی گراف کے منتخب کردہ نمونے کا استعمال کرتے ہوئے نیسٹنگ یا سیکوینسنگ کے ذریعے ختم نہیں کیا جا سکتا، مثال کے طور پر اسٹرکچرڈ پروگرامنگ کے ابتدائی۔ نظریاتی تحقیق کا تعین کرنے پر کیا گیا ہے، مثال کے طور پر، گرافوں کے منتخب کردہ سیٹ کو دیکھتے ہوئے پرائم فلو گرافوں کا تناسب۔ سیٹ تھیوری پیٹر ایکزل نے جڑوں والے ڈائریکٹڈ گراف کا استعمال اس طرح کیا ہے کہ ہر نوڈ جڑ سے قابل رسائی ہو (جسے وہ قابل رسائی نوک دار گراف کہتے ہیں) تاکہ غیر قائم شدہ سیٹ تھیوری میں ایکزل کے اینٹی فاؤنڈیشن محور کو وضع کیا جا سکے۔ اس تناظر میں، ایک قابل رسائی نوک دار گراف کا ہر ورٹیکس ایکزل کے (غیر اچھی طرح سے قائم) سیٹ تھیوری کے اندر ایک (غیر اچھی طرح سے قائم) سیٹ کا نمونہ بناتا ہے، اور ایک ورٹیکس V سے ایک ورٹیکس W ماڈل تک ایک آرک جو کہ v ڈبلیو کا ایک عنصر ہے۔ ایکزل کے اینٹی فاؤنڈیشن محور میں کہا گیا ہے کہ ہر قابل رسائی نوک دار گراف اس طرح سے سیٹ (غیر اچھی طرح سے قائم) کے خاندان کا نمونہ بناتا ہے۔ مشترکہ گیم تھیوری ایک مشترکہ گیم کو دیکھتے ہوئے، ایک منسلک جڑوں والا ڈائریکٹڈ گراف ہوتا ہے جس کے عمودی حصے گیم پوزیشن ہوتے ہیں اور جن کے کنارے حرکت کرتے ہیں، اور جڑ سے شروع ہونے والے گراف ٹریورسل کو گیم ٹری بنانے کے لیے استعمال کیا جاتا ہے۔ اگر گراف میں ڈائریکٹڈ سائیکل ہوتے ہیں، تو گیم میں ایک پوزیشن لامحدود کئی بار دہرائی جا سکتی ہے، اور عام طور پر کھیل کو غیر معینہ مدت تک جاری رہنے سے روکنے کے لیے قواعد کی ضرورت ہوتی ہے۔ بصورت دیگر، گراف ایک ڈائریکٹڈ ایسائکلک گراف ہے، اور اگر یہ جڑا ہوا درخت نہیں ہے، تو گیم میں ٹرانسپوزیشن ہوتی ہے۔ یہ گراف اور اس کی ٹوپولوجی گیم کی پیچیدگی کے مطالعہ میں اہم ہیں، جہاں اسٹیٹ اسپیس کی پیچیدگی گراف میں عمودی حصوں کی تعداد ہے، گیم کی اوسط لمبائی عمودی حصوں کی اوسط تعداد ہے جو جڑ سے کسی عمودی حصے تک بغیر کسی براہ راست جانشین کے گزرتی ہے، اور گیم ٹری کا اوسط شاخ سازی عنصر گراف کی اوسط آؤٹ ڈگری ہے۔ مشترکہ گنتی 1، 2، نوڈس کے لیے جڑے ہوئے غیر ہدایت شدہ گرافوں کی تعداد 1، 2، 6، 20، 90، 544، ہے۔ متعلقہ تصورات دلچسپی کا ایک خاص معاملہ جڑوں والے درخت ہیں، وہ درخت جن کی جڑوں کا ایک ممتاز ورٹیکس ہے۔ اگر جڑوں والے ڈیگراف میں جڑ سے ہدایت شدہ راستے اضافی طور پر منفرد ہونے تک محدود ہیں، تو حاصل کردہ تصور (جڑوں والے) آربوریسنس کا ہے-جو جڑوں والے درخت کے مساوی ہدایت شدہ گراف ہے۔ جڑے ہوئے گراف میں ایک ہی جڑ کے ساتھ ایک آربوریسینس ہوتا ہے اگر اور صرف اس صورت میں جب پورے گراف تک جڑ سے پہنچا جا سکے، اور کمپیوٹر سائنس دانوں نے زیادہ سے زیادہ آربوریسینس تلاش کرنے کے الگورتھمک مسائل کا مطالعہ کیا ہے۔ جڑوں والے گراف کو گراف کے جڑوں والے پروڈکٹ کا استعمال کرتے ہوئے جوڑا جا سکتا ہے۔ کے-ورٹیکس سے منسلک گراف پوائنٹڈ سیٹ حوالہ جات مزید پڑھنا بیرونی لنکس گراف کی توسیعات اور عمومی کاریاں بھی دیکھیں۔