انفارمیشنکس میں گراف: تعریف، اقسام، ایپلی کیشنز، مثالیں. کمپیوٹر سائنس میں گرافکس کا نظریہ

انفارمیشنکس میں گراف عناصر کے ایک مجموعہ میں تعلقات کی وضاحت کرنے کا ایک طریقہ ہیں. یہ گراف اصول کے مطالعہ کی اہم چیزیں ہیں .

بنیادی تعریفیں

کمپیوٹر سائنس میں گراف کیا ہے؟ یہ عمودی یا نوڈس نامی اشیاء کی ایک سیٹ بھی شامل ہے، جس میں کچھ جوڑے نام نہاد کے ساتھ منسلک ہیں. ریب مثال کے طور پر، شکل (الف) میں گراف چار نوڈس پر مشتمل ہے، جس میں A، B، C، اور D نامزد ہوتا ہے، جس میں بی کناروں کی طرف سے دوسرے تین عمودیوں سے منسلک ہوتا ہے، اور سی اور ڈی بھی منسلک ہیں. اگر وہ کنارے سے منسلک ہوتے ہیں تو دو نوڈس ملحق ہیں. یہ اعداد و شمار انفارمیشنکس میں گراف کی تعمیر کا ایک عام طریقہ دکھاتا ہے. حلقوں کو عمودی طور پر پیش کرتا ہے، اور ان میں سے ہر ایک کو منسلک کرنے والی لائنز ریب ہیں.

کمپیوٹر سائنس میں غیر مبنی گراف کیا جاتا ہے؟ رب کے دو سروں کے درمیان ان کا تعلق ہموار ہے. رش صرف ان کو ایک دوسرے سے جوڑتا ہے. بہت سے معاملات میں، تاہم، یہ لازمی ضروری ہے کہ غیر معمولی تعلقات کا اظہار کریں - مثال کے طور پر، حقیقت یہ ہے کہ A پوائنٹس بی، لیکن اس کے برعکس. یہ مقصد کمپیوٹر سائنس میں ایک گراف کی تعریف ہے، جس میں ابھی تک نوڈس کا ایک سیٹ بھی شامل ہے، جو ایک کنارے پر مشتمل ہے. ہر پرانی کنارے عمودی کے درمیان تعلق ہے، جس کی سمت ایک قدر ہے. اعداد و شمار (ب) میں دکھایا گیا ہے کے طور پر ہدایت شدہ گرافز کی نمائندگی کی جاتی ہے، ان کے کناروں تیر کی طرف سے نمائندگی کی جاتی ہیں. جب اس پر زور دیا جارہا ہے کہ گراف غیر رویہ ہے، اسے غیر مستقیم کہا جاتا ہے.

نیٹ ورک کے ماڈل

کمپیوٹر سائنس میں گرافس نیٹ ورک ڈھانچے کے ریاضیاتی ماڈل کے طور پر کام کرتی ہیں. مندرجہ ذیل اعداد و شمار دسمبر 1 9 70 میں انٹرنیٹ کے ڈھانچے کو ظاہر کرتا ہے، اس کے بعد ARPANET کہا جاتا ہے جب یہ صرف 13 پوائنٹس تھا. نوڈس کمپیوٹنگ مراکز ہیں، اور کناروں کو ان کے درمیان براہ راست کنکشن کے ساتھ دو عمودی طور پر جوڑتا ہے. اگر آپ امریکہ کے سپرد شدہ نقشے پر توجہ نہیں دیتے تو باقی تصویر پچھلے لوگوں کے ساتھ ایک 13 نوڈ گراف ہے. اس صورت میں، عمودی کی اصل ترتیب غیر معمولی ہے. یہ ضروری ہے کہ نوڈس ایک دوسرے سے منسلک ہوجائیں.

کمپیوٹر سائنس میں گرافوں کا استعمال آپ کو یہ تصور کرنے کی اجازت دیتا ہے کہ نیٹ ورک ڈھانچے میں ایک دوسرے سے جسمانی طور پر یا منطقی طور پر منطقی طور پر کیا تعلق ہے. 13 نوڈ ARPANET ایک مواصلاتی نیٹ ورک کا ایک مثال ہے جس میں کمپیوٹر کی عمودی یا دیگر آلات پیغامات کو منتقل کرسکتے ہیں، اور کنارے براہ راست روابط ہیں جس پر معلومات منتقل کی جا سکتی ہے.

