Directed graph
ریاضی میں، اور خاص طور پر گراف تھیوری میں، ایک ڈائریکٹڈ گراف (یا ڈیگراف) ایک ایسا گراف ہے جو ڈائریکٹڈ کناروں سے جڑے عمودی حصوں کے ایک سیٹ سے بنا ہوتا ہے، جسے اکثر آرکس کہا جاتا ہے۔ تعریف رسمی اصطلاحات میں، ایک ہدایت شدہ گراف ایک ترتیب شدہ جوڑا ہے جہاں V ایک سیٹ ہے جس کے عناصر کو عمودی، نوڈس، یا پوائنٹس کہا جاتا ہے۔ A عمودی کے ترتیب شدہ جوڑوں کا ایک مجموعہ ہے، جسے آرکس، ہدایت شدہ کنارے (بعض اوقات صرف A کے بجائے E نامی متعلقہ سیٹ کے ساتھ کنارے)، تیر، یا ہدایت شدہ لائنیں کہتے ہیں۔ یہ ایک عام یا غیر ہدایت شدہ گراف سے مختلف ہے، اس میں مؤخر الذکر کی تعریف عمودی کے غیر ترتیب شدہ جوڑوں کے لحاظ سے کی جاتی ہے، جنہیں عام طور پر کنارے، لنکس یا لائنیں کہا جاتا ہے۔ مذکورہ بالا تعریف ایک ہدایت شدہ گراف کو ایک ہی ماخذ اور ہدف نوڈس کے ساتھ متعدد تیروں کی اجازت نہیں دیتی ہے، لیکن کچھ مصنفین ایک وسیع تر تعریف پر غور کرتے ہیں جو ہدایت شدہ گراف کو اس طرح کے متعدد آرکس رکھنے کی اجازت دیتی ہے (یعنی، وہ آرک سیٹ کو ملٹی سیٹ ہونے کی اجازت دیتے ہیں)۔ بعض اوقات ان اداروں کو ڈائریکٹڈ ملٹی گراف (یا ملٹی گراف) کہا جاتا ہے۔ دوسری طرف، مذکورہ بالا تعریف ایک ہدایت شدہ گراف کو لوپس رکھنے کی اجازت دیتی ہے (یعنی آرکس جو براہ راست نوڈس کو اپنے ساتھ جوڑتے ہیں)، لیکن کچھ مصنفین ایک تنگ تعریف پر غور کرتے ہیں جو ہدایت شدہ گراف کو لوپس رکھنے کی اجازت نہیں دیتا ہے۔ لوپس کے بغیر ڈائریکٹڈ گراف کو سادہ ڈائریکٹڈ گراف کہا جا سکتا ہے، جبکہ لوپس کے ساتھ ڈائریکٹڈ گراف کو لوپ-ڈیگراف کہا جا سکتا ہے (سیکشن دیکھیں ڈائریکٹڈ گراف کی اقسام)۔ ہدایت شدہ گراف کی اقسام ذیلی کلاسیں ہم آہنگ ہدایت شدہ گراف ہدایت شدہ گراف ہوتے ہیں جہاں تمام کنارے دو بار ظاہر ہوتے ہیں، ہر سمت میں ایک (یعنی ہر تیر کے لیے جو ڈیگراف سے تعلق رکھتا ہے، متعلقہ الٹا تیر بھی اس سے تعلق رکھتا ہے)۔ (اس طرح کے کنارے کو بعض اوقات "بائی ڈائریکٹڈ" کہا جاتا ہے اور اس طرح کے گراف کو بعض اوقات "بائی ڈائریکٹڈ" کہا جاتا ہے، لیکن یہ بائی ڈائریکٹڈ گراف کے معنی سے متصادم ہے۔) سادہ ڈائریکٹڈ گراف ایسے ڈائریکٹڈ گراف ہوتے ہیں جن میں کوئی لوپ (تیر جو سیدھے عمودی حصوں کو خود سے جوڑتے ہیں) نہیں ہوتے ہیں اور ایک ہی ماخذ اور ٹارگٹ نوڈس کے ساتھ متعدد تیر نہیں ہوتے ہیں۔ جیسا کہ پہلے ہی متعارف کرایا گیا ہے، متعدد تیروں کی صورت میں وجود کو عام طور پر ڈائریکٹڈ ملٹی گراف کے طور پر خطاب کیا جاتا ہے۔ کچھ مصنفین لوپس والے ڈیگراف کو لوپ-ڈیگراف کے طور پر بیان کرتے ہیں۔ مکمل ڈائریکٹڈ گراف سادہ ڈائریکٹڈ گراف ہوتے ہیں جہاں عمودی کے ہر جوڑے کو ڈائریکٹڈ آرکس کے سمیٹرک جوڑے سے جوڑا جاتا ہے (یہ ایک غیر ڈائریکٹڈ مکمل گراف کے برابر ہوتا ہے جس کے کناروں کو الٹا آرکس کے جوڑوں سے تبدیل کیا جاتا ہے)۔ اس کے بعد ایک مکمل ڈیگراف ہم آہنگ ہوتا ہے۔ نیم مکمل ملٹی پارٹیٹ ڈیگراف سادہ ڈیگراف ہوتے ہیں جن میں ورٹیکس سیٹ کو سیٹوں میں اس طرح تقسیم کیا جاتا ہے کہ مختلف سیٹوں میں عمودی x اور y کے ہر جوڑے کے لیے، x اور y کے درمیان ایک آرک ہوتا ہے۔ x اور y کے درمیان ایک آرک یا مخالف سمتوں میں دو آرک ہو سکتے ہیں۔ نیم مکمل ڈیگراف سادہ ڈیگراف ہوتے ہیں جہاں عمودی کے ہر جوڑے کے درمیان ایک آرک ہوتا ہے۔ ہر نیم مکمل ڈیگراف معمولی انداز میں ایک نیم مکمل ملٹی پارٹیٹ ڈیگراف ہوتا ہے، جس میں ہر ورٹیکس پارٹیشن کا ایک سیٹ تشکیل دیتا ہے۔ نیم عارضی ڈیگراف سادہ ڈیگراف ہوتے ہیں جہاں x سے y اور y سے z تک کے آرکس والے الگ الگ عمودی حصوں کے ہر ٹرپل x، y، z کے لیے x اور z کے درمیان ایک آرک ہوتا ہے۔ x اور z کے درمیان صرف ایک آرک یا مخالف سمتوں میں دو آرک ہو سکتے ہیں۔ ایک نیم مکمل ڈیگراف ایک نیم عارضی ڈیگراف ہے۔ نیم عارضی ڈیگراف کی توسیعات ہیں جنہیں کے-نیم عارضی ڈیگراف کہا جاتا ہے۔ مبنی گراف ہدایت شدہ گراف ہوتے ہیں جن میں ہدایت شدہ کناروں کے مخالف جوڑے نہیں ہوتے ہیں (یعنی۔ زیادہ سے زیادہ ایک اور گراف کے تیر ہو سکتے ہیں)۔ اس کے بعد ایک ہدایت شدہ گراف ایک مبنی گراف ہے اگر اور صرف اس صورت میں جب اس کا کوئی 2-سائیکل نہ ہو۔ (یہ "مبنی گراف" کا واحد معنی نہیں ہے ؛ واقفیت (گراف تھیوری) دیکھیں۔) ٹورنامنٹ غیر ہدایت شدہ مکمل گراف میں ہر کنارے کے لیے سمت کا انتخاب کرکے حاصل کیے گئے مبنی گراف ہوتے ہیں۔ ٹورنامنٹ ایک نیم مکمل ڈیگراف ہوتا ہے۔ ایک ڈائریکٹڈ گراف ایسیکلک ہوتا ہے اگر اس میں کوئی ڈائریکٹڈ سائیکل نہ ہو۔ اس طرح کے ڈیگراف کا عام نام ڈائریکٹڈ ایسائکلک گراف (ڈی اے جی) ہے۔ ملٹی ٹری ڈی اے جی ہوتے ہیں جن میں ایک ہی ابتدائی سرے سے ایک ہی اختتامی سرے تک کوئی دو الگ الگ راستے نہیں ہوتے ہیں۔ پر مبنی درخت یا پولی ٹری ڈی اے جی ہوتے ہیں جو درختوں کے کناروں کو سمت دے کر بنائے جاتے ہیں (جڑے ہوئے، ایسائکلک غیر ہدایت شدہ گراف)۔ جڑوں والے درخت ایسے درخت ہوتے ہیں جن میں بنیادی غیر ہدایت شدہ درخت کے تمام کناروں کو یا تو جڑ سے دور یا اس کی طرف ہدایت دی جاتی ہے (انہیں بالترتیب آربوریسینس یا آؤٹ ٹری اور ان ٹری کہا جاتا ہے۔ ضمیمہ خصوصیات والے ڈیگراف وزن والے ڈائریکٹڈ گراف (جسے ڈائریکٹڈ نیٹ ورک بھی کہا جاتا ہے) (سادہ) ڈائریکٹڈ گراف ہوتے ہیں جن کے وزن ان کے تیروں کو تفویض کیے جاتے ہیں، اسی طرح وزن والے گراف (جنہیں غیر ہدایت شدہ نیٹ ورک یا وزن والے نیٹ ورک بھی کہا جاتا ہے)۔ فلو نیٹ ورک وزنی ڈائریکٹڈ گراف ہوتے ہیں جہاں دو نوڈس کو ممتاز کیا جاتا ہے، ایک ماخذ اور ایک سنک۔ جڑوں والے ڈائریکٹڈ گراف (جسے فلو گراف بھی کہا جاتا ہے) ڈیگراف ہوتے ہیں جن میں ایک ورٹیکس کو جڑ کے طور پر ممتاز کیا گیا ہے۔ کنٹرول فلو گراف جڑے ہوئے ڈیگراف ہوتے ہیں جو کمپیوٹر سائنس میں ان راستوں کی نمائندگی کے طور پر استعمال ہوتے ہیں جو اس کے نفاذ کے دوران کسی پروگرام سے گزر سکتے ہیں۔ سگنل فلو گراف ہدایت شدہ گراف ہوتے ہیں جن میں نوڈس نظام کے متغیرات کی نمائندگی کرتے ہیں اور شاخیں (کنارے، آرکس، یا تیر) نوڈس کے جوڑوں کے درمیان فعال رابطوں کی نمائندگی کرتے ہیں۔ بہاؤ گراف لکیری الجبرائی یا تفریقی مساوات کے ایک سیٹ سے وابستہ ڈیگراف ہوتے ہیں۔ ریاستی خاکے ہدایت شدہ ملٹی گراف ہوتے ہیں جو محدود ریاستی مشینوں کی نمائندگی کرتے ہیں۔ مواصلاتی خاکے زمرہ نظریہ میں استعمال ہونے والے ڈیگراف ہیں، جہاں عمودی (ریاضیاتی) اشیاء کی نمائندگی کرتے ہیں اور تیر مورفزم کی نمائندگی کرتے ہیں، اس خاصیت کے ساتھ کہ ایک ہی آغاز اور اختتامی نکات والے تمام سمت والے راستے ساخت کے لحاظ سے ایک ہی نتیجہ کی طرف لے جاتے ہیں۔ لائ گروپوں کے نظریہ میں، کوئور کیو ایک ہدایت شدہ گراف ہے جو ڈومین کے طور پر کام کرتا ہے، اور اس طرح ایک نمائندگی V کی شکل کی خصوصیت کرتا ہے، جسے فنکٹر کے طور پر بیان کیا گیا ہے، خاص طور پر فنکٹر زمرے FinVctKF (Q) کا ایک آبجیکٹ جہاں F (Q) Q پر آزاد زمرہ ہے جو Q میں راستوں پر مشتمل ہے اور FinVctK ایک فیلڈ K پر محدود جہتی ویکٹر خالی جگہوں کا زمرہ ہے۔ کوئور کی نمائندگی اس کے عمودی حصوں کو ویکٹر خالی جگہوں اور اس کے کناروں (اور اس وجہ سے راستوں) کے ساتھ مطابقت رکھتی ہے جو ان کے درمیان لکیری تبدیلیوں کے ساتھ مطابقت رکھتی ہے، اور قدرتی تبدیلیوں کے ذریعے تبدیل ہوتی ہے۔ بنیادی اصطلاحات ایک آرک کو x سے y تک ہدایت شدہ سمجھا جاتا ہے۔ y کو سر کہا جاتا ہے اور x کو آرک کی دم کہا جاتا ہے۔ y کو x کا براہ راست جانشین کہا جاتا ہے اور x کو y کا براہ راست پیشرو کہا جاتا ہے۔ اگر کوئی راستہ x سے y کی طرف جاتا ہے، تو y کو x کا جانشین اور x سے قابل رسائی کہا جاتا ہے، اور x کو y کا پیشرو کہا جاتا ہے۔ آرک کو ریورسڈ آرک آف کہا جاتا ہے۔ لوپس کے ساتھ ملٹی گراف کا ملٹی گراف کا ملٹی گراف کا ملٹی گراف انٹیجر ویلیوڈ میٹرکس ہے جس میں قطاریں اور کالم عمودی سے مطابقت رکھتے ہیں، جہاں ایک غیر اخترن اندراج aij عمودی i سے عمودی j تک آرکس کی تعداد ہے، اور اخترن اندراج ai عمودی i پر لوپس کی تعداد ہے۔ ہدایت شدہ گراف کا ملحقہ میٹرکس ایک منطقی میٹرکس ہے، اور قطاریں اور کالموں کی ترتیب تک منفرد ہے۔ ڈائریکٹڈ گراف کے لیے ایک اور میٹرکس کی نمائندگی اس کا انسیڈنس میٹرکس ہے۔ مزید تعریفوں کے لیے سمت دیکھیں۔ کسی ورٹیکس کے لیے، ورٹیکس سے متصل سر کے سروں کی تعداد کو ورٹیکس کی انڈیگری کہا جاتا ہے اور ورٹیکس سے متصل دم کے سروں کی تعداد اس کی آؤٹ ڈگری ہوتی ہے (جسے درختوں میں برانچنگ فیکٹر کہا جاتا ہے)۔ لیٹ اینڈ۔ v کی انڈیگری کو ڈیگ − (v) اور اس کی آؤٹ ڈگری کو ڈیگ + (v) سے ظاہر کیا جاتا ہے۔ اس کے ساتھ ایک ورٹیکس کو ماخذ کہا جاتا ہے، کیونکہ یہ اس کے ہر آنے والے آرکس کی ابتدا ہے۔ اسی طرح، اس کے ساتھ ایک ورٹیکس کو سنک کہا جاتا ہے، کیونکہ یہ اس کے آنے والے آرکس میں سے ہر ایک کا اختتام ہے۔ ڈگری سم فارمولا بیان کرتا ہے کہ، ایک ہدایت شدہ گراف کے لیے، اگر ہر سرے کے لیے، گراف کو متوازن ہدایت شدہ گراف کہا جاتا ہے۔ ڈگری سیکوینس ایک ڈائریکٹڈ گراف کی ڈگری سیکوینس اس کے انڈیگری اور آؤٹ ڈگری جوڑوں کی فہرست ہے۔ مندرجہ بالا مثال کے لیے ہمارے پاس ڈگری سیکوینس ((2، 0)، (2، 2)، (0، 2)، (1، 1) ہے۔ ڈگری سیکوینس ایک ڈائریکٹڈ گراف غیر متغیر ہے لہذا آئسومورفک ڈائریکٹڈ گراف کی ڈگری سیکوینس ایک جیسی ہوتی ہے۔ تاہم، ڈگری کی ترتیب، عام طور پر، ایک ہدایت شدہ گراف کی منفرد طور پر شناخت نہیں کرتی ہے۔ کچھ معاملات میں، غیر آئسومورفک ڈیگراف کی ڈگری کی ترتیب ایک جیسی ہوتی ہے۔ ڈائریکٹڈ گراف کی وصولی کا مسئلہ ڈگری کی ترتیب کے ساتھ ایک ڈائریکٹڈ گراف تلاش کرنے کا مسئلہ ہے جو مثبت انٹیجر جوڑوں کی دی گئی ترتیب ہے۔ (صفر کے ٹریلنگ جوڑوں کو نظر انداز کیا جا سکتا ہے کیونکہ ہدایت شدہ گراف میں الگ تھلگ عمودی کی مناسب تعداد شامل کرکے ان کا معمولی احساس ہوتا ہے۔) ایک ترتیب جو کسی ہدایت شدہ گراف کی ڈگری ترتیب ہے، یعنی۔ جس کے لیے ڈائریکٹڈ گراف کے احساس کے مسئلے کا حل ہوتا ہے، اسے ڈائریکٹڈ گرافک یا ڈائریکٹڈ گرافیکل سیکوینس کہا جاتا ہے۔ اس مسئلے کو یا تو کلیٹ مین-وانگ الگورتھم یا فلکرسن-چین-اینسٹی تھیوریم کے ذریعے حل کیا جا سکتا ہے۔ ڈائریکٹڈ گراف کنیکٹیویٹی ایک ڈائریکٹڈ گراف کمزور طور پر جڑا ہوا ہے (یا صرف جڑا ہوا ہے) اگر گراف کے تمام ڈائریکٹڈ کناروں کو غیر ہدایت شدہ کناروں سے بدل کر حاصل کیا گیا غیر ہدایت شدہ بنیادی گراف ایک منسلک گراف ہے۔ ایک ہدایت شدہ گراف مضبوطی سے جڑا ہوا یا مضبوط ہوتا ہے اگر اس میں عمودی کے ہر جوڑے کے لیے x سے y (اور y سے x) تک ایک ہدایت شدہ راستہ ہو۔ مضبوط اجزاء زیادہ سے زیادہ مضبوطی سے جڑے ہوئے ذیلی گراف ہیں۔ جڑے ہوئے جڑوں والا گراف (یا بہاؤ کا گراف) وہ ہوتا ہے جہاں ایک ممتاز جڑ کے سرے سے ہر سرے کی طرف ایک ہدایت شدہ راستہ موجود ہوتا ہے۔ نوٹ حوالہ جات بھی دیکھیں (2007 کا درست شدہ پہلا ایڈیشن اب مصنفین کی سائٹ پر آزادانہ طور پر دستیاب ہے ؛ دوسرا ایڈیشن 2009 میں شائع ہوا)۔ ۔ ۔ (الیکٹرانک تیسرا ایڈیشن مصنف کی ویب سائٹ پر مفت دستیاب ہے)۔ ۔ انٹیجر سیکوینسز کے آن لائن انسائیکلوپیڈیا سے n نوڈس کے ساتھ ڈائریکٹڈ گرافز (یا ڈائریکٹڈ گرافز) کی تعداد بیرونی لنکس ڈائریکٹڈ گرافز گراف تھیوری گراف ڈیٹا ڈھانچے