رسم بياني

يُعد رسم المخططات مجالًا من مجالات الرياضيات وعلوم الحاسوب يجمع بين أساليب نظرية المخططات الهندسية وتصور المعلومات لاستخلاص تمثيلات ثنائية الأبعاد (أو ثلاثية الأبعاد في بعض الأحيان) للمخططات الناشئة عن تطبيقات مثل تحليل الشبكات الاجتماعية ، ورسم الخرائط ، واللغويات ، والمعلوماتية الحيوية . ^{[ 1 ]}

رسم المخطط البياني أو مخطط الشبكة هو تمثيل تصويري لرؤوس وحواف المخطط . يجب عدم الخلط بين هذا الرسم والمخطط نفسه، إذ قد تتوافق تخطيطات مختلفة تمامًا مع المخطط نفسه. [ ^{2 ] من} الناحية النظرية، كل ما يهم هو أزواج الرؤوس المتصلة بالحواف. أما من الناحية العملية، فإن ترتيب هذه الرؤوس والحواف داخل الرسم يؤثر على سهولة فهمه واستخدامه وتكلفة إنتاجه وجمالياته . [ ^{3 ] وتتفاقم} المشكلة إذا تغير المخطط بمرور الوقت بإضافة حواف أو حذفها (رسم المخطط الديناميكي)، وكان الهدف هو الحفاظ على الخريطة الذهنية للمستخدم. ^{[ 4 ]}

تُرسَم الرسوم البيانية غالبًا على شكل مخططات العقد والروابط، حيث تُمثَّل الرؤوس بأقراص أو مربعات أو تسميات نصية، بينما تُمثَّل الحواف بقطع مستقيمة أو خطوط متعددة أو منحنيات في المستوى الإقليدي . ^{[ 3 ]} يمكن تتبع أصول مخططات العقد والروابط إلى أعمال بسودو-لول التي نُشرت في القرنين الرابع عشر والسادس عشر تحت اسم رامون لول ، وهو عالم موسوعي من القرن الثالث عشر. رسم بسودو-لول مخططات من هذا النوع للرسوم البيانية الكاملة بهدف تحليل جميع التوليفات الثنائية بين مجموعات المفاهيم الميتافيزيقية. ^{[ 5 ]}

في حالة الرسوم البيانية الموجهة ، تُعد رؤوس الأسهم اصطلاحًا رسوميًا شائع الاستخدام لإظهار اتجاهها ؛ ^{[ 2 ]} ومع ذلك، أظهرت دراسات المستخدمين أن اصطلاحات أخرى، مثل التناقص التدريجي، توفر هذه المعلومات بشكل أكثر فعالية. ^{[ 6 ]} يستخدم الرسم المستوي الصاعد اصطلاح توجيه كل حافة من رأس أدنى إلى رأس أعلى، مما يجعل رؤوس الأسهم غير ضرورية. ^{[ 7 ]}

تشمل الاصطلاحات البديلة لمخططات العقد والروابط تمثيلات التجاور مثل تعبئة الدوائر ، حيث يتم تمثيل الرؤوس بمناطق منفصلة في المستوى ويتم تمثيل الحواف بالتجاور بين المناطق؛ تمثيلات التقاطع حيث يتم تمثيل الرؤوس بأشكال هندسية غير منفصلة ويتم تمثيل الحواف بتقاطعاتها؛ تمثيلات الرؤية حيث يتم تمثيل الرؤوس بمناطق في المستوى ويتم تمثيل الحواف بمناطق لها خط رؤية غير معاق لبعضها البعض؛ الرسومات المتقاربة، حيث يتم تمثيل الحواف كمنحنيات ناعمة داخل مسارات قطار رياضية ؛ الأقمشة، حيث يتم تمثيل العقد كخطوط أفقية والحواف كخطوط رأسية؛ ^{[ 8 ]} وتصورات مصفوفة التجاور للرسم البياني.

تم تحديد العديد من معايير الجودة المختلفة للرسوم البيانية، في محاولة لإيجاد وسائل موضوعية لتقييم جمالياتها وسهولة استخدامها. ^{[ 9 ]} بالإضافة إلى توجيه الاختيار بين طرق التخطيط المختلفة لنفس الرسم البياني، تحاول بعض طرق التخطيط تحسين هذه المعايير بشكل مباشر.