راستے

اگرچہ بہت سے مختلف علاقوں میں گراف استعمال کیے جاتے ہیں، ان میں عام خصوصیات ہیں. گرافکس (کمپیوٹر سائنس) کے نظریہ، شاید، سب سے اہم ایک - خیال یہ ہے کہ چیزیں اکثر کنارے کے ساتھ منتقل ہوتے ہیں، مسلسل مسلسل نوڈ سے نوڈ سے گزرتے ہیں، چاہے وہ کسی پرواز سے متعلق معلومات یا سماجی نیٹ ورک میں شخص سے شخص کو منتقل کرنے والے مسافروں کے مسافر ہو. روابط کے بعد، کمپیوٹر، ترتیب کے چند صفحات کے صفحے پر ملاحظہ کرتے ہیں.

یہ خیال کناروں کی طرف سے منسلک عمودی کی ترتیب کے طور پر راستے کی تعریف کی حوصلہ افزائی کرتا ہے. کبھی کبھی ایسے راستے پر غور کرنے کے لئے ضروری ہو جاتا ہے جو نہ صرف نوڈس بلکہ ان سے منسلک کناروں کی ترتیب بھی. مثال کے طور پر، عمودی MIT، BBN، RAND، UCLA کے ترتیب انٹرنیٹ گراف ARPANET میں ایک راستہ ہے. نوڈس اور کناروں کی منظوری دو بار کی جا سکتی ہے. مثال کے طور پر، ایس آر، اسٹین، یو سی ایل اے، ایس آر، یو آر اے، ایم آئی ٹی بھی ایک راستہ ہے. جس راستے میں کناروں کو دوبارہ نہیں جانا جاتا وہ ایک سلسلہ کہا جاتا ہے. اگر نوڈس بار بار نہیں آتے ہیں تو اسے ایک سادہ سلسلہ کہا جاتا ہے.

سائیکل

کمپیوٹر سائنس میں گرافکس کی خاص طور پر اہم قسمیں سائیکل ہیں، جس میں انگوٹی کی ساخت کی نمائندگی کرتی ہے، جیسے نوڈس لینکس، کیس، کارن، ہار وی، بی بی این، ایم آئی ٹی، لائنر. کم از کم تین کناروں کے ساتھ راستے، جس میں پہلی اور آخری نوڈ ایک ہی ہیں، اور دیگر مختلف ہیں، کمپیوٹر سائنس میں سائیکلکل گرافکس ہیں.

مثال: سائیکل سری لنکا، اسٹین، یو ایس سی اے، ایس آر آر سب سے کم ہے، اور ایس آر، اسٹین، یو ایل سی اے، رینڈ، بی بی این، یو آر اے، بہت بڑا ہے.

دراصل، ARPANET گراف کے ہر کنارے ایک سائیکل سے تعلق رکھتا ہے. یہ جان بوجھ کر کیا گیا تھا: اگر ان میں سے کوئی بھی ناکام ہوجاتا ہے، تو ایک نوڈ سے کسی دوسرے کو منتقل کرنے کا امکان ہوگا. مواصلات اور نقل و حمل کے نظام میں سائیکل بے حد مہیا کرنے کے لئے موجود ہیں - وہ ایک مختلف راہ راست کے ساتھ متبادل راستے فراہم کرتے ہیں. سوشل نیٹ ورک میں، سائیکلوں کو اکثر دیکھا جاتا ہے. جب آپ ڈھونڈتے ہیں تو، آپ کی بیوی کے چچا کے قریب قریبی سکول دوست آپ کے بھائی کے ساتھ کام کررہا ہے، یہ ایک ایسا سائیکل ہے جس میں آپ کی بیوی، اس کے چچا، اس کے دوست دوست، اس کے ملازم بھائی) اور آخر میں، پھر آپ.

منسلک گراف: تعریف (مطلع)

