Expected linear time MST algorithm
متوقع لکیری ٹائم ایم ایس ٹی الگورتھم ایک بے ترتیب الگورتھم ہے جو وزن والے گراف کے کم سے کم پھیلے ہوئے جنگل کی گنتی کے لیے ہے جس میں کوئی الگ تھلگ عمودی نہیں ہے۔ اسے ڈیوڈ کارگر، فلپ کلین اور رابرٹ ٹارجن نے تیار کیا تھا۔ الگورتھم لکیری وقت میں کم سے کم پھیلے ہوئے درخت کی تصدیق کے لیے ایک الگورتھم کے ساتھ بوروکا کے الگورتھم کی تکنیکوں پر انحصار کرتا ہے۔ یہ متوقع لکیری کارکردگی کو حاصل کرنے کے لیے تقسیم اور فتح الگورتھم، لالچی الگورتھم، اور بے ترتیب الگورتھم کے ڈیزائن کے نمونوں کو یکجا کرتا ہے۔ تعیناتی الگورتھم جو کم سے کم پھیلے ہوئے درخت کو تلاش کرتے ہیں ان میں پرائم کا الگورتھم، کرسکال کا الگورتھم، ریورس ڈیلیٹ الگورتھم، اور بوروکا کا الگورتھم شامل ہیں۔ جائزہ الگورتھم کی کلیدی بصیرت ایک بے ترتیب نمونے لینے کا مرحلہ ہے جو ہر ذیلی گراف میں شامل کرنے کے لیے تصادفی طور پر کناروں کا انتخاب کرکے گراف کو دو ذیلی گرافوں میں تقسیم کرتا ہے۔ الگورتھم بار بار پہلے ذیلی مسئلے کے کم سے کم پھیلے ہوئے جنگل کو تلاش کرتا ہے اور گراف میں کناروں کو ضائع کرنے کے لیے لکیری ٹائم تصدیق الگورتھم کے ساتھ مل کر حل کا استعمال کرتا ہے جو کم سے کم پھیلے ہوئے درخت میں نہیں ہو سکتے۔ بوروکا کے الگورتھم سے لیا گیا ایک طریقہ کار بھی ہر تکرار پر گراف کے سائز کو کم کرنے کے لیے استعمال کیا جاتا ہے۔ بوروکا مرحلہ الگورتھم کی ہر تکرار بوروکا کے الگورتھم کی موافقت پر منحصر ہے جسے بوروکا مرحلہ کہا جاتا ہے: ان پٹ: ایک گراف G جس میں کوئی الگ تھلگ عمودی نہیں ہے 1 ہر ورٹیکس v کے لیے، v 2 پر ہلکے کنارے کا واقعہ منتخب کریں 'ایک معاہدہ شدہ گراف G بنائیں' مرحلہ 1 میں منتخب کناروں سے جڑے G کے ہر جزو کو ایک واحد عمودی کے ساتھ تبدیل کریں 3 G آؤٹ پٹ سے تمام الگ تھلگ عمودی، سیلف لوپس، اور غیر کم از کم تکراری کناروں کو ہٹا دیں: مرحلہ 1 میں منتخب کناروں اور معاہدہ شدہ گراف G A بوروکا مرحلہ بوروکا کے الگورتھم کے اندرونی لوپ کے برابر ہے، جو O (m) وقت میں چلتا ہے جہاں m ہے۔ اس طرح، ایک بوروکا مرحلہ گراف میں عمودی حصوں کی تعداد کو کم از کم دو کے عنصر سے کم کرتا ہے اور کم از کم n/2 کناروں کو حذف کرتا ہے جہاں n G میں عمودی حصوں کی تعداد ہے۔ مثال کے طور پر بوروکا مرحلے F-بھاری اور F-ہلکے کناروں پر عمل درآمد ہر تکرار میں الگورتھم مخصوص خصوصیات والے کناروں کو ہٹا دیتا ہے جو انہیں کم سے کم پھیلے ہوئے درخت سے خارج کرتے ہیں۔ ان کو ایف بھاری کناروں کے نام سے جانا جاتا ہے اور ان کی تعریف مندرجہ ذیل ہے۔ گراف H پر F کو جنگل مان لیں۔ ایک F بھاری کنارہ ایک ایسا کنارہ ہے جو e کو جوڑتا ہے، جس کا وزن F میں U سے V تک کے راستے پر سب سے بھاری کنارہ کے وزن سے سختی سے زیادہ ہے۔ (اگر F میں کوئی راستہ موجود نہیں ہے تو اسے لامحدود وزن سمجھا جاتا ہے)۔ کوئی بھی کنارہ جو ایف ہیوی نہیں ہے وہ ایف لائٹ ہے۔ اگر F G کا ذیلی گراف ہے تو G میں کوئی بھی F بھاری کنارہ سائیکل پراپرٹی کے لحاظ سے G کے کم از کم پھیلے ہوئے درخت میں نہیں ہو سکتا۔ جنگل کو دیکھتے ہوئے، ایف بھاری کناروں کا حساب لکیری وقت میں کم از کم پھیلے ہوئے درخت کی تصدیق کے الگورتھم کا استعمال کرتے ہوئے کیا جا سکتا ہے۔ الگورتھم ان پٹ: ایک گراف G جس میں کوئی الگ تھلگ عمودی نہیں ہے اگر G خالی ہے تو ایک خالی جنگل واپس کریں G پر دو یکے بعد دیگرے بوروکا مراحل چلا کر ایک معاہدہ شدہ گراف G بنائیں امکان 1/2 کے ساتھ G "میں ہر کنارے کو منتخب کرکے ایک ذیلی گراف H بنائیں۔ اس کے کم سے کم پھیلے ہوئے جنگل ایف کو حاصل کرنے کے لیے بار بار الگورتھم کو ایچ پر لاگو کریں۔ لکیری ٹائم کم سے کم پھیلے ہوئے درخت کی تصدیق کے الگورتھم کا استعمال کرتے ہوئے جی سے تمام ایف بھاری کناروں کو ہٹا دیں (جہاں ایف مرحلہ 3 سے جنگل ہے)۔ اس کے کم سے کم پھیلے ہوئے جنگل کو حاصل کرنے کے لیے جی پر الگورتھم کو بار بار لاگو کریں۔ آؤٹ پٹ: G کا کم از کم پھیلا ہوا جنگل اور بوروکا کے مراحل سے تنگ کناروں کی درستگی گراف میں عمودی حصوں کی تعداد پر انڈکشن کے ذریعے ثابت ہوتی ہے۔ بنیادی معاملہ معمولی طور پر درست ہے۔ T * کو G کا کم از کم پھیلا ہوا درخت ہونے دیں۔ بوروکا مرحلے میں منتخب کردہ ہر کنارہ کٹ پراپرٹی کے ذریعے T * میں ہوتا ہے اور معاہدہ شدہ گراف بنانے کے لیے ہٹائے گئے کناروں میں سے کوئی بھی کٹ پراپرٹی (بے کار کناروں کے لیے) اور سائیکل پراپرٹی (سیلف لوپس کے لیے) کے ذریعے T * میں نہیں ہوتا ہے۔ ٹی * کے بقیہ کناروں کو مرحلہ 2 میں منتخب نہیں کیا گیا ہے جو کٹ پراپرٹی کے ذریعہ معاہدہ شدہ گراف کے کم سے کم پھیلے ہوئے درخت کی تشکیل کرتے ہیں (ہر کٹ کو سپرنوڈ ہونے دیں)۔ حذف شدہ ہر ایف بھاری کنارے سائیکل پراپرٹی کے ذریعہ کم سے کم پھیلے ہوئے درخت میں نہیں ہے۔ آخر میں ایف 'انڈکٹو مفروضے کے ذریعہ معاہدہ شدہ گراف کا کم سے کم پھیلا ہوا درخت ہے۔ اس طرح ایف 'اور بوروکا سیڑھیوں سے تنگ کناروں سے کم سے کم پھیلا ہوا درخت بنتا ہے۔ کارکردگی متوقع کارکردگی بے ترتیب نمونے لینے کے مرحلے کا نتیجہ ہے۔ بے ترتیب نمونے لینے کے مرحلے کی تاثیر کو درج ذیل لیما کے ذریعے بیان کیا گیا ہے جو G میں F-روشنی کے کناروں کی تعداد پر ایک باؤنڈ رکھتا ہے جس سے دوسرے ذیلی مسئلے کے سائز کو محدود کیا جاتا ہے۔ بے ترتیب نمونے لینے والا لیما لیما-فرض کریں کہ H G کا ذیلی گراف ہے جو G کے ہر کنارے کو آزادانہ طور پر امکان p کے ساتھ شامل کرکے تشکیل دیا گیا ہے اور فرض کریں کہ F H کا کم سے کم پھیلا ہوا جنگل ہے۔ G میں F-روشنی کے کناروں کی متوقع تعداد زیادہ سے زیادہ n/p ہے جہاں n G میں عمودی کناروں کی تعداد ہے۔ لیما کو ثابت کرنے کے لیے G کے کناروں کی جانچ کریں کیونکہ انہیں H میں شامل کیا جا رہا ہے۔ G میں F-روشنی کے کناروں کی تعداد اس ترتیب سے آزاد ہے جس میں H کے کناروں کا انتخاب کیا جاتا ہے کیونکہ تمام سلیکشن آرڈرز کے لیے H کا کم سے کم پھیلا ہوا جنگل ایک جیسا ہوتا ہے۔ ثبوت کی خاطر ہلکے سے بھاری تک کنارے کے وزن کی ترتیب میں ایک وقت میں جی ون کے کناروں کو لے کر ایچ کے لیے کناروں کو منتخب کرنے پر غور کریں۔ ای کو موجودہ کنارے پر غور کیا جا رہا ہے۔ اگر e کے اختتامی نکات H کے دو منقطع اجزاء میں ہیں تو e ان اجزاء کو جوڑنے والا سب سے ہلکا کنارہ ہے اور اگر اسے H میں شامل کیا جائے تو یہ کٹ پراپرٹی کے ذریعہ F میں ہوگا۔ اس کا مطلب یہ بھی ہے کہ ای ایف ہلکا ہے اس سے قطع نظر کہ اسے ایچ میں شامل کیا گیا ہے یا نہیں کیونکہ بعد میں صرف بھاری کناروں پر غور کیا جاتا ہے۔ اگر e کے دونوں اختتامی نکات H کے ایک ہی جزو میں ہیں تو سائیکل پراپرٹی کے لحاظ سے یہ (اور ہمیشہ ہوگا) F بھاری ہے۔ اس کے بعد ایج ای کو امکان پی کے ساتھ ایچ میں شامل کیا جاتا ہے۔ ایچ میں شامل ایف-لائٹ کناروں کی زیادہ سے زیادہ تعداد این-1 ہے کیونکہ ایچ کے کسی بھی کم سے کم پھیلے ہوئے درخت میں این-1 کناروں ہوتے ہیں۔ ایک بار جب این-1 ایف-لائٹ کناروں کو ایچ میں شامل کر دیا جاتا ہے تو سائیکل پراپرٹی کے مطابق اس کے بعد کے کناروں میں سے کوئی بھی ایف-لائٹ نہیں ہے۔ اس طرح، G میں F-روشنی کے کناروں کی تعداد H کے لیے سمجھے جانے والے F-روشنی کے کناروں کی تعداد سے محدود ہے اس سے پہلے کہ n-1 F-روشنی کے کناروں کو اصل میں H میں شامل کیا جائے۔ چونکہ کسی بھی F-روشنی کے کنارے کو امکان p کے ساتھ شامل کیا جاتا ہے، یہ اس سکے کو پلٹنے کے مترادف ہے جس میں p کے ساتھ آنے والے سروں کا امکان ہے جب تک کہ n-1 سر ظاہر نہ ہو جائیں۔ سکے پلٹانے کی کل تعداد G میں F-روشنی کے کناروں کی تعداد کے برابر ہے۔ سکے پلٹانے کی تعداد کی تقسیم پیرامیٹرز n-1 اور p کے ساتھ الٹا بائنومیل تقسیم کے ذریعے دی جاتی ہے۔ ان پیرامیٹرز کے لیے اس تقسیم کی متوقع قیمت (n-1)/p ہے۔ متوقع تجزیہ تکراری ذیلی مسائل میں کیے گئے کام کو نظر انداز کرنا الگورتھم کی ایک ہی دعوت میں کیے گئے کام کی کل مقدار ان پٹ گراف میں کناروں کی تعداد میں لکیری ہوتی ہے۔ مرحلہ 1 مستقل وقت لیتا ہے۔ بوروکا مراحل کو وقت کی لکیری میں کناروں کی تعداد میں انجام دیا جا سکتا ہے جیسا کہ بوروکا مرحلہ سیکشن میں ذکر کیا گیا ہے۔ مرحلہ 3 کناروں کے ذریعے دہراتا ہے اور ہر ایک کے لیے ایک سکے کو پلٹاتا ہے تاکہ یہ کناروں کی تعداد میں لکیری ہو۔ مرحلہ 4 کو لکیری ٹائم میں ایک ترمیم شدہ لکیری ٹائم کم از کم اسپیننگ ٹری ویریفکیشن الگورتھم کا استعمال کرتے ہوئے انجام دیا جا سکتا ہے۔ چونکہ الگورتھم کے ایک تکرار میں کیا گیا کام کناروں کی تعداد میں لکیری ہوتا ہے اس لیے الگورتھم کے ایک مکمل رن میں کیا گیا کام (بشمول تمام تکراری کالز) ایک مستقل عنصر گنا اصل مسئلے میں کناروں کی کل تعداد اور تمام تکراری ذیلی مسائل سے محدود ہوتا ہے۔ الگورتھم کی ہر دعوت زیادہ سے زیادہ دو ذیلی مسائل پیدا کرتی ہے لہذا ذیلی مسائل کا مجموعہ بائنری ٹری بناتا ہے۔ ہر بوروکا قدم عمودی حصوں کی تعداد کو کم از کم دو کے عنصر سے کم کرتا ہے لہذا دو بوروکا اقدامات کے بعد عمودی حصوں کی تعداد کو چار کے عنصر سے کم کر دیا گیا ہے۔ اس طرح، اگر اصل گراف میں n عمودی اور m کنارے ہیں تو درخت کی گہرائی d پر ہر ذیلی مسئلہ زیادہ سے زیادہ n/4d عمودی کے گراف پر ہوتا ہے۔ اس کے علاوہ درخت میں زیادہ تر لاگ 4 این کی سطح ہوتی ہے۔ ریکرشن ٹری کے بارے میں استدلال کرنے کے لیے مرحلہ 3 میں ریکرسو کال میں بائیں بچے کا مسئلہ ذیلی مسئلہ ہو اور مرحلہ 5 میں ریکرسو کال میں دائیں بچے کا مسئلہ ذیلی مسئلہ ہو۔ اصل مسئلہ میں کناروں کی کل تعداد اور تمام ذیلی مسائل کو درخت کے ہر بائیں راستے میں کناروں کی تعداد گن کر شمار کریں۔ بائیں راستہ یا تو دائیں بچے یا جڑ سے شروع ہوتا ہے اور اس میں وہ تمام نوڈس شامل ہوتے ہیں جو بائیں بچوں کے راستے سے پہنچ سکتے ہیں۔ بائنری ٹری کے بائیں راستے دائیں طرف کے خاکہ میں نیلے رنگ میں دائرے میں دکھائے گئے ہیں۔ بائیں بچے کے مسئلے میں ہر کنارے کو اس کے بنیادی مسئلے کے کناروں سے منتخب کیا جاتا ہے (بوروکا مراحل میں سکڑے ہوئے کناروں سے کم) امکان 1/2 کے ساتھ۔ اگر والدین کے مسئلے میں x کنارے ہیں تو بائیں بچے کے مسئلے میں کناروں کی متوقع تعداد زیادہ سے زیادہ x/2 ہے۔ اگر x کو بے ترتیب متغیر X سے تبدیل کیا جاتا ہے تو توقع کی لکیری سے بائیں بچے کے مسئلے Y میں کناروں کی متوقع تعداد اس کے ذریعہ دی جاتی ہے۔ اس طرح اگر بائیں راستے کے اوپری حصے میں کسی مسئلے میں کناروں کی متوقع تعداد k ہے تو بائیں راستے میں ہر ذیلی مسئلے میں کناروں کی متوقع تعداد کا مجموعہ زیادہ سے زیادہ ہے (جیومیٹرک سیریز دیکھیں)۔ جڑ کے کنارے m ہوتے ہیں لہذا کناروں کی متوقع تعداد 2m کے برابر ہوتی ہے اور ہر دائیں ذیلی مسئلے میں کناروں کی متوقع تعداد سے دوگنا ہوتی ہے۔ ہر دائیں ذیلی مسئلہ میں کناروں کی متوقع تعداد بنیادی مسئلہ میں ایف-لائٹ کناروں کی تعداد کے برابر ہے جہاں ایف بائیں ذیلی مسئلہ کا کم از کم پھیلا ہوا درخت ہے۔ ایف-لائٹ کناروں کی تعداد نمونے لینے والے لیما کے ذریعہ ذیلی مسئلے میں عمودی حصوں کی تعداد سے کم یا دوگنا کے برابر ہوتی ہے۔ گہرائی d پر ذیلی مسئلے میں عمودی کی تعداد n/4d ہے لہذا تمام صحیح ذیلی مسائل میں عمودی کی کل تعداد اس کے ذریعہ دی گئی ہے۔ اس طرح، اصل مسئلہ اور تمام ذیلی مسائل میں کناروں کی متوقع تعداد زیادہ سے زیادہ 2m + n ہے۔ چونکہ کسی الگ تھلگ عمودی کے بغیر گراف کے لیے زیادہ سے زیادہ 2 میٹر پر n، الگورتھم متوقع وقت O (m) میں چلتا ہے۔ بدترین کیس کا تجزیہ بدترین کیس رن ٹائم بوروکا کے الگورتھم کے رن ٹائم کے برابر ہے۔ یہ اس وقت ہوتا ہے جب تمام کناروں کو ہر دعوت پر بائیں یا دائیں ذیلی مسئلہ میں شامل کیا جاتا ہے۔ اس صورت میں الگورتھم بوروکا کے الگورتھم سے ملتا جلتا ہے جو n عمودی اور m کناروں والے گراف پر O (Min {n2, mlogn}) میں چلتا ہے۔ مزید پڑھنے کے حوالے لکیری ٹائم رینڈمائزڈ الگورتھم اسپیننگ ٹری میں کم از کم اسپیننگ ٹری کی تصدیق