كيفية تمثيل البيان في ذاكرة الحاسوب و استخداماته

كيفية تمثيل البيان في ذاكرة الحاسوب و استخداماته 

البيان ومفاهيم عامة

البيان: (Graph)

هو زوج مرتب (G(V,E يشمل مجموعة (...V (a,b,c

من الرؤوس و مجموعة  (...,{E({b,c} ,{a,d  من الأضلاع والتي هي بدورها مجموعة ثنائيات جزئية غير مرتبة من Vويعرف هذا النوع من البيانات بالبيان البسيط غير الموجه.

إذا كان الضلع مزوداً باتجاه (سهم) أصبح البيان موجهاً و أصبحت مجموعة الأضلاع {...(E{(a,b),(b,c 

مجموعة ثنائيات مرتبة من V 

تمثيل البيان في الذاكرة : هناك العديد من الاحتمالات لتمثيل البيان في الذاكرة 

(G=(V,E

Let the set of nodes be V={1,2,….,n} with edges E ⊆V ×V  and let  m:=|E|                                                                                          

 : توجد طريقتان لتمثيل الرسم البياني في ذاكرة الكمبيوتر  وهما 

•التمثيل المتسلسل : يمكن تمثيل الرسوم البيانية من خلال مصفوفة .

و أنواعه : تمثيل مصفوفة الجوار ، تمثيل حدوث مصفوفة ، تمثيل دائرة مصفوفة ، خفض التمثيل مجموعة ماتريكس ، مسار تمثيل مصفوفة .

•التمثيل المترابط : يمكن تمثيل الرسوم البيانية من خلال قائمة مرتبطة .

و أنواعه : تمثيل قائمة الجوار

 The Adjacency matrix of a graph G with n vertices is N × N .  It is given by A=[a] .

تمثيل حدوث مصفوفة :

تمثيل المصفوفة الدائرية :

خفض التمثيل مجموعة ماتريكس :

مسار تمثيل مجموعة :

قائمة تمثيل الجوار :

الجوار مصفوفة جيدة للرسومات البيانية الكثيفة

 •قوائم المتاخمة جيدة للرسوم البيانية المتناثرة و

 أيضاً لتغيير عدد العقد .

يتم تمثيل البيان في ذاكرة الحاسوب بعدة طرق و هي:

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

Adjacency matrix

قائمة الحافة

Edge List

قائمة المجاورة  Adjacency List: يمكن استخدام  هذا التمثيل لتمثيل رسم بياني مرجح , يمكن تمثيل أوزان الحواف كقوائم للأزواج 

القدرات الفريدة من ذاكرة الرسم البياني :

يوفر Memory Graph  مجموعة من القدرات الفريدة التي تميزه عن التقنيات الأخرى الموجودة في الذكاء الاصطناعي : تمثيل موحد ومتكامل لكل من الذاكرة العرضية والدلالية بناءً على البنية 'ثلاثية' التي تشكل رسمًا بيانيًا مدمجًا موجهًا . ذاكرة الرسم البياني يتكامل مع قواعد المعرفة الخارجية . تدعم Memory Graph الذاكرة قصيرة المدى مع مساحة صغيرة يمكن تشغيلها على أجهزة Android مناسبة لتطبيقات الأجهزة المحمولة وأجهزة إنترنت الأشياء . بالنسبة للذاكرة طويلة المدى ، فإن Memory Graph قابلة للتحجيم إلى كمية البيانات على المستوى البشري (بترتيب بيتابايت) بناءً على إطار البيانات الكبيرة Apache Spark / GraphX

استخدام نظرية البيان : 

•في الكمبيوتر، تُستخدم الرسوم البيانية لتمثيل شبكات الاتصال، وتنظيم البيانات، والأجهزة الحسابية، وتدفق الحساب، على سبيل المثال، يمكن تمثيل بنية رابط موقع الويب برسم بياني موجه، تمثل فيه القمم صفحات الويب والحواف الموجّهة تمثل روابط من صفحة إلى أخرى. يمكن اتباع نهج مماثل للمشاكل في وسائل الإعلام الاجتماعية، السفر، علم الأحياء، تصميم رقاقة الكمبيوتر، ورسم خريطة تطور الأمراض العصبية التنفسية، والعديد من المجالات الأخرى. ولذلك فإن تطوير الخوارزميات للتعامل مع الرسوم البيانية هو من الاهتمامات الرئيسية في علوم الكمبيوتر. غالبًا ما يتم رسم الطابع الرسمي لتحويل الرسوم البيانية ويتم تمثيلها بواسطة أنظمة العادة الرسم البياني. تعد أنظمة تحويل الرسومات البيانية التكميلية إلى نظم التحويل التي تركز على معالجة الرسوم البيانية في الذاكرة، هي قواعد البيانات الموجهة نحو المعاملات الآمنة والمخزنة المستمرة والاستعلام عن البيانات المنسقة الرسوم البيانية.

استخدامات البيان في علوم الحاسوب:

      خوارزمية ديكسترا: 

وهي احدى اشهر تطبيقات البيان في علوم الحاسوب تستخدمخوارزمية ديكسترا لتحديد أقصر مسار هي احدى أشهر الخوارزميات التي تستخدم لهذا الغرض ولها تطبيقات مهمة نستخدمها بشكل يوميالبيانات التي تنتقل عبر الإنترنت تمر بمسارات مختلفة حول العالم لذلك من المهم أن يتم توجيهها عبر مسارات قصيرة وأقل ازدحاما وهذا ممكن عن طريق خوارزمية ديكسترا فمثلا بروتوكول التوجيه OSPF اختصار لOpen Shortest Path First الذي يستخدم في بروتوكول الإنترنت (IP)  يعتمد على خوارزمية ديكسترا لتحديد  أقصر مسارأيضا باستخدام هذه الخوارزمية أصبح بإمكان خرائط جوجل أن تحدد لنا أقصر طريق يمكننا أن نسلكها لنذهب من نقطة محددة إلى مطعم أو مطار معين

   عند تطبيق الخوارزمية سنعلم ما هي أقصر مسافة بين نقطة المصدر ولتكن النقطة s وبين جميع النقاط الأخرى
وبعد القليل من التعديلات على الخوارزمية سيكون بالإمكان أن نعلم المحطات أو النقاط الفرعية التي سنمر بها عند اختيار أقصر مسار

تلوين الخرائط وشبكات الهاتف المحمول GSM:

•بالنظر إلى خريطة مرسومة على سطح أو سطح الكرة، تؤكد نظرية الألوان الأربعة الشهيرة أنه من الممكن دائمًا تلوين مناطق الخريطة بشكل صحيح بحيث لا يتم تخصيص منطقتين متجاورتين بنفس اللون، باستخدام أربعة أنواع مميزة على الأكثر ألوان لأي خريطة معينة، يمكننا بناء الرسم البياني المزدوج على النحو التالي. ضع قمة الرأس داخل كل منطقة من الخريطة وقم بتوصيل رأسيين مختلفين من خلال حافة إذا وفقط إذا كانت المناطق الخاصة بهما تشتركان في جزء كامل من حدودهما المشتركة. بعد ذلك، يؤدي التلوين المناسب للرأس البياني المزدوج إلى تلوين مناسب لمناطق الخريطة الأصلية.

أمن شبكات الحاسوب :

 قام فريق من علماء الكمبيوتر بقيادة إريك فيلول  في مختبر علم الفيروسات ومعهد التشفير ، و ESAT ، والبحرية الفرنسية، ESCANSIC ، باستخدام خوارزمية غطاء الرأس لمحاكاة نشر فيروسات التخفي على شبكات الكمبيوتر الكبيرة. تصميم استراتيجيات مثالية لحماية الشبكة ضد هجمات الفيروسات في الوقت الفعلي.

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

WEB GRAPH:

  يصف webgraph  الروابط الموجهة بين صفحات الشبكة العنكبوتية العالمية يتكون البيان، بشكل عام، من العديد من الرؤوس، وبعض الأزواج المتصلة بالحواف. في البيان الموجه يتم توجيه الحواف إلى خطوط أو أقواس. يمثل web graph رسمًا بيانيًا موجهًا، تتوافق رؤوسه مع صفحات WWW، وتقوم الحافة الموجهة بتوصيل الصفحة X بالصفحة Y إذا كان هناك ارتباط تشعبي في الصفحة X ، فيرجى الرجوع إلى الصفحة Y.

تطبيقاته:

يستخدم لحساب نظام رتبة الصفحات من صفحات الشبكة العنكبوتية.

يستخدم لحساب نظام تصنيف الصفحات الشخصي.

يستخدم للكشف عن صفحات الويب ذات المواضيع المتماثلة.

يتم تطبيق  webgraph في خوارزمية HITS لتحديد المحاور والسلطات في الويب.

تُستخدم الرسوم البيانية لتمثيل العديد من التطبيقات الواقعية: تُستخدم الرسوم البيانية لتمثيل الشبكات. قد تتضمن الشبكات مسارات في مدينة أو شبكة هاتفية أو شبكة دارة. تُستخدم الرسوم البيانية أيضًا في الشبكات الاجتماعية مثل linkedIn و Facebook. على سبيل المثال ، في Facebook ، يتم تمثيل كل شخص برأس (أو عقدة). كل عقدة هي بنية وتحتوي على معلومات مثل هوية الشخص والاسم والجنس والإعدادات المحلية.

و مما سبق تعرفنا في هذا البحث على المفاهيم الأساسية في نظرية البيان  و كيفية تمثيله في ذاكرة الحاسوب و تعرفنا على استخداماته