قدرتی طور پر یہ پوچھنا ضروری ہے کہ آیا ہر نوڈ سے کسی دوسرے نوڈ میں حاصل کرنا ممکن ہے. اگر ہر ایک جوڑی کے درمیان ایک راستہ ہے تو ایک گراف متعدد ہے. مثال کے طور پر، ARPANET نیٹ ورک ایک منسلک گراف ہے. سب سے زیادہ مواصلات اور ٹرانسپورٹ کے نیٹ ورک کے بارے میں یہ کہا جا سکتا ہے، کیونکہ ان کا مقصد ایک نوڈ سے دوسرا ٹریفک براہ راست ہے.

دوسری جانب، کمپیوٹر کی سائنس میں ان قسم کے گرافوں کو وسیع پیمانے پر وسیع کرنے کی کوئی وجہ نہیں ہے. مثال کے طور پر، سوشل نیٹ ورک میں دو لوگوں کو تصور کرنا مشکل نہیں ہے جو ایک دوسرے سے منسلک نہیں ہیں.

اجزاء

اگر کمپیوٹر سائنس میں گراف منسلک نہیں ہیں، تو وہ قدرتی طور پر متعلقہ ٹکڑے ٹکڑے، نوڈس کے گروہوں میں شامل ہیں جو الگ الگ اور غیر انتباہ ہوتے ہیں. مثال کے طور پر، اعداد و شمار تین ایسے حصوں سے ظاہر ہوتا ہے: پہلا - A اور B، دوسرا - سی، ڈی اور ای، اور تیسری باقی باقی عمارات پر مشتمل ہوتا ہے.

ایک گراف کنیکٹوٹی کے اجزاء نوڈس کے سبسڈی ہیں جس میں:

• ذیلی گروپ کے ہر عمودی میں کسی دوسرے کا کوئی راستہ ہے؛
• ایک ذیلی سیٹ ایک بڑا سیٹ کا حصہ نہیں ہے جس میں ہر نوڈ میں کسی دوسرے کا راستہ ہے.

جب کمپیوٹر سائنس میں گرافس ان کے اجزاء میں تقسیم ہوتے ہیں تو یہ صرف ان کی ساخت کی وضاحت کا ابتدائی طریقہ ہے. اس جزو کے اندر اندر ایک امیر اندرونی ساختہ ہوسکتا ہے جو نیٹ ورک کی تشریح کے لئے ضروری ہے. مثال کے طور پر، نوڈ کی اہمیت کا تعین کرنے کا ایک رسمی طریقہ یہ ہے کہ گریڈ تقسیم ہوجائیں، اگر نوڈ کو ہٹایا جاتا ہے تو.

زیادہ سے زیادہ جزو

کنیکٹوٹی اجزاء کی کوالٹی تشخیص کا ایک طریقہ ہے. مثال کے طور پر، اگر وہ دوست ہیں تو دو لوگوں کے درمیان رابطے کے ساتھ ایک عالمی سوشل نیٹ ورک ہے.

کیا وہ منسلک ہے؟ شاید نہیں. منسلک ایک انتہائی نازک جائیداد ہے، اور ایک نوڈ کے رویے (یا ان کا ایک چھوٹا سا سیٹ) اسے نگل سکتا ہے. مثال کے طور پر، کوئی زندہ دوستوں کے ساتھ کوئی فرد ایک اجزاء نہیں ہوتا جس میں واحد عمودی مشتمل ہے، اور اس وجہ سے گراف متعدد نہیں ہوگا. یا ایک ریموٹ اشنکٹبندیی جزیرے، جن لوگوں پر مشتمل ہے جو باہر کی دنیا کے ساتھ کوئی تعلق نہیں رکھتے ہیں، بھی نیٹ ورک کا ایک چھوٹا سا جزو ہوگا، جو اس کی بے مثالیت کی تصدیق کرتی ہے.

دوستوں کے عالمی نیٹ ورک

