الدرس 2 من 2 · الرياضيات المتقطعة

الرسوم البيانية ومصفوفة الجوار Graphs and the Adjacency Matrix

الرسم البياني عقد وحواف؛ يُمثَّل بمصفوفة الجوار A، وقواها تعد المسيرات: العنصر \((A^k)_{ij}\) هو عدد المسيرات بطول k من i إلى j. والبحث بالعرض يجد أقصر المسارات، وPageRank هو التوزيع المستقر لمشي عشوائي على الروابط.

رياضيات التعلم الآلي الصعوبة: متوسط زمن الدراسة: 50 دقيقة
محتويات الدرس
  1. مقدمة
  2. لماذا ندرس هذا الموضوع؟
  3. الشرح النظري
  4. التعريفات الرياضية
  5. المعادلات
  6. مثال محلول
  7. التطبيق في الذكاء الاصطناعي
  8. المختبر التفاعلي
  9. تمارين تدريبية
  10. الملخص
  11. اختبار قصير
  12. دروس مرتبطة

1 مقدمة

الشبكات الاجتماعية، وروابط الويب، والجزيئات، وخرائط الطرق، ورسوم المعرفة: كلها رسوم بيانية (Graphs). وتمثيلها بمصفوفة يجعل الجبر الخطي أداة لتحليلها، وهذا ما تبني عليه شبكات الرسوم البيانية العصبية (GNNs).

الأهداف التعليمية

  • تمييز الرسوم الموجهة وغير الموجهة والدرجة
  • بناء مصفوفة الجوار وقراءة خصائصها
  • عد المسيرات بقوى مصفوفة الجوار
  • إيجاد أقصر مسار بالبحث بالعرض وفهم PageRank

2 لماذا ندرس هذا الموضوع؟

