مصفوفة لابلاس

مصفوفة لابلاس في علم المخططات (بالإنجليزية:Laplacian Matrix) هي مصفوفة تعطي العلاقة بين الرؤوس (العُقَد) والأضلاع التي تربط بينها. تستخدم المصفوفة أيضا لحساب عدد تفرعات ما يعرف بشجرة الإمتداد وتعتبر تطبيقا رياضيا متقطعا لمعامل لابلاس.[1] يتم استخدام المتجهات الذاتية المٌرادفة للقيم الذاتية الصغرى لمصفوفة لابلاس في عمليات تصنيف البيانات (spectral clustering).

تعريف

عدل

مصفوفة لابلاس L تحتوي على الرؤوس V (nodes) وعدد من الأضلاع (edges) E وهي مصفوفة (L) ذات بعد |V| x |V| وتعطى بالعلاقة:

 

حيث D هي مصفوفة تعطي درجة الترابط (degree matrix) وA هي مصفوفة المُجَاورة (adjacency matrix) والتي تعطي القيمة 1 إذا كان هناك ارتباط بين نقطتين و 0 إن لم يكن.

مثال

عدل

Numbering Degree Matrix Adjacency Matrix
Laplace-Matrix

       

كما يبان في الجدول، تحتوي مصفوفة لابلاس في قطرها الرئيسي على درجة كل من الرؤوس وهو عدد الأضلاع المرتبطة بذلك الرأس وأما العناصر خارج القطر الرئيسي فهي لا تساوي صفر وسالبة في حالة كان هناك ضلع يربط الرؤوس وصفر فيما لا. فمثلا العنصر (2،2) في المصفوفة قيمته 3 وهي درجة الرأس 2 حيث أنه مرتبط عبر 3 أضلاع مع الرؤوس المجاورة له وهي 1، 5، 3.

انظر أيضا

عدل

المصادر

عدل
  1. ^ Y. Weiss, “Segmentation using eigenvectors: a unifying view,” in Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, vol. 2, pp. 975–982 vol.2, 1999.