لیکن کچھ اور ہے. مثال کے طور پر، ایک مقبول کتاب کے قارئین کو دوستی ہے جو دوسرے ممالک میں بڑھا اور ان کے ساتھ ایک جزو بناتا ہے. اگر آپ ان دوستوں اور ان کے دوستوں کے والدین کو اکاؤنٹ میں لے جاتے ہیں، تو یہ سب لوگ اسی اجزاء میں بھی ہوتے ہیں، اگرچہ انہوں نے کبھی بھی قاری سے نہیں سنا ہے، ایک مختلف زبان بولتے ہیں اور کبھی کبھی اس کے ساتھ نہیں ہوتے ہیں. اس طرح، جبکہ عالمی دوستی نیٹ ورک کو متفق نہیں ہے، قارئین ایک بہت بڑے جزو میں داخل ہوجائے گی جس میں دنیا کے تمام حصوں میں داخل ہوجائے گی، بشمول مختلف پس منظر کے لوگوں سمیت، اور حقیقت میں، دنیا کی آبادی کا بڑا حصہ بھی شامل ہے.

نیٹ ورک کے اعداد و شمار کے بڑے بڑے، پیچیدہ نیٹ ورکوں کے لئے یہ وہی ہے جو اکثر نوڈس میں اہم حصہ شامل ہے. اس کے علاوہ، جب نیٹ ورک زیادہ سے زیادہ اجزاء پر مشتمل ہے تو یہ تقریبا ایک ہی ہے. سمجھنے کے لئے کیوں، ہمیں دوستی کے عالمی نیٹ ورک کے ساتھ مثال پر واپس جانا چاہئے اور دو زیادہ سے زیادہ اجزاء کی موجودگی کا تصور کرنے کی کوشش کریں، جن میں سے ہر ایک لاکھ افراد شامل ہیں. اس کو ایک اجزاء کی موجودگی میں سے ایک سے پہلے اجزاء میں سے دوسرا حصہ کی ضرورت ہوتی ہے، تاکہ دو زیادہ سے زیادہ اجزاء ایک میں مل جائیں. چونکہ کنارے منفرد ہے، زیادہ تر معاملات میں یہ ناقابل اعتماد ہے کہ یہ فارم نہیں بناتا ہے، اور اس وجہ سے حقیقی نیٹ ورکس میں دو زیادہ سے زیادہ اجزاء کبھی نہیں دیکھے جاتے ہیں.

کچھ غیر معمولی معاملات میں، جب ایک زیادہ سے زیادہ اجزاء ایک حقیقی نیٹ ورک میں طویل عرصے سے ہم آہنگ ہوتے ہیں تو ان کی متحد غیر متوقع، ڈرامائی اور آخر میں، تباہی کا نتیجہ تھا.

اجزاء فیوژن کریش

مثال کے طور پر، مغربی آب و ہوا کے تہذیب میں یورپی محققین کے آنے کے بعد، تقریبا ایک ملین سال پہلے، ایک گلوبل کیتھی ہوئی. نیٹ ورک نقطہ نظر سے، اس طرح یہ دیکھا گیا: پانچ ہزار سال کے لئے عالمی سوشل نیٹ ورک شاید دو بڑے اجزاء پر مشتمل تھا - شمالی اور جنوبی امریکہ میں، اور یوروشیا میں دوسرا. اس وجہ سے، ٹیکنالوجی کو دو اجزاء میں آزادانہ طور پر تیار کیا گیا ہے، اور اس سے بھی بدترین انسانوں کی بیماریوں کو بھی تیار کیا جاتا ہے. جب دو اجزاء آخر میں رابطے میں آتے ہیں، تو ایک جلدی اور تباہی کے باعث بیماریوں کا دوسرا حصہ بھرا ہوا ہے.

امریکی ہائی سکول

