رسم بياني كثيف

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

لنفترض رسمًا بيانيًا بسيطًا${\displaystyle (V,E)}$أين${\displaystyle V}$هي مجموعة الرؤوس و${\displaystyle E}$هي مجموعة الحواف. نكتب${\displaystyle |V|}$للدلالة على عدد الرؤوس، و${\displaystyle |E|}$للدلالة على عدد الحواف. كثافة الرسم البياني للرسم البياني البسيط${\displaystyle (V,E)}$يتم تعريفها على أنها نسبة عدد الحواف | E | بالنسبة إلى الحد الأقصى للحواف الممكنة.

بالنسبة للرسوم البيانية البسيطة غير الموجهة ، تكون كثافة الرسم البياني كما يلي:

${\displaystyle D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}}$

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

${\displaystyle D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}}$

الحد الأقصى لعدد الحواف في الرسم البياني غير الموجه هو${\displaystyle {\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}}$لذا فإن الكثافة القصوى هي 1 (للرسوم البيانية الكاملة ) والكثافة الدنيا هي 0. ^{[ 1 ]}

بالنسبة لمجموعات الرسوم البيانية ذات الأحجام المتزايدة، يُطلق عليها غالبًا اسم الرسوم البيانية المتفرقة إذا${\displaystyle D\rightarrow 0}$مثل${\displaystyle |V|\rightarrow \infty }$في بعض الأحيان، في علوم الحاسوب ، يُستخدم تعريف أكثر تقييدًا للمصفوفات المتفرقة مثل${\displaystyle |E|=O(|V|\log |V|)}$أو حتى${\displaystyle |E|=O(|V|)}$في هذا السياق نفسه، يمكن تعريف الرسم البياني الكثيف بأنه أي رسم بياني تكون فيه قيمة | E | "قريبة" من${\displaystyle |V|^{2}}$[ ^{2 ] [ 3 ]​}

الكثافة العليا هي امتداد لمفهوم كثافة الرسم البياني المُعرَّف أعلاه، من الرسوم البيانية المحدودة إلى الرسوم البيانية غير المحدودة. وبشكلٍ بديهي، يحتوي الرسم البياني غير المحدود على عددٍ كبيرٍ من الرسوم البيانية الجزئية المحدودة ذات كثافةٍ أقل من كثافته العليا، ولا يحتوي على عددٍ كبيرٍ من الرسوم البيانية الجزئية المحدودة ذات كثافةٍ أكبر من كثافته العليا. رياضيًا، الكثافة العليا للرسم البياني G هي الحد الأدنى للقيم α التي تجعل الرسوم البيانية الجزئية المحدودة لـ G ذات الكثافة α تحتوي على عددٍ محدودٍ من الرؤوس. يمكن إثبات ذلك باستخدام نظرية ^{إردوش - ستون} أن الكثافة العليا لا يمكن أن تكون إلا 1 أو واحدة من النسب الفائقة 0 ، 1 / ​​2 ، 2 / 3 ، 3 / 4 ، 4 / 5 ، ... n / n + 1 [ 4 ]

عرّف لي وسترينو (2008) وسترينو وثيران ( 2009) الرسم البياني بأنه ( k , l ) -متفرق إذا كان كل رسم بياني فرعي غير فارغ ذي n رأس يحتوي على kn − l حافة على الأكثر، و ( k , l ) -متماسك إذا كان ( k , l ) -متفرقًا ويحتوي على kn − l حافة بالضبط. وبالتالي، فإن الأشجار هي بالضبط الرسوم البيانية (1,1) -المتماسكة، والغابات هي بالضبط الرسوم البيانية (1,1) -المتفرقة، والرسوم البيانية ذات التشعب k هي بالضبط الرسوم البيانية ( k , k ) -المتفرقة. أما الغابات الزائفة فهي بالضبط الرسوم البيانية (1,0) -المتفرقة، ورسوم لامان البيانية الناشئة في نظرية الصلابة هي بالضبط الرسوم البيانية (2,3) -المتماسكة. ^{[ 5 ]}

يمكن وصف عائلات الرسوم البيانية الأخرى التي لا تتميز بقلة عدد رؤوسها بهذه الطريقة أيضًا. على سبيل المثال ، حقيقة أن أي رسم بياني مستوٍ ذي n رأسًا يحتوي على 3n – 6 حواف على الأكثر (باستثناء الرسوم البيانية ذات أقل من 3 رؤوس)، وأن أي رسم بياني فرعي من رسم بياني مستوٍ هو رسم بياني مستوٍ، تشير مجتمعةً إلى أن الرسوم البيانية المستوية متفرقة من النوع (3,6) . مع ذلك، ليس كل رسم بياني متفرق من النوع (3,6) مستويًا. وبالمثل، فإن الرسوم البيانية الخارجية المستوية متفرقة من النوع (2,3)، والرسوم البيانية المستوية ثنائية الأجزاء متفرقة من النوع (2,4) .

يُظهر سترينو وثيران أنه يمكن إجراء اختبار ( k , l ) -التباعد في وقت متعدد الحدود عندما يكون k و l أعدادًا صحيحة و 0 ≤ l < 2k . ^{[ 6 ]}