• عدد التقاطعات في الرسم هو عدد أزواج الحواف التي تتقاطع. إذا كان الرسم البياني مستويًا ، فمن الملائم غالبًا رسمه دون أي تقاطعات للحواف؛ أي أن رسم الرسم البياني في هذه الحالة يمثل تضمينًا للرسم البياني . مع ذلك، تظهر الرسوم البيانية غير المستوية بشكل متكرر في التطبيقات، لذا يجب أن تسمح خوارزميات رسم الرسوم البيانية عمومًا بتقاطعات الحواف. ^{[ 10 ]}
• مساحة الرسم هي حجم أصغر مربع محيط به ، نسبةً إلى أقرب مسافة بين أي رأسين. تُفضّل الرسومات ذات المساحة الأصغر عمومًا على تلك ذات المساحة الأكبر، لأنها تسمح بعرض تفاصيل الرسم بحجم أكبر وبالتالي بشكل أوضح. وقد تكون نسبة أبعاد المربع المحيط مهمة أيضًا.
• تُعنى مشكلة عرض التناظر بإيجاد مجموعات التناظر داخل رسم بياني مُعطى، وإيجاد رسم يُظهر أكبر قدر ممكن من التناظر. تُؤدي بعض طرق التخطيط تلقائيًا إلى رسومات متناظرة؛ في المقابل، تبدأ بعض طرق الرسم بإيجاد التناظرات في الرسم البياني المُدخل واستخدامها لإنشاء الرسم. ^{[ 11 ]}
• من المهم أن تكون أشكال الحواف بسيطة قدر الإمكان، لتسهيل تتبعها بصريًا. في الرسومات متعددة الخطوط، يُقاس تعقيد الحافة بعدد انحناءاتها ، وتهدف العديد من الطرق إلى توفير رسومات ذات عدد قليل من الانحناءات إجمالًا أو عدد قليل من الانحناءات لكل حافة. ​​وبالمثل، في منحنيات سبلاين، يُقاس تعقيد الحافة بعدد نقاط التحكم عليها.
• تتعلق العديد من معايير الجودة الشائعة بأطوال الحواف: فمن المستحسن عمومًا تقليل الطول الإجمالي للحواف، وكذلك الحد الأقصى لطول أي حافة. ​​بالإضافة إلى ذلك، قد يكون من الأفضل أن تكون أطوال الحواف موحدة بدلًا من أن تكون متفاوتة بشكل كبير.
• الدقة الزاوية هي مقياس لأدق الزوايا في الرسم البياني. إذا كان للرسم البياني رؤوس ذات درجة عالية ، فستكون دقته الزاوية صغيرة بالضرورة، ولكن يمكن تحديد الحد الأدنى للدقة الزاوية بدالة للدرجة. ^{[ 12 ]}
• عدد ميول الرسم البياني هو الحد الأدنى لعدد ميول الحواف المختلفة اللازمة في رسم ذي حواف مستقيمة (مع السماح بالتقاطعات). يبلغ عدد ميول الرسوم البيانية المكعبة أربعة على الأكثر، بينما قد يكون عدد ميول الرسوم البيانية من الدرجة الخامسة غير محدود؛ ولا يزال من غير المعروف ما إذا كان عدد ميول الرسوم البيانية من الدرجة الرابعة محدودًا. ^{[ 12 ]}

توجد العديد من استراتيجيات تخطيط الرسوم البيانية المختلفة:

• في أنظمة التخطيط القائمة على القوى ، يقوم برنامج رسم المخططات بتعديل موضع الرؤوس الأولي عن طريق تحريكها باستمرار وفقًا لنظام قوى مستوحى من مفاهيم فيزيائية متعلقة بأنظمة النوابض أو الميكانيكا الجزيئية . عادةً، تجمع هذه الأنظمة بين قوى التجاذب بين الرؤوس المتجاورة وقوى التنافر بين جميع أزواج الرؤوس، وذلك للبحث عن تخطيط تكون فيه أطوال الحواف قصيرة مع وجود مسافات كافية بين الرؤوس. قد تُجري هذه الأنظمة عملية تقليل لدالة الطاقة باستخدام خوارزمية التدرج الهبوطي ، أو قد تُترجم القوى مباشرةً إلى سرعات أو تسارعات للرؤوس المتحركة. ^{[ 14 ]}
• تستخدم طرق التخطيط الطيفي كمتجهات ذاتية لمصفوفة مثل لابلاس المشتقة من مصفوفة التجاور للرسم البياني. ^{[ 15 ]}
• تُتيح طرق التخطيط المتعامد امتداد حواف الرسم البياني أفقيًا أو رأسيًا، بالتوازي مع محاور إحداثيات التخطيط. صُممت هذه الطرق في الأصل لمشاكل تخطيط الدوائر المتكاملة واسعة النطاق (VLSI) ولوحات الدوائر المطبوعة (PCB) ، ولكن جرى تكييفها أيضًا لرسم المخططات. تتضمن هذه الطرق عادةً نهجًا متعدد المراحل، حيث يتم فيه تسطيح الرسم البياني المُدخل باستبدال نقاط التقاطع بالرؤوس، ثم إيجاد تمثيل طوبولوجي للرسم البياني المُسطّح، واختيار اتجاهات الحواف لتقليل الانحناءات، ووضع الرؤوس بما يتوافق مع هذه الاتجاهات، وأخيرًا، تعمل مرحلة ضغط التخطيط على تقليل مساحة الرسم. ^{[ 16 ]}
• تُظهر خوارزميات تخطيط الشجرة هذه تكوينًا يشبه الشجرة الجذرية ، وهو مناسب للأشجار . غالبًا، في تقنية تُسمى "تخطيط البالون"، يتم رسم أبناء كل عقدة في الشجرة على دائرة تحيط بالعقدة، مع تناقص أنصاف أقطار هذه الدوائر في المستويات الأدنى من الشجرة بحيث لا تتداخل هذه الدوائر. ^{[ 17 ]}
• تُعدّ طرق رسم المخططات الطبقية (والتي تُعرف غالبًا باسم رسم سوجياما) الأنسب للمخططات الموجهة غير الدورية أو المخططات شبه الدورية، مثل مخططات التبعيات بين الوحدات أو الوظائف في نظام برمجي. في هذه الطرق، تُرتّب عُقد المخطط في طبقات أفقية باستخدام طرق مثل خوارزمية كوفمان-غراهام ، بحيث تتجه معظم الحواف إلى الأسفل من طبقة إلى أخرى؛ بعد هذه الخطوة، تُرتّب العُقد داخل كل طبقة لتقليل التقاطعات. ^{[ 18 ]}

• مخططات القوس ، وهو أسلوب تخطيط يعود تاريخه إلى الستينيات، ^{[ 19 ]} يضع الرؤوس على خط؛ يمكن رسم الحواف على شكل أنصاف دوائر أعلى أو أسفل الخط، أو كمنحنيات سلسة متصلة ببعضها البعض من أنصاف دوائر متعددة.
• تعتمد طرق التخطيط الدائري على وضع رؤوس الرسم البياني على دائرة، مع اختيار ترتيب الرؤوس حول الدائرة بعناية لتقليل التقاطعات ووضع الرؤوس المتجاورة بالقرب من بعضها البعض. يمكن رسم الحواف إما كأوتار للدائرة أو كأقواس داخل الدائرة أو خارجها. في بعض الحالات، يمكن استخدام دوائر متعددة. ^{[ 20 ]}
• يُرتب الرسم المهيمن الرؤوس بحيث يكون أحد الرؤوس أعلى أو يمين أو كليهما بالنسبة لرأس آخر إذا وفقط إذا كان بالإمكان الوصول إليه من الرأس الآخر. وبهذه الطريقة، يجعل أسلوب التخطيط علاقة الوصول في الرسم البياني واضحة بصريًا. ^{[ 21 ]}

تشمل الرسوم البيانية والرسومات البيانية التي تظهر في مجالات تطبيق أخرى ما يلي:

• المخططات الاجتماعية ، وهي رسومات للشبكة الاجتماعية ، كما هو الحال غالبًا مع برامج تحليل الشبكات الاجتماعية ^{[ 22 ].}
• مخططات هاس ، وهي نوع من أنواع الرسم البياني المتخصص في الترتيبات الجزئية ^{[ 23 ]}
• Dessin d'enfants ، وهو نوع من أنواع الرسم البياني المستخدم في الهندسة الجبرية ^{[ 24 ]}
• مخططات الحالة ، وهي تمثيلات بيانية لآلات الحالة المحدودة ^{[ 25 ]}
• مخططات شبكة الحاسوب ، وهي عبارة عن تصوير للعقد والوصلات في شبكة الحاسوب ^{[ 26 ]}
• المخططات الانسيابية ومخططات دراكون ، وهي رسومات تمثل فيها العقد خطوات الخوارزمية وتمثل الحواف تدفق التحكم بين الخطوات.
• شبكة المشروع ، وهي تمثيل بياني للترتيب الزمني الذي يجب أن تكتمل به أنشطة المشروع .
• مخططات تدفق البيانات ، وهي رسومات تمثل فيها العقد مكونات نظام المعلومات وتمثل الحواف حركة المعلومات من مكون إلى آخر.
• المعلوماتية الحيوية بما في ذلك الأشجار التطورية ، وشبكات تفاعل البروتين-البروتين ، والمسارات الأيضية . ^{[ 27 ]}

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

توجد العديد من الخوارزميات لرسم الرسوم البيانية. من بينها:

• خوارزمية رينغولد-تيلفورد لرسم الأشجار. ^{[ 28 ]}
• خوارزمية كانط، ^{[ 29 ]} التي ترسم مخططًا متعدد الخطوط لرسم بياني مستوٍ ثلاثي الاتصال بحيث يكون حجم أصغر زاوية بين الأقواس على الأقل${\displaystyle {\frac {1}{d}}\pi }$، حيث d هي درجة العقدة القصوى؛ وتعميمها، الذي يعمل بشكل جيد أيضًا للرسوم البيانية المستوية الأخرى، بواسطة جوتفينجر وموتزل. ^{[ 30 ]}
• خوارزمية تاماسيا لتقليل عدد الانحناءات في التمثيل المتعامد للرسم البياني المستوي. ^{[ 31 ]}
• نموذج الزنبرك المغناطيسي لسوجياما وميسوي. ^{[ 32 ]}

تشمل البرامج والأنظمة وموردي أنظمة رسم الرسوم البيانية ما يلي:

• برنامج BioFabric مفتوح المصدر لتصور الشبكات الكبيرة عن طريق رسم العقد كخطوط أفقية.
• برنامج Cytoscape ، وهو برنامج مفتوح المصدر لتصوير شبكات التفاعل الجزيئي
• جيفي ، برنامج مفتوح المصدر لتحليل الشبكات وتصورها
• graph-tool ، مكتبة بايثون مجانية/مفتوحة المصدر لتحليل الرسوم البيانية
• Graphviz ، وهو نظام رسم بياني مفتوح المصدر من شركة AT&T ^{[ 33 ]}
• Linkurious ، برنامج تجاري لتحليل الشبكات وتصور قواعد بيانات الرسوم البيانية
• Mathematica ، أداة حسابية للأغراض العامة تتضمن أدوات لتصور الرسوم البيانية ثنائية وثلاثية الأبعاد وأدوات تحليل الرسوم البيانية. ^{[ 34 ]}
• Microsoft Automatic Graph Layout ، مكتبة .NET مفتوحة المصدر (تسمى سابقًا GLEE) لتخطيط الرسوم البيانية ^{[ 35 ]}
• NetworkX هي مكتبة بايثون لدراسة الرسوم البيانية والشبكات.
• توليب ، ^{[ 36 ]} أداة مفتوحة المصدر لتصور البيانات
• yEd ، محرر رسوم بيانية مزود بوظائف تخطيط الرسوم البيانية ^{[ 37 ]}
• PGF/TikZ 3.0 مع graphdrawingالحزمة (يتطلب LuaTeX ). ^{[ 38 ]}
• LaNet-vi ، برنامج مفتوح المصدر لتصور الشبكات الكبيرة
• OGDF، مكتبة مفتوحة المصدر لهياكل البيانات والخوارزميات C++، في الغالب لرسم الرسوم البيانية ^{[ 39 ]}

• ندوة دولية حول رسم المخططات
• قائمة أدوات لغة النمذجة الموحدة

• مكتبة GraphX ​​لـ .NET (مؤرشفة بتاريخ 26 يناير 2018 على Wayback Machine) : مكتبة WPF مفتوحة المصدر لحساب الرسوم البيانية وتصورها. تدعم العديد من خوارزميات التخطيط وتوجيه الحواف.
• أرشيف مطبوعات الرسم البياني الإلكترونية : يتضمن معلومات عن الأوراق البحثية من جميع ندوات الرسم البياني .