زیادہ سے زیادہ اجزاء کا تصور نیٹ ورک کے بارے میں اور بہت چھوٹے سائز میں استدلال کے لئے مفید ہے. ایک دلچسپ مثال یہ ہے کہ 18 مہینے کے عرصے میں امریکی ہائی سکول میں رومانٹک تعلقات کا ایک گراف دکھایا گیا ہے. حقیقت یہ ہے کہ اس میں زیادہ سے زیادہ جزو شامل ہے جب یہ جنسی طور پر منتقل شدہ بیماریوں کے پھیلاؤ میں آتا ہے، جو مطالعہ کا مقصد تھا. اس عرصے کے دوران شاگردوں کے پاس صرف ایک پارٹنر ہوسکتا تھا، لیکن اس کے باوجود، اس کے بغیر اس کے بغیر، وہ زیادہ سے زیادہ اجزاء کا حصہ تھے اور اس وجہ سے کئی ممکنہ منتقلی کے راستوں کا حصہ تھا. یہ ڈھانچے ایسے تعلقات کی عکاسی کرتی ہیں جو ختم ہو چکے ہیں، لیکن وہ قریبی توجہ اور گپ شپ کے موضوع بننے کے لئے بہت لمبے عرصے سے زنجیروں میں افراد سے منسلک ہوتے ہیں. اس کے باوجود، وہ حقیقی ہیں: سماجی حقائق پوشیدہ ہیں، لیکن منطقی طور پر مکھنی برادریوں کی بہاؤ جو انفرادی ثالثی کی مصنوعات پیدا ہوتی ہے.

فاصلے اور چوڑائی کی تلاش

اس بارے میں معلومات کے علاوہ کہ دو نوڈس ایک راستے سے منسلک ہوتے ہیں، کمپیوٹر سائنس میں گراف کا نظریہ اس کی لمبائی - ٹرانسپورٹ، مواصلات یا خبروں اور بیماریوں کے بارے میں جاننے کے لۓ، اس کے ساتھ ساتھ یہ کئی چوٹیوں یا کثرت کے ذریعے گزرتا ہے.

ایسا کرنے کے لئے، راستے کی لمبائی کا تعین کرتے ہیں، اس سے شروع ہونے والے مرحلے سے متعلق مرحلے کے برابر، یہ ہے کہ، اس ترتیب میں کناروں کی تعداد جس سے اسے بناتا ہے. مثال کے طور پر، MIT، BBN، RAND، UCLA کا راستہ ہے 3 کی لمبائی، اور MIT، UTAH 1. راستے کی لمبائی کا استعمال کرتے ہوئے، یہ بات کر سکتا ہے کہ دو نوڈ ایک دوسرے کے قریب یا اس کے قریب گراف میں واقع ہیں: دو عمودی کے درمیان فاصلے لمبائی کے طور پر بیان کی جاتی ہے. ان کے درمیان سب سے چھوٹا راستہ. مثال کے طور پر، LINC اور SRI کے درمیان فاصلہ 3 ہے، اگرچہ اس بات کا یقین کرنے کے لئے، آپ کو اس بات کو یقینی بنانا چاہئے کہ ان کے درمیان 1 یا 2 کی لمبائی برابر ہو.

تلاش الگورتھم وسیع ہے

چھوٹے گرافکس کے لئے، دو نوڈس کے درمیان فاصلہ آسانی سے شمار کیا جا سکتا ہے. لیکن پیچیدہ افراد کے لئے، فاصلے کا تعین کرنے کے ایک منظم طریقہ کی ضرورت ہوتی ہے.

ایسا کرنے کا سب سے بڑا طریقہ اور اس وجہ سے، سب سے زیادہ مؤثر، مندرجہ ذیل ہے (دوستوں کے عالمی نیٹ ورک کے مثال):

• تمام دوستوں کو 1 کی فاصلے پر ہونے کا اعلان کیا جاتا ہے.
• دوستوں کے تمام دوستوں (جنہیں پہلے سے ہی نشان زد کیا گیا ہے) 2 کے فاصلے پر واقع ہونے کا اعلان نہیں کیا جاتا ہے.
• ان کے تمام دوست (دوبارہ، ٹیگ کردہ افراد کی گنتی نہیں کرتے) 3 کی فاصلے پر ریموٹ کا اعلان کیا جاتا ہے.

اس طرح جاری رکھنا، بعد میں تہوں میں تلاش کی جاتی ہے، جن میں سے ہر ایک ایک یونٹ پچھلے ایک سے باہر ہے. ہر نئی پرت نوڈس بن گئی ہے جو پہلے ہی پچھلے لوگوں میں حصہ نہیں لیتے ہیں، اور پچھلے پرت کے سب سے اوپر کے کنارے داخل ہوتے ہیں.

