ما معنى Labeled Graph؟ شرح الرسم البياني المُعنون في الخوارزميات وهياكل البيانات
الرسم البياني المُعنون (Labeled Graph) هو ببساطة رسم بياني تُلصَق فيه «تسمية» أو «قيمة» بكل عقدة (Node) أو حافة (Edge) أو بكليهما، بدلاً من أن تكون العُقد والحواف مجرد نقاط وخطوط مجهولة. هذه التسمية قد تكون نصاً، أو رقماً، أو نوعاً، أو أي بيانات تميّز العنصر وتحمل معنى إضافياً يستفيد منه البرنامج أثناء المعالجة.
لكن قبل أن تمضي في القراءة، انتبه لمصيدة مهمة: مصطلح «Labeled Graph» له معنيان مختلفان تماماً حسب السياق، وكثير من الشروحات تخلط بينهما. سنفصلهما بوضوح، لأن معرفة أيّهما يقصده مصدرك تُغيّر الإجابة كلياً.
المعنى الأول: التسمية كبيانات مرفقة (سياق هياكل البيانات)
في عالم البرمجة وقواعد البيانات، يعني الرسم المُعنون أن كل عنصر يحمل «حمولة» من البيانات:
- تسمية على العقدة (Vertex label): مثل اسم شخص، معرّف مستخدم، أو تصنيف.
- تسمية على الحافة (Edge label): مثل نوع العلاقة بين عقدتين («صديق»، «يتبع»، «اشترى»).
مثال حيّ: في الرسم البياني المعرفي (Knowledge Graph) نمثّل الجملة «القاهرة عاصمةُ مصر» بعقدتين («القاهرة» و«مصر») وحافة معنونة بـ«عاصمة». هذا بالضبط هو أساس صيغ مثل RDF ونماذج قواعد البيانات الرسومية مثل Neo4j، التي تُسمّى «Property Graph» لأنها تسمح بتخزين خصائص متعددة على كل عقدة وحافة.
المعنى الثاني: التمييز في نظرية الرسوم البيانية
في الرياضيات ونظرية الرسوم، للمصطلح معنى أدقّ ومختلف: الرسم «المُعنون» هو رسم أُعطيت عُقده هويّات مميزة (مثل أرقام من 1 إلى n)، في مقابل الرسم «غير المُعنون» الذي نتعامل معه بشكله فقط دون تمييز عُقده.
الفرق ليس شكلياً؛ فهو جوهري عند العدّ. مثال كلاسيكي: عدد الأشجار المُعنونة التي يمكن تكوينها من n عقدة يساوي n^(n-2) بحسب صيغة كايلي (Cayley)، بينما عدد الأشجار غير المُعنونة (المختلفة شكلاً فقط) أصغر بكثير. إذا صادفت المصطلح في مسألة عدٍّ أو تماثل (Isomorphism)، فالمقصود غالباً هذا المعنى، لا التسميات كبيانات.
جدول للتفريق بين المفاهيم المتشابهة
| النوع | ما يحمله | مثال الاستخدام |
|---|---|---|
| رسم غير معنون (Unlabeled) | لا شيء؛ الشكل فقط | دراسة التماثل والبنية |
| رسم معنون بالبيانات (Labeled) | نص/نوع على العُقد أو الحواف | الرسوم المعرفية، الشبكات الاجتماعية |
| رسم موزون (Weighted) | رقم (وزن) على الحواف تحديداً | أقصر مسار، شبكات الطرق |
لاحظ أن الرسم الموزون هو في الحقيقة حالة خاصة من الرسم المُعنون، تكون فيها التسمية رقماً على الحافة. لذلك كل رسم موزون معنون، لكن ليس كل معنون موزوناً.
أين يُستخدم عملياً؟
- الشبكات الاجتماعية: كل شخص عقدة، وكل علاقة حافة معنونة بنوعها.
- أقصر المسارات: خوارزميات مثل Dijkstra وA* تعتمد على أوزان (تسميات رقمية) على الحواف.
- المُترجمات وتحليل البرامج: رسوم تدفّق التحكّم، حيث تُعنون الحواف بالشروط.
- مطابقة الأنماط: البحث عن رسم جزئي بمواصفات تسميات محددة (Subgraph Matching)، وهو أساس محرّكات الاستعلام في قواعد البيانات الرسومية.
كيف تُمثَّل في الكود؟
أبسط طريقة هي قائمة جوار (Adjacency List) تُخزّن مع كل حافة تسميتها. في بايثون مثلاً:
- اجعل كل عقدة مفتاحاً في قاموس (Dictionary).
- اجعل القيمة قائمةً من أزواج: (العقدة المجاورة، التسمية).
- لتسمية العُقد نفسها، استخدم قاموساً منفصلاً يربط كل عقدة بحمولتها.
بهذا الشكل: graph = {"القاهرة": [("مصر", "عاصمة")]}. وإن كانت التسميات أرقاماً (أوزاناً)، تصلح مصفوفة الجوار (Adjacency Matrix) حين يكون الرسم كثيف الحواف.
نصيحة عملية وخطأ شائع
الخطأ الأكثر شيوعاً هو الخلط بين «التسمية» و«الوزن». الوزن قيمة رقمية تخضع للجمع والمقارنة (تصلح لحساب المسافات)، أما التسمية فقد تكون نصاً أو نوعاً لا معنى لجمعه. إذا كتبت خوارزمية أقصر مسار على رسم تسمياته نصية دون تحويلها إلى أوزان رقمية، فلن تعمل. القاعدة العملية: حدّد أولاً هل تسمياتك «معلومات للتمييز» أم «قيم للحساب»، واختر الخوارزمية بناءً على ذلك.
الأسئلة الشائعة
هل الرسم المُعنون هو نفسه الرسم الموزون؟ لا تماماً. الموزون حالة خاصة تكون فيها التسمية رقماً على الحافة يُعبّر عن تكلفة أو مسافة. المُعنون أعمّ، إذ قد تكون التسمية نصاً أو نوعاً على العقدة أو الحافة.
هل يمكن تعنين العُقد والحواف معاً؟ نعم، وهو الشائع في قواعد البيانات الرسومية. تحمل العقدة تصنيفها (مثل «شخص») وتحمل الحافة نوع العلاقة (مثل «يعمل في»)، وقد يحمل كلاهما خصائص إضافية.
ما علاقة صيغة كايلي بالموضوع؟ تظهر حين نتحدث عن المعنى النظري: عدد الأشجار الممكنة من n عقدة معنونة (مميّزة) هو n^(n-2). إنها تذكّرك بأن «العنونة» في نظرية الرسوم تعني تمييز الهويّات، لا إرفاق بيانات.
أيّ المعنيين يقصده أستاذي في مادة الخوارزميات؟ غالباً المعنى الأول (التسمية كبيانات) إن كان الحديث عن تمثيل وتطبيقات، والمعنى الثاني إن كان الدرس عن العدّ والتماثل. راجع سياق المحاضرة لتحسم الأمر.