Laplacian matrix
گراف تھیوری کے ریاضیاتی میدان میں، لیپلاسیئن میٹرکس، جسے گراف لیپلاسیئن، ایڈمیٹنس میٹرکس، کرچوف میٹرکس یا مجرد لیپلاسیئن بھی کہا جاتا ہے، گراف کی میٹرکس نمائندگی ہے۔ پیئر سائمن لیپلیس کے نام سے منسوب، گراف لیپلاسیئن میٹرکس کو ایک گراف پر منفی مجرد لیپلیس آپریٹر کی میٹرکس شکل کے طور پر دیکھا جا سکتا ہے جو کہ محدود فرق کے طریقہ کار سے حاصل کردہ منفی مسلسل لیپلاسیئن کا تخمینہ لگاتا ہے۔ لیپلاشین میٹرکس گراف کی بہت سی مفید خصوصیات سے متعلق ہے۔ کرچوف کے نظریہ کے ساتھ مل کر، اسے کسی دیئے گئے گراف کے لیے پھیلے ہوئے درختوں کی تعداد کا حساب لگانے کے لیے استعمال کیا جا سکتا ہے۔ گراف کی سب سے کم کٹ کا تخمینہ فیڈلر ویکٹر کے ذریعے لگایا جا سکتا ہے-گراف لیپلاسیئن کے دوسرے سب سے چھوٹے آئجن ویلیو سے مطابقت رکھنے والا آئجن ویکٹر-جیسا کہ چیگر کی عدم مساوات سے قائم ہوتا ہے۔ لیپلاسین میٹرکس کا سپیکٹرم سڑنا کم جہتی سرایتوں کی تعمیر کی اجازت دیتا ہے جو بہت سی مشین لرننگ ایپلی کیشنز میں ظاہر ہوتے ہیں اور گراف ڈرائنگ میں سپیکٹرم ترتیب کا تعین کرتے ہیں۔ گراف پر مبنی سگنل پروسیسنگ گراف فورئیر ٹرانسفارم پر مبنی ہے جو سگنل سے مطابقت رکھنے والے گراف کے لیپلاسیئن میٹرکس کے آئجین ویکٹرز کے لیے پیچیدہ سینوسائڈز کی معیاری بنیاد کو تبدیل کرکے روایتی مجرد فورئیر ٹرانسفارم کو بڑھاتا ہے۔ لیپلاشین میٹرکس ایک سادہ گراف کے لیے تعریف کرنا سب سے آسان ہے، لیکن ایج ویٹڈ گراف کے لیے ایپلی کیشنز میں زیادہ عام ہے، یعنی، اس کے کناروں پر وزن کے ساتھ-گراف ملحقہ میٹرکس کی اندراجات۔ سپیکٹرم گراف تھیوری گراف کی خصوصیات کو سپیکٹرم سے متعلق کرتی ہے، یعنی آئجین ویلیوز، اور گراف سے وابستہ میٹرکس کے آئجین ویکٹرز، جیسے کہ اس کے ملحقہ میٹرکس یا لیپلاسیئن میٹرکس۔ غیر متوازن وزن میٹرکس سپیکٹرم کو ناپسندیدہ طور پر متاثر کر سکتا ہے، جس کی وجہ سے نارملائزیشن کی ضرورت ہوتی ہے-میٹرکس اندراجات کا ایک کالم/قطار اسکیلنگ-جس کے نتیجے میں نارملائزڈ ملحقہ اور لیپلاسیئن میٹرکس ہوتے ہیں۔ سادہ گرافوں کے لیے تعریفیں لیپلاسیئن میٹرکس عمودی کے ساتھ ایک سادہ گراف کو دیکھتے ہوئے، اس کے لیپلاسیئن میٹرکس کو عنصر کے لحاظ سے یا اس کے مساوی میٹرکس کے ذریعے بیان کیا جاتا ہے جہاں D ڈگری میٹرکس ہے اور A گراف کا ملحقہ میٹرکس ہے۔ چونکہ یہ ایک سادہ گراف ہے، اس میں صرف 1s یا 0s ہوتے ہیں اور اس کے اخترن عناصر تمام 0s ہوتے ہیں۔ یہاں ایک لیبل شدہ، غیر ہدایت شدہ گراف اور اس کے لیپلاسیئن میٹرکس کی ایک سادہ مثال ہے۔ ہم غیر ہدایت شدہ گراف کے لیے مشاہدہ کرتے ہیں کہ ملحقہ میٹرکس اور لیپلاسیئن میٹرکس دونوں ہم آہنگ ہیں، اور لیپلاسیئن میٹرکس کی صف اور کالم کے مجموعے تمام صفر ہیں۔ ہدایت شدہ گرافوں کے لیے، یا تو انڈیگری یا آؤٹ ڈگری کا استعمال کیا جا سکتا ہے، درخواست کے لحاظ سے، جیسا کہ مندرجہ ذیل مثال میں ہے: ہدایت شدہ گراف میں، ملحقہ میٹرکس اور لیپلاسیئن میٹرکس دونوں غیر متناسب ہیں۔ اس کے لیپلاشین میٹرکس میں، کالم کے مجموعے یا صف کے مجموعے صفر ہوتے ہیں، یہ اس بات پر منحصر ہوتا ہے کہ آیا انڈیگری یا آؤٹ ڈگری کا استعمال کیا گیا ہے۔ واقعات میٹرکس کے ذریعے سمیٹرک لیپلاسیئن عمودی v اور کنارے e کے لیے عنصر Bve کے ساتھ واقعات میٹرکس B کی تعریف اس طرح کی جاتی ہے اگرچہ اس تعریف میں کناروں کو تکنیکی طور پر ہدایت دی گئی ہے، پھر بھی ان کی سمت من مانی ہو سکتی ہے، جس کے نتیجے میں ایک ہی سمیٹرک لیپلاسیئن میٹرکس L کی تعریف کی گئی ہے جہاں B کا میٹرکس ٹرانسپوز ہے۔ ایک متبادل پروڈکٹ نام نہاد کنارے پر مبنی لیپلاسیئن کی وضاحت کرتا ہے، جیسا کہ اصل عام طور پر استعمال ہونے والے ورٹیکس پر مبنی لیپلاسیئن میٹرکس ایل کے برخلاف ہے۔ ایک ہدایت شدہ گراف کے لیے سمیٹرک لیپلاسیئن میٹرکس تعریف کے لحاظ سے عام طور پر غیر سمیٹرک ہوتا ہے، جبکہ، مثال کے طور پر، روایتی سپیکٹرم کلسٹرنگ بنیادی طور پر سمیٹرک ملحقہ اور لیپلاسیئن میٹرکس کے ساتھ غیر ہدایت شدہ گراف کے لیے تیار کی جاتی ہے۔ سمیٹری کی ضرورت والی تکنیکوں کو لاگو کرنے کے لیے ایک معمولی نقطہ نظر یہ ہے کہ اصل ہدایت شدہ گراف کو غیر ہدایت شدہ گراف میں تبدیل کیا جائے اور مؤخر الذکر کے لیے لیپلاسیئن میٹرکس بنایا جائے۔ میٹرکس نوٹیشن میں، غیر ہدایت شدہ گراف کے ملحقہ میٹرکس کو، مثال کے طور پر، اصل ہدایت شدہ گراف اور اس کے میٹرکس ٹرانسپوز کے ملحقہ میٹرکس کے بولین مجموعہ کے طور پر بیان کیا جا سکتا ہے، جہاں صفر اور ایک اندراج کو عددی، اقدار کے بجائے منطقی سمجھا جاتا ہے، جیسا کہ مندرجہ ذیل مثال میں ہے: لیپلاسیئن میٹرکس نارملائزیشن ایک بڑی ڈگری والا ورٹیکس، جسے ہیوی نوڈ بھی کہا جاتا ہے، جس کے نتیجے میں لیپلاسیئن میٹرکس میں میٹرکس کی خصوصیات پر غلبہ حاصل ہوتا ہے۔ نارملائزیشن کا مقصد لیپلاسیئن میٹرکس کے اندراجات کو ورٹیکس ڈگریوں سے تقسیم کرکے اس طرح کے عمودی حصوں کے اثر کو دوسرے عمودی حصوں کے برابر بنانا ہے۔ صفر سے تقسیم سے بچنے کے لیے، صفر ڈگری والے الگ تھلگ عمودی حصوں کو معمول کے عمل سے خارج کر دیا جاتا ہے۔ سمیٹریکل طور پر نارملائزڈ لیپلاسیئن میٹرکس سمیٹریکل طور پر نارملائزڈ لیپلاسیئن میٹرکس کی تعریف اس طرح کی گئی ہے: جہاں مور-پینروز الٹا ہے۔ کے عناصر اس طرح کے ذریعے دیے جاتے ہیں۔ سمیٹریکل طور پر نارملائزڈ لیپلاسیئن میٹرکس سمیٹریک ہوتا ہے اگر اور صرف اس صورت میں جب ملحقہ میٹرکس سمیٹریک ہو۔ ڈائریکٹڈ گراف کے غیر ہم آہنگ ملحقہ میٹرکس کے لیے، انڈیگری اور آؤٹ ڈگری میں سے کسی ایک کو نارملائزیشن کے لیے استعمال کیا جا سکتا ہے: لیفٹ (رینڈم واک) اور رائٹ نارملائزڈ لیپلاسیئنز لیفٹ (رینڈم واک) نارملائزڈ لیپلاسیئن میٹرکس کی تعریف اس طرح کی گئی ہے: مور-پینروز انورس کہاں ہے۔ کے عناصر کی طرف سے دیا جاتا ہے اسی طرح، دائیں نارملائزڈ لیپلاسیئن میٹرکس کی تعریف اس طرح کی جاتی ہے۔ بائیں یا دائیں نارمل شدہ لیپلاسیئن میٹرکس ہم آہنگ نہیں ہے اگر ملحقہ میٹرکس ہم آہنگ ہے، سوائے تمام الگ تھلگ عمودی کے معمولی معاملے کے۔ مثال کے طور پر، مثال یہ بھی ظاہر کرتی ہے کہ اگر کوئی الگ تھلگ عمودی نہیں ہے، تو دائیں اسٹاکسٹک اور اس وجہ سے بے ترتیب چہل قدمی کا میٹرکس ہے، تاکہ بائیں نارمل شدہ لیپلاسیئن میں ہر صف کا مجموعہ صفر ہو۔ اس طرح ہم بعض اوقات متبادل طور پر بے ترتیب چہل قدمی کو نارملائزڈ لیپلاسیئن کہتے ہیں۔ کم غیر معمولی طور پر استعمال ہونے والے دائیں نارملائزڈ لیپلاسیئن میں ہر کالم کا مجموعہ صفر ہوتا ہے کیونکہ یہ بائیں اسٹاکسٹک ہوتا ہے۔ ڈائریکٹڈ گراف کے غیر ہم آہنگ ملحقہ میٹرکس کے لیے، کسی کو نارملائزیشن کے لیے انڈیگری یا آؤٹ ڈگری کا انتخاب کرنے کی بھی ضرورت ہوتی ہے: تمام 0 قطار کے مجموعوں کے ساتھ لیفٹ آؤٹ ڈگری نارملائزڈ لیپلاسیئن دائیں سٹوچسٹک سے متعلق ہے، جبکہ دائیں ڈگری میں نارملائزڈ لیپلاسیئن کالم کے مجموعوں کے ساتھ تمام 0 میں بائیں سٹوچسٹک ہوتا ہے۔ وزن والے کناروں والے گرافوں کی تعریفیں وزن والے کناروں والے ایپلی کیشنز گرافوں میں عام طور پر ان کے ملحقہ میٹرکس کے ذریعہ آسانی سے بیان کیے جاتے ہیں جہاں اندراجات کی اقدار عددی ہوتی ہیں اور اب صفر اور ایک تک محدود نہیں ہوتی ہیں۔ سپیکٹرم کلسٹرنگ اور گراف پر مبنی سگنل پروسیسنگ میں، جہاں گراف کے عمودی حصے ڈیٹا پوائنٹس کی نمائندگی کرتے ہیں، کنارے کے وزن کا حساب لگایا جا سکتا ہے، مثال کے طور پر، ڈیٹا پوائنٹس کے جوڑوں کے درمیان فاصلے کے الٹا متناسب کے طور پر، جس کی وجہ سے تمام وزن غیر منفی ہوتے ہیں۔ بڑی اقدار کے ساتھ غیر رسمی طور پر ڈیٹا پوائنٹس کے زیادہ ملتے جلتے جوڑوں سے مطابقت رکھتے ہیں۔ ڈیٹا پوائنٹس کے درمیان ارتباط اور مخالف ارتباط کا استعمال قدرتی طور پر مثبت اور منفی دونوں وزن کا باعث بنتا ہے۔ سادہ گراف کی زیادہ تر تعریفیں معمولی طور پر غیر منفی وزن کے معیاری معاملے تک بڑھا دی جاتی ہیں، جبکہ منفی وزن پر زیادہ توجہ کی ضرورت ہوتی ہے، خاص طور پر معمول پر لانے میں۔ لیپلاشین میٹرکس کی تعریف اس طرح کی جاتی ہے جہاں D ڈگری میٹرکس ہے اور A گراف کا ملحقہ میٹرکس ہے۔ ہدایت شدہ گرافوں کے لیے، یا تو انڈیگری یا آؤٹ ڈگری کا استعمال کیا جا سکتا ہے، درخواست کے لحاظ سے، جیسا کہ مندرجہ ذیل مثال میں ہے: گراف سیلف لوپس، جو ملحقہ میٹرکس کے مرکزی اخترن پر غیر صفر اندراجات کے ذریعے خود کو ظاہر کرتے ہیں، کی اجازت ہے لیکن گراف لیپلاسین اقدار کو متاثر نہیں کرتے ہیں۔ واقعات میٹرکس کے ذریعے سمیٹرک لیپلاسیئن وزن والے کناروں والے گرافوں کے لیے کوئی بھی وزن والے واقعات میٹرکس B کی وضاحت کر سکتا ہے اور اسے متعلقہ ہم آہنگی لیپلاسیئن کی تعمیر کے لیے استعمال کر سکتا ہے۔ ایک متبادل کلینر نقطہ نظر، جو یہاں بیان کیا گیا ہے، وزن کو کنیکٹوٹی سے الگ کرنا ہے: باقاعدہ گراف کے لیے انسیڈنس میٹرکس کا استعمال جاری رکھیں اور صرف وزن کی اقدار کو رکھنے والا میٹرکس متعارف کروائیں۔ اسپرنگ سسٹم اس ماڈل کی ایک مثال ہے جو میکانکس میں دی گئی سختی اور یونٹ کی لمبائی کے اسپرنگ کے نظام کو بیان کرنے کے لیے استعمال ہوتا ہے، جہاں سختی کی اقدار گراف کے کناروں کے وزن کا کردار ادا کرتی ہیں۔ اس طرح ہم ورٹیکس v کے لیے عنصر Bve کے ساتھ ویٹ لیس انسیڈینس میٹرکس B کی تعریف کو دوبارہ استعمال کرتے ہیں اور ایج e (ورٹیکس کو جوڑنے والا اور i> j کے ساتھ) کی وضاحت کرتے ہیں۔ اگرچہ B کی تعریف میں کناروں کو تکنیکی طور پر ہدایت دی گئی ہے، پھر بھی ان کی سمتیں من مانی ہو سکتی ہیں، جس کے نتیجے میں وہی سمیٹرک لیپلاسیئن میٹرکس L کی تعریف کی جاتی ہے جہاں B کا میٹرکس ٹرانسپوز ہے۔ تعمیر کو مندرجہ ذیل مثال میں واضح کیا گیا ہے، جہاں ہر کنارے کو وزن کی قیمت i تفویض کی گئی ہے، ہدایت شدہ گراف کے لیے سمیٹرک لیپلاسیئن کے ساتھ۔ سادہ گراف کی طرح، ہدایت شدہ وزن والے گراف کا لیپلاسیئن میٹرکس تعریف کے مطابق عام طور پر غیر سمیٹرک ہوتا ہے۔ سمیٹری کو لاپلیشین کی تعمیر سے پہلے اصل ہدایت شدہ گراف کو غیر ہدایت شدہ گراف میں تبدیل کر کے نافذ کیا جا سکتا ہے۔ غیر ہدایت شدہ گراف کے ملحقہ میٹرکس کو، مثال کے طور پر، اصل ہدایت شدہ گراف کے ملحقہ میٹرکس کے مجموعے کے طور پر بیان کیا جا سکتا ہے اور اس کے میٹرکس کو مندرجہ ذیل مثال کے طور پر منتقل کیا جا سکتا ہے: جہاں صفر اور ایک اندراج کو منطقی کے بجائے عددی سمجھا جاتا ہے، سادہ گرافوں کے طور پر، اقدار، نتائج میں فرق کی وضاحت کرتے ہوئے-سادہ گرافوں کے لیے، ہم آہنگ گراف کو اب بھی اس کے ہم آہنگ ملحقہ میٹرکس کے ساتھ سادہ ہونے کی ضرورت ہے جس میں صرف منطقی، عددی اقدار نہیں ہیں، مثال کے طور پر، منطقی مجموعہ 1 v1 = 1 ہے، جبکہ عددی مجموعہ 1 + 1 = 2 ہے۔ متبادل طور پر، سمیٹرک لیپلاسیئن میٹرکس کا حساب دو لیپلاسیئنز سے انڈیگری اور آؤٹ ڈگری کا استعمال کرتے ہوئے کیا جا سکتا ہے، جیسا کہ مندرجہ ذیل مثال میں ہے: آؤٹ ڈگری لیپلاسیئن ٹرانسپوزڈ اور ان ڈگری لیپلاسیئن کا مجموعہ سمیٹرک لیپلاسیئن میٹرکس کے برابر ہوتا ہے۔ لیپلاسیئن میٹرکس نارملائزیشن نارملائزیشن کا مقصد، سادہ گرافوں کی طرح، لیپلاسیئن میٹرکس کے ڈائیگنل اندراجات کو تمام یونٹ بنانا ہے، اور اسی کے مطابق آف ڈائیگنل اندراجات کو بھی اسکیل کرنا ہے۔ وزن والے گراف میں، ایک ورٹیکس میں منسلک کناروں کی ایک چھوٹی سی تعداد کی وجہ سے بڑی ڈگری ہو سکتی ہے لیکن بڑے وزن کے ساتھ ساتھ یونٹ وزن کے ساتھ منسلک کناروں کی ایک بڑی تعداد کی وجہ سے بھی۔ گراف سیلف لوپس، یعنی ملحقہ میٹرکس کے مرکزی اخترن پر غیر صفر اندراجات، گراف لیپلاسیئن اقدار کو متاثر نہیں کرتے، لیکن معمول کے عوامل کے حساب کے لیے شمار کرنے کی ضرورت پڑ سکتی ہے۔ سمیٹریکل نارملائزڈ لیپلاسیئن سمیٹریکل نارملائزڈ لیپلاسیئن کی تعریف اس طرح کی جاتی ہے جہاں L غیر معمولی لیپلاسیئن ہے، A ملحقہ میٹرکس ہے، D ڈگری میٹرکس ہے، اور مور-پینروز الٹا ہے۔ چونکہ ڈگری میٹرکس D اخترن ہے، اس لیے اس کا باہمی مربع جڑ صرف اخترن میٹرکس ہے جس کے اخترن اندراجات D کے اخترن اندراجات کے مربع جڑوں کے باہمی ہیں۔ اگر تمام کنارے کے وزن غیر منفی ہیں تو تمام ڈگری ویلیوز خود بخود بھی غیر منفی ہیں اور اس لیے ہر ڈگری ویلیو کا ایک منفرد مثبت مربع جڑ ہوتا ہے۔ صفر سے تقسیم سے بچنے کے لیے، صفر ڈگری والے عمودی حصوں کو معمول کے عمل سے خارج کر دیا جاتا ہے، جیسا کہ مندرجہ ذیل مثال میں ہے: متناسب طور پر معمول والا لیپلاسیئن ایک متناسب میٹرکس ہے اگر اور صرف اس صورت میں جب ملحقہ میٹرکس A متناسب ہو اور D کی اخترن اندراجات غیر منفی ہوں، اس صورت میں ہم متناسب معمول والے لیپلاسیئن کی اصطلاح استعمال کر سکتے ہیں۔ سمیٹرک نارملائزڈ لیپلاسیئن میٹرکس کو ویٹ لیس انسیڈنس میٹرکس B اور ڈائیگنل میٹرکس W کا استعمال کرتے ہوئے بھی لکھا جا سکتا ہے جس میں کنارے کے وزن ہوتے ہیں اور نئے ویٹڈ انسیڈنس میٹرکس کی وضاحت کی جاتی ہے جس کی قطاریں عمودی طور پر انڈیکس کی جاتی ہیں اور جن کے کالموں کو G کے کناروں سے اس طرح انڈیکس کیا جاتا ہے کہ ہر کالم کے کنارے e = {u, v} کے مطابق صف میں یو کے مطابق اندراج ہوتا ہے، قطار میں v کے مطابق اندراج ہوتا ہے، اور اس میں کہیں اور 0 اندراجات ہوتے ہیں۔ رینڈم واک نارملائزڈ لیپلاسیئن رینڈم واک نارملائزڈ لیپلاسیئن کی تعریف اس طرح کی جاتی ہے جہاں D ڈگری میٹرکس ہے۔ چونکہ ڈگری میٹرکس D اخترن ہے، اس لیے اس کے الٹا کو محض ایک اخترن میٹرکس کے طور پر بیان کیا جاتا ہے، جس میں اخترن اندراجات ہوتے ہیں جو D کے متعلقہ اخترن اندراجات کے باہمی ہوتے ہیں۔ الگ تھلگ عمودی حصوں (جن کی ڈگری 0 ہوتی ہے) کے لیے، ایک عام انتخاب یہ ہے کہ متعلقہ عنصر کو 0 پر سیٹ کیا جائے۔ رینڈم واک نارملائزڈ لیپلاسیئن کا نام اس حقیقت سے آتا ہے کہ یہ میٹرکس ہے، جہاں گراف پر صرف ایک رینڈم واکر کا ٹرانزیشن میٹرکس ہے، غیر منفی وزن فرض کرتے ہوئے۔ مثال کے طور پر آئیے i-th معیاری بیس ویکٹر کو ظاہر کرتے ہیں۔ پھر ایک امکانی ویکٹر ہے جو عمودی سے ایک قدم اٹھانے کے بعد بے ترتیب واکر کے مقامات کی تقسیم کی نمائندگی کرتا ہے۔ زیادہ عام طور پر، اگر ویکٹر گراف کے عمودی حصوں پر بے ترتیب واکر کے مقام کی امکانات کی تقسیم ہے، تو یہ قدموں کے بعد واکر کی امکانات کی تقسیم ہے۔ بے ترتیب واک نارملائزڈ لیپلاسیئن کو لیفٹ نارملائزڈ لیپلاسیئن بھی کہا جا سکتا ہے کیونکہ نارملائزیشن لیپلاسیئن کو بائیں طرف نارملائزیشن میٹرکس سے ضرب دے کر کی جاتی ہے۔ یہ فرض کرتے ہوئے کہ تمام وزن غیر منفی ہیں، اس میں ہر صف کا خلاصہ صفر ہوتا ہے کیونکہ یہ صحیح اسٹاکسٹک ہے۔ کم غیر معمولی طور پر استعمال ہونے والے دائیں نارملائزڈ لیپلاسیئن میں ہر کالم کا مجموعہ صفر ہوتا ہے کیونکہ یہ بائیں اسٹاکسٹک ہوتا ہے۔ ڈائریکٹڈ گراف کے غیر ہم آہنگ ملحقہ میٹرکس کے لیے، کسی کو نارملائزیشن کے لیے انڈیگری یا آؤٹ ڈگری کا انتخاب کرنے کی بھی ضرورت ہوتی ہے: تمام 0 قطار کے مجموعوں کے ساتھ لیفٹ آؤٹ ڈگری نارملائزڈ لیپلاسیئن دائیں سٹوچسٹک سے متعلق ہے، جبکہ دائیں ڈگری میں نارملائزڈ لیپلاسیئن کالم کے مجموعوں کے ساتھ تمام 0 میں بائیں سٹوچسٹک ہوتا ہے۔ منفی وزن منفی وزن معمول کے لیے کئی چیلنجز پیش کرتے ہیں: منفی وزن کی موجودگی قدرتی طور پر غیر الگ تھلگ عمودی کے لیے صفر صف اور/یا کالم کے مجموعے کا باعث بن سکتی ہے۔ ایک ورٹیکس جس میں مثبت وزن کی بڑی قطار کا مجموعہ اور منفی وزن کے یکساں منفی بڑے قطار کا مجموعہ، جو ایک ساتھ صفر تک ہوتا ہے، کو بھاری نوڈ سمجھا جا سکتا ہے اور دونوں بڑی اقدار کو اسکیل کیا جا سکتا ہے، جبکہ اخترن اندراج صفر رہتا ہے، جیسے کہ ایک الگ تھلگ ورٹیکس کے لیے۔ منفی وزن منفی صف اور/یا کالم کے مجموعے بھی دے سکتے ہیں، تاکہ غیر معمول شدہ لیپلاسیئن میٹرکس میں متعلقہ اخترن اندراج منفی ہو اور سمیٹرک نارملائزیشن کے لیے درکار مثبت مربع جڑ موجود نہ ہو۔ نارملائزیشن کے مقصد کے لیے صف اور/یا کالم کے مجموعوں کی مطلق قیمت لینے کے لیے دلائل دیے جا سکتے ہیں، اس طرح ممکنہ قدر-1 کو نارملائزڈ لیپلاسیئن میٹرکس کے مرکزی اخترن کے جائز یونٹ اندراج کے طور پر مانا جا سکتا ہے۔ ایک (غیر ہدایت شدہ) گراف G اور اس کے لیپلاسیئن میٹرکس L کے لیے آئجین ویلیوز کے ساتھ: L سمیٹرک ہے۔ L مثبت-سیمیڈفائنٹ ہے (یہ سب کے لیے ہے)۔ یہ اس حقیقت سے دیکھا جا سکتا ہے کہ لیپلاسیئن ہم آہنگ اور ترچھا غالب ہے۔ L ایک M-میٹرکس ہے (اس کی غیر اخترن اندراجات غیر مثبت ہیں، پھر بھی اس کی آئجن ویلیوز کے حقیقی حصے غیر منفی ہیں)۔ L کی ہر صف کا مجموعہ اور کالم کا مجموعہ صفر ہے۔ درحقیقت، مجموعہ میں، سرے کی ڈگری کا خلاصہ ہر پڑوسی کے لیے "-1" کے ساتھ کیا جاتا ہے۔ نتیجتا، کیونکہ ویکٹر مطمئن کرتا ہے اس سے یہ بھی ظاہر ہوتا ہے کہ لیپلاشین میٹرکس واحد ہے۔ گراف میں جڑے ہوئے اجزاء کی تعداد لیپلاسیئن کے نل اسپیس کی جہت اور 0 آئجین ویلیو کی الجبرائی ضرب ہے۔ ایل کی سب سے چھوٹی غیر صفر آئجین ویلیو کو سپیکٹرم گیپ کہا جاتا ہے۔ ایل (صفر ہو سکتا ہے) کا دوسرا سب سے چھوٹا آئجن ویلیو جی کا الجبرائی رابطہ (یا فیڈلر ویلیو) ہے اور گراف کے سب سے کم کٹ کا تخمینہ لگاتا ہے۔ لیپلاسیئن افعال کی n جہتی ویکٹر جگہ پر ایک آپریٹر ہے، جہاں G کا ورٹیکس سیٹ ہے، اور۔ جب G k-ریگولر ہوتا ہے، تو نارملائزڈ لیپلاسیئن ہوتا ہے:، جہاں A ملحقہ میٹرکس ہے اور I ایک شناختی میٹرکس ہے۔ متعدد منسلک اجزاء والے گراف کے لیے، ایل ایک بلاک ڈائیگنل میٹرکس ہے، جہاں ہر بلاک ہر جزو کے لیے متعلقہ لیپلاسیئن میٹرکس ہے، ممکنہ طور پر عمودی حصوں کو دوبارہ ترتیب دینے کے بعد (یعنی۔ ایل ایک بلاک ڈائیگنل میٹرکس کی طرح ترتیب ہے)۔ لیپلاشین میٹرکس L کا سراغ اس کے برابر ہے جہاں سمجھے جانے والے گراف کے کناروں کی تعداد ہے۔ اب یونٹ نارم آئجین ویوکٹرز اور متعلقہ آئجین ویلیوز کے ساتھ ایک آئجینڈی کمپوزیشن پر غور کریں: کیونکہ اسے ویکٹر کے اندرونی پروڈکٹ کے طور پر لکھا جا سکتا ہے، اس سے پتہ چلتا ہے کہ اور اس طرح کے تمام آئجین ویلیوز غیر منفی ہیں۔ نارملائزڈ سمیٹرک لیپلاسیئن کی تمام آئجین ویلیوز 0 = μ0 ≤. ≤ μn−1 ≤ 2 کو مطمئن کرتی ہیں۔ یہ آئجین ویلیوز (جسے نارملائزڈ لیپلاسیئن کے سپیکٹرم کے نام سے جانا جاتا ہے) عام گراف کے لیے دیگر گراف غیر متغیرات سے اچھی طرح سے متعلق ہیں۔ کوئی یہ چیک کر سکتا ہے کہ:، یعنی، نارملائزڈ لیپلاشین سے ملتا جلتا ہے۔ اس وجہ سے، یہاں تک کہ اگر عام طور پر ہم آہنگی نہیں ہے، تو اس میں حقیقی آئجین ویلیوز ہیں-بالکل وہی جو معمول کے ہم آہنگی لیپلاسیئن کی آئجین ویلیوز کے برابر ہیں۔ مسلسل لیپلاسیئن کا تخمینہ لگانے والے مجرد لیپلیس آپریٹر کے طور پر تشریح گراف لیپلاسیئن میٹرکس کو مزید ایک گراف پر منفی مجرد لیپلیس آپریٹر کی میٹرکس شکل کے طور پر دیکھا جا سکتا ہے جو محدود فرق کے طریقہ کار سے حاصل کردہ منفی مسلسل لیپلاسیئن آپریٹر کا تخمینہ لگاتا ہے۔ (ڈسکریٹ پوسن مساوات دیکھیں) اس تشریح میں، ہر گراف ورٹیکس کو گرڈ پوائنٹ کے طور پر سمجھا جاتا ہے۔ ورٹیکس کا مقامی رابطہ اس گرڈ پوائنٹ پر محدود فرق تخمینہ اسٹینسل کا تعین کرتا ہے، گرڈ کا سائز ہمیشہ ہر کنارے کے لیے ایک ہوتا ہے، اور کسی بھی گرڈ پوائنٹس پر کوئی رکاوٹیں نہیں ہوتیں، جو یکساں نیومن باؤنڈری کنڈیشن یعنی فری باؤنڈری کے معاملے سے مطابقت رکھتی ہیں۔ اس طرح کی تشریح کسی کو اجازت دیتی ہے، مثال کے طور پر، لیپلاسی میٹرکس کو گراف کے معاملے میں لامحدود تعداد میں عمودی اور کناروں کے ساتھ عام کرنا، جس سے لامحدود سائز کا لیپلاسی میٹرکس بنتا ہے۔ عام کردہ لیپلاسیئن کی تعریف اس طرح کی گئی ہے: نوٹ کریں کہ عام لیپلاسیئن ایک عام شدہ لیپلاسیئن ہے۔ ملحقہ میٹرکس کے مقناطیسی لیپلاسیئن اندراجات پیچیدہ قدر والے ہو سکتے ہیں، اس صورت میں میٹرکس سمیٹری کے تصور کو ہرمیٹین میٹرکس سے تبدیل کرنے کی ضرورت ہے۔ حقیقی وزن کے ساتھ ایک ہدایت شدہ گراف کے لیے مقناطیسی لیپلاسیئن کو سمیٹریزڈ لیپلاسیئن اور ہرمیٹین فیز میٹرکس کے حقیقی سمیٹرک میٹرکس کے ہڈمارڈ پروڈکٹ کے طور پر ان پیچیدہ اندراجات کے ساتھ بنایا جاتا ہے جو پیچیدہ سطح میں مرحلے میں کنارے کی سمت کو انکوڈ کرتے ہیں۔ کوانٹم فزکس کے تناظر میں، مقناطیسی لیپلاسیئن کی تشریح اس آپریٹر کے طور پر کی جا سکتی ہے جو گراف پر آزاد چارج شدہ ذرہ کے مظاہر کو بیان کرتا ہے، جو مقناطیسی میدان کے عمل سے مشروط ہے اور اس پیرامیٹر کو برقی چارج کہا جاتا ہے۔ مندرجہ ذیل مثال میں: ڈیفارمڈ لیپلاسیئن خراب لیپلاسیئن کو عام طور پر اس طرح بیان کیا جاتا ہے جہاں I شناختی میٹرکس ہے، A ملحقہ میٹرکس ہے، D ڈگری میٹرکس ہے، اور s ایک (پیچیدہ قدر والا) نمبر ہے۔ معیاری لیپلاسیئن منصفانہ ہے اور بے علامت لیپلاسیئن ہے۔ سگنل لیس لیپلاسیئن کی تعریف اس طرح کی گئی ہے کہ ڈگری میٹرکس کہاں ہے، اور یہ ملحقہ میٹرکس ہے۔ دستخط شدہ لیپلاسیئن کی طرح، بے علامت لیپلاسیئن بھی مثبت نیم یقینی ہے کیونکہ اس کی وجہ یہ ہو سکتی ہے کہ انسیڈینس میٹرکس کہاں ہے۔ ایک 0-آئجین ویکٹر ہے اگر اور صرف اس صورت میں جب اس میں الگ تھلگ عمودی حصوں کے علاوہ دو طرفہ منسلک جزو ہو۔ اسے اس طرح دکھایا جا سکتا ہے کہ اس کا ایک حل ہے جہاں اور صرف اس صورت میں جب گراف میں دو طرفہ منسلک جزو ہو۔ ڈائریکٹڈ ملٹیگرافس لیپلاسیئن میٹرکس کے ایک ینالاگ کی تعریف ڈائریکٹڈ ملٹیگرافس کے لیے کی جا سکتی ہے۔ اس صورت میں لیپلاشین میٹرکس L کی تعریف اس طرح کی گئی ہے جہاں D ایک اخترن میٹرکس ہے جس میں Di ہے، i ورٹیکس i کی آؤٹ ڈگری کے برابر ہے اور A ایک میٹرکس ہے جس میں AI ہے، j i سے j تک کناروں کی تعداد کے برابر ہے (بشمول لوپس)۔ اوپن سورس سافٹ ویئر کے نفاذ سائنس پائی نیٹ ورک ایکس جولیا ایپلی کیشن سافٹ ویئر اسککیٹ-لرن سپیکٹرل کلسٹرنگ پی جی ایس پی: ازگر میگا مین میں گراف سگنل پروسیسنگ: لاکھوں پوائنٹس کے لیے مینی فولڈ لرننگ ہموار جی لیپلاسیئن چینج پوائنٹ ڈیٹیکشن فار ڈائنامک گرافز (کے ڈی ڈی ڈی 2020) لیپلاسیئن آپٹ (لیپلاسیئن کے وزن والے گرافوں کی دوسری آئجین ویلیو کو زیادہ سے زیادہ کرنے کے لیے ایک جولیا پیکیج) لیگ ایم جی (بڑا بے قاعدہ گراف ملٹی گرڈ) Laplacians.jl یہ بھی دیکھیں کہ محدود وزن والے گرافوں پر سختی میٹرکس مزاحمت کی منتقلی کی شرح میٹرکس کیلکولس گراف فورئیر ٹرانسفارم حوالہ جات الجبرائی گراف تھیوری میٹرکس عددی تفریقی مساوات