یہ تکنیک ایک چوڑائی کی تلاش کہا جاتا ہے، کیونکہ یہ ابتدائی نوڈوں کو سب سے پہلے ڈھونڈنے والے نوڈ سے گراف سے باہر نکلتا ہے. فاصلے کا تعین کرنے کے راستے فراہم کرنے کے علاوہ، یہ گراف کی ساخت کو منظم کرنے کے ساتھ ساتھ انفارمیشنکس میں گراف کی تعمیر کے لئے ایک مفید تصوراتی بنیاد کی حیثیت سے خدمت کرسکتا ہے، مقررہ نقطۂ نقطۂٔ نقطۂٔٔٔٔٔٔٔٔ سے اپنی دوری پر مبنی عمودی اجزاء رکھتا ہے.

چوڑائی میں تلاش نہ صرف دوستوں کے نیٹ ورک پر بلکہ کسی بھی گراف میں بھی لاگو کیا جاسکتا ہے.

دنیا چھوٹا ہے

اگر آپ دوستوں کے عالمی نیٹ ورک پر واپس جاتے ہیں تو، آپ دیکھ سکتے ہیں کہ زیادہ سے زیادہ جزو کی ملکیت کی وضاحت کرنے والے دلیل، حقیقت میں، کچھ اور کہتے ہیں: نہ صرف ریڈر اس کے دوستوں کو راستہ دیتا ہے جو انہیں دنیا کی آبادی کا بڑا حصہ بناتا ہے، لیکن یہ راستے حیران کن ہوتے ہیں. .

یہ خیال "قریبی دنیا کا رجحان" کہا جاتا ہے: دنیا چھوٹا لگتا ہے، اگر تم سوچتے ہو کہ کوئی مختصر راستہ کسی بھی شخص کو جوڑتا ہے.

"چھ ہینڈشکس" کے اصول نے سب سے پہلے 1960 ء میں اسٹینلے ملگرم اور اس کے ساتھیوں کی تحقیقات کی. سماجی نیٹ ورکنگ کے اعداد و شمار اور 680 ڈالر کے بجٹ کے کسی بھی سیٹ پر نہیں، اس نے مقبول خیال کا امتحان کرنے کا فیصلہ کیا. اس اختتام تک، انہوں نے 296 بے ترتیب منتخب کردہ ابتدائی نوکرینوں کو ایک اسٹاک بروکر کو خط بھیجنے کے لئے جو بوسٹن کے مضافات میں رہتے تھے. ابتداء کو اس مقصد کے بارے میں کچھ ذاتی معلومات دی گئی (بشمول ایڈریس اور پیشرفت) اور ان کو ایک ایسے شخص کو خط بھیجنا پڑا جسے وہ نام سے جانتا تھا، اسی ہدایات کے ساتھ جو اس نے ممکنہ حد تک ممکنہ حد تک پہنچ لیا. ہر خط نے کئی دوستوں کے ہاتھوں سے گزر لیا اور ایک سلسلہ بنائی جو بوسٹن کے باہر تبادلے کے بروکر پر بند تھا.

64 گولوں میں سے جو گول تک پہنچے تھے، اوسط لمبائی چھ تھی، جس کی تصدیق دو دہائیوں سے پہلے ہوئی جسے جان گیئر کے عنوان کے عنوان میں درج کیا گیا تھا.

اس تحقیق کے تمام پہلوؤں کے باوجود، تجربے نے سماجی نیٹ ورکوں کو سمجھنے کے سب سے اہم پہلوؤں میں سے ایک کا مظاہرہ کیا. بعد میں سالوں میں، انہوں نے ایک وسیع نتیجہ اخذ کیا: سماجی نیٹ ورک، ایک اصول کے طور پر، لوگوں کے مباحثہ جوڑوں کے درمیان بہت مختصر راستے ہیں. اور یہاں تک کہ اگر کاروباری رہنماؤں اور سیاسی رہنماؤں کے ساتھ ایسے غیر مستقیم رابطے روزانہ کی بنیاد پر ادا نہیں کرتے، تو ایسے مختصر راستوں کی موجودگی معاشرے میں معلومات، بیماریوں اور دیگر قسم کے انفیکشن کے ساتھ ساتھ، مواقع کے مواقع میں سماجی نیٹ ورک کے لوگوں کو فراہم کرتا ہے. مکمل طور پر مخالف خصوصیات.