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

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

تعريف

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

$L=D-A$

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

مثال

	Numbering	Degree Matrix	Adjacency Matrix	Laplace-Matrix
		$\left(\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\\ \end{array}\right)$	$\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\\ \end{array}\right)$	$\left(\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\\ \end{array}\right)$

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

انظر أيضا

• مصفوفة المجاورة