بالنسبة لعائلة من الرسوم البيانية، فإن وجود قيمتين k و l بحيث تكون جميع الرسوم البيانية في العائلة متفرقة من النوع ( k , l ) يكافئ وجود رسوم بيانية في العائلة ذات انحلال محدود أو ذات تفرع محدود . وبشكل أدق، يتبين من نتيجة ناش-ويليامز (1964) أن الرسوم البيانية ذات التفرع على الأكثر a هي بالضبط الرسوم البيانية المتفرقة من النوع ( a , a ) . ^{[ 7 ]} وبالمثل، فإن الرسوم البيانية ذات الانحلال على الأكثر d هي${\displaystyle \left(d,{\binom {d+1}{2}}\right)}$الرسوم البيانية المتفرقة. ^{[ 8 ]}

اعتبر نيشيتريل وأوسونا دي مينديز (2010) أن ثنائية الكثافة/التباعد تستلزم النظر في فئات رسوم بيانية لا نهائية بدلاً من حالات الرسوم البيانية المفردة. وقد عرّفا فئات الرسوم البيانية الكثيفة في مكان ما بأنها فئات الرسوم البيانية التي يوجد لها عتبة t بحيث يظهر كل رسم بياني كامل كتقسيم فرعي من t في رسم بياني فرعي من رسم بياني في الفئة. وعلى النقيض من ذلك، إذا لم توجد مثل هذه العتبة، فإن الفئة غير كثيفة في أي مكان . ^{[ 9 ]}

تُدرج كل من فئات الرسوم البيانية ذات الانحلال المحدود والرسوم البيانية غير الكثيفة في أي مكان ضمن عائلات الرسوم البيانية الخالية من الثنائيات ، وهي عائلات رسوم بيانية تستبعد بعض الرسوم البيانية الثنائية الكاملة كرسوم بيانية فرعية. ^{[ 10 ]}

• التوسع المحدود
• رسم بياني فرعي كثيف

• كولمان، توماس ف .؛ موريه، خورخي ج. (1983)، "تقدير مصفوفات جاكوبي المتفرقة ومسائل تلوين الرسوم البيانية"، مجلة SIAM للتحليل العددي ، 20 (1): 187-209 ، Bibcode : 1983SJNA...20..187C ، doi : 10.1137/0720013
• ديستل، راينهارد (2005)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات ، سبرينغر-فيرلاغ، ISBN 3-540-26183-4، OCLC 181535575 
• لي، أودري؛ سترينو، إيليانا (2008)، "خوارزميات لعبة الحصى والرسوم البيانية المتفرقة"، الرياضيات المتقطعة ، 308 (8): 1425-1437 ، arXiv : math/0702129 ، doi : 10.1016/j.disc.2007.07.104 ، MR 2392060 
• ناش-ويليامز، سي. سانت جيه إيه (1964)، "تحليل الرسوم البيانية المحدودة إلى غابات"، مجلة جمعية لندن الرياضية ، 39 (1): 12، doi : 10.1112/jlms/s1-39.1.12 ، MR 0161333 
• ليك، دون ر؛ وايت، آرثر ت (1970)، " الرسوم البيانية المنحلة من الرتبة k " ، المجلة الكندية للرياضيات ، 22 (5): 1082-1096 ، doi : 10.4153/CJM-1970-125-1
• بريس، الطبعة الأولى (1998)، هياكل البيانات والخوارزميات مع أنماط التصميم الموجهة للكائنات في لغة C++ ، جون وايلي وأولاده، رقم ISBN 0-471-24134-2
• نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس ( 2010)، "من الرسوم البيانية المتفرقة إلى الهياكل غير الكثيفة: التفكيكات، والاستقلال، والازدواجيات، والنهايات"، المؤتمر الأوروبي للرياضيات ، الجمعية الرياضية الأوروبية، ص 135-165 
• نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد  28، هايدلبرغ: سبرينغر، doi : 10.1007/978-3-642-27875-4 ، ISBN 978-3-642-27874-7MR 2920058​ 
• سترينو، آي .؛ ثيران، إل. (2009)، "الرسوم البيانية الفائقة المتفرقة وخوارزميات لعبة الحصى"، المجلة الأوروبية للتوافقية ، 30 (8): 1944-1964 ، arXiv : math/0703921 ، doi : 10.1016/j.ejc.2008.12.018
• تيل، جان آرني؛ فيلانجر، ينجفي (2012)، "خوارزميات FPT للهيمنة في الرسوم البيانية الخالية من الثنائيات"، في إبستين، ليا؛ فيراجينا، باولو (محرران)، الخوارزميات - ESA 2012: الندوة الأوروبية السنوية العشرون، ليوبليانا، سلوفينيا، 10-12 سبتمبر 2012، وقائع ، سلسلة محاضرات في علوم الحاسوب ، المجلد  7501، سبرينغر، الصفحات 802-812 ، doi : 10.1007/978-3-642-33090-2_69 ، ISBN  978-3-642-33089-6

• بلاك، بول إي، "الرسم البياني المتفرق"، قاموس الخوارزميات وهياكل البيانات ، المعهد الوطني للمعايير والتكنولوجيا ، تم الاطلاع عليه في 29 سبتمبر 2005