طبقة GNN تحسب تقريباً \(H' = \sigma(\hat A H W)\): كل عقدة تجمع تمثيلات جيرانها عبر مصفوفة الجوار. وPageRank الذي بُني عليه محرك بحث Google هو قيمة ذاتية لمصفوفة مشتقة من الروابط. وأقصر المسارات أساس التخطيط والملاحة.

3 الشرح النظري

التعريفات

الرسم البياني \(G = (V, E)\): مجموعة عقد V ومجموعة حواف E. في الرسم غير الموجه الحافة \(\{u, v\}\) تعمل في الاتجاهين، وفي الموجه \((u, v)\) من u إلى v. درجة العقدة عدد حوافها، ومجموع الدرجات يساوي ضعف عدد الحواف (مبرهنة المصافحة).

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

\(A_{ij} = 1\) إذا وُجدت حافة من i إلى j وإلا 0. للرسم غير الموجه A متماثلة. للمربع A–B–C–D–A مع القطر A–C:

\[A = \begin{bmatrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{bmatrix}\]

مجموع الصف i هو درجة العقدة i: \((3, 2, 3, 2)\).

قوى المصفوفة تعد المسيرات

العنصر \((A^2)_{ij} = \sum_k A_{ik}A_{kj}\) يعد العقد الوسيطة k المتصلة بـ i و j، أي عدد المسيرات بطول 2. وعموماً \((A^k)_{ij}\) عدد المسيرات بطول k. في المثال \((A^2)_{BD} = 2\) (عبر A وعبر C)، و\(\operatorname{tr}(A^3)/6 = 2\) هو عدد المثلثات.

البحث بالعرض BFS

يبدأ من عقدة المصدر ويزور جيرانها أولاً، ثم جيران الجيران، وهكذا طبقة بعد طبقة. لذلك أول مرة يصل فيها إلى عقدة تكون عبر أقصر مسار (بعدد الحواف) في رسم غير موزون.

PageRank

متصفح عشوائي يتبع رابطاً عشوائياً باحتمال d (التخميد، عادة 0.85) أو يقفز إلى صفحة عشوائية باحتمال \(1 - d\). رتبة الصفحة هي نسبة الوقت التي يقضيها فيها على المدى الطويل:

\[r = \frac{1-d}{n}\mathbf 1 + d\,M r\]

حيث \(M_{ji} = 1/\text{outdeg}(i)\) إذا ربطت i بـ j. للروابط A→B و A→C و B→C و C→A تكون الرتب تقريباً \((0.388, 0.215, 0.397)\)، و C الأعلى لأن رابطين يصلان إليها.

4 التعريفات الرياضية

الرسم البياني
زوج من مجموعة عقد ومجموعة حواف تصل بينها.
\[G=(V,E)\]
مصفوفة الجوار
مصفوفة n×n عنصرها 1 إذا وُجدت حافة بين العقدتين.
\[A_{ij}\in\{0,1\}\]
الدرجة
عدد الحواف المتصلة بالعقدة.
\[\deg(i)=\sum_j A_{ij}\]
PageRank
التوزيع المستقر لمتصفح عشوائي يتبع الروابط مع قفز عشوائي.
\[r=\frac{1-d}{n}\mathbf 1+dMr\]
مصفوفة الجوار (Adjacency Matrix)
تمثيل الرسم البياني بمصفوفة عنصرها 1 عند وجود حافة؛ قواها تعد المسيرات.
\[(A^k)_{ij}\]
الرسم البياني (Graph)
مجموعة عقد وحواف تمثل العلاقات بين الكيانات.
\[G=(V,E)\]
البحث بالعرض (Breadth-First Search)
استكشاف الرسم طبقة بعد طبقة من المصدر، فيجد أقصر المسارات بعدد الحواف.
ترتيب الصفحات (PageRank)
التوزيع المستقر لمتصفح عشوائي يتبع الروابط ويقفز عشوائياً باحتمال 1 − d.
\[r=\frac{1-d}{n}\mathbf 1+dMr\]

5 المعادلات

\[(A^k)_{ij} = \text{عدد المسيرات بطول } k \text{ من } i \text{ إلى } j\]
قوى مصفوفة الجوار
\[\sum_i \deg(i) = 2|E|\]
مبرهنة المصافحة
\[H^{(l+1)} = \sigma(\hat A H^{(l)} W^{(l)})\]
طبقة رسم بياني التفافية مبسطة

6 مثال محلول خطوة بخطوة

عد المسيرات

المسألة: في الرسم المربع مع القطر A–C، كم مسيرة بطول 2 من B إلى D؟

  1. \((A^2)_{BD} = \sum_k A_{Bk}A_{kD}\).
  2. B متصلة بـ A و C، وكلتاهما متصلة بـ D.

النتيجة: 2 مسيرتان: B–A–D و B–C–D

مبرهنة المصافحة

المسألة: رسم فيه 4 عقد درجاتها \((3, 2, 3, 2)\). كم حافة فيه؟

  1. مجموع الدرجات 10.
  2. كل حافة تُعد مرتين.

النتيجة: 5 حواف

PageRank

المسألة: احسب PageRank للروابط A→B و A→C و B→C و C→A مع d = 0.85.

  1. \(M\): A توزع رتبتها نصفين على B و C، و B تعطي C كلها، و C تعطي A كلها.
  2. كرر \(r \leftarrow 0.05 + 0.85\,M r\) حتى الاستقرار.

النتيجة: \(r \approx (0.388, 0.215, 0.397)\)

7 تطبيق عملي في الذكاء الاصطناعي

  • شبكات الرسوم البيانية العصبية: تجمع كل عقدة رسائل جيرانها عبر مصفوفة الجوار، وتُستخدم في الكيمياء الحاسوبية وأنظمة التوصية.
  • محركات البحث: PageRank يرتب الصفحات بحسب بنية الروابط، وهو قيمة ذاتية مرتبطة بالقيمة 1.
  • رسوم المعرفة: تمثيل الكيانات وعلاقاتها كرسم موجه موسوم يساعد النماذج اللغوية في الاسترجاع والاستدلال.

8 مختبر تفاعلي مرتبط بالدرس

حاسبة التباديل والتوافيق ومثلث باسكال، ورسم بياني يُكتب نصاً مع مصفوفة الجوار والبحث بالعرض BFS وعدد المسارات بقوى مصفوفة الجوار، وترتيب الصفحات PageRank بطريقة القوة.

افتح مختبر الرياضيات المتقطعة

9 تمارين تدريبية

أسئلة مراجعة للتفكير

  • لماذا تكون مصفوفة الجوار متماثلة في الرسم غير الموجه؟
  • كيف تفسر العنصر \((A^2)_{ii}\)؟
  • ما دور معامل التخميد في PageRank؟

أخطاء شائعة

  • افتراض أن مصفوفة الجوار متماثلة في الرسم الموجه.
  • الخلط بين المسيرة (يمكن تكرار العقد) والمسار (لا تتكرر).
  • استخدام BFS لأقصر مسار في رسم موزون بأوزان مختلفة.
  • نسيان معالجة العقد التي لا روابط خارجة لها في PageRank.

تدرب على 8 أسئلة من بنك الأسئلة لهذا الدرس

10 ملخص الدرس

  • مصفوفة الجوار تحول أسئلة الرسوم إلى جبر خطي.
  • \((A^k)_{ij}\) يعد المسيرات بطول k.
  • BFS يجد أقصر المسارات في الرسوم غير الموزونة.
  • PageRank توزيع مستقر لمشي عشوائي على الروابط.

11 اختبار قصير

5 أسئلة · 10 دقائق · النجاح من 60% — اجتيازه يُكمل الدرس.