الرسم البياني الفائق

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 153 صور
الموسوعة الحرة
مثال على الرسم البياني الفائق غير الموجه، مع X={v1،v2،v3،v4،v5،v6،v7}{\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}و هـ={هـ1،هـ2،هـ3،هـ4}={\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}{{v1،v2،v3}،{\displaystyle \{\{v_{1},v_{2},v_{3}\},}{v2،v3}،{\displaystyle \{v_{2},v_{3}\},}{v3،v5،v6}،{\displaystyle \{v_{3},v_{5},v_{6}\},}{v4}}{\displaystyle \{v_{4}\}\}}. هذا الرسم البياني الفائق له رتبة 7 وحجم 4. هنا، لا تربط الحواف رأسين فقط بل عدة رؤوس، ويتم تمثيلها بالألوان.
تصوير PAOH للرسم البياني الفائق
تمثيل بديل للرسم البياني الفائق الموضح في الشكل أعلاه، يُسمى PAOH. [ 1 ] الحواف عبارة عن خطوط رأسية تربط الرؤوس. V7 رأس معزول. الرؤوس محاذية لليسار. يوضح مفتاح الرسم على اليمين أسماء الحواف.
منح أ1:=({1}،{2}){\displaystyle {a_{1}:=\left(\{1\},\{2\}\right)}}و أ2:=({2}،{3}){\displaystyle {a_{2}:=\left(\{2\},\{3\}\right)}}و أ3:=({3}،{1}){\displaystyle {a_{3}:=\left(\{3\},\{1\}\right)}}و أ4:=({2،3}،{4،5}){\displaystyle {a_{4}:=\left(\{2,3\},\{4,5\}\right)}}و أ5:=({3،5}،{6}){\displaystyle {a_{5}:=\left(\{3,5\},\{6\}\right)}}و هـ:={أ1،أ2،أ3،أ4،أ5}{\displaystyle {E:=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}}}و X:={1،2،3،4،5،6}{\displaystyle {X:=\{1,2,3,4,5,6\}}}وأخيراً، الزوجان (X،هـ){\displaystyle {\left(X,E\right)}} سيصف الرسم البياني الموجه.

في الرياضيات ، يُعدّ الرسم البياني الفائق تعميماً للرسم البياني ، حيث يمكن للحافة أن تربط أي عدد من الرؤوس . في المقابل، في الرسم البياني العادي، تربط الحافة رأسين فقط.

بصورة رسمية، فإن الرسم البياني الفائق الموجه هو زوج(X،هـ){\displaystyle (X,E)}، أينX{\displaystyle X}هي مجموعة من العناصر تسمى العقد أو الرؤوس أو النقاط أو العناصر وهـ{\displaystyle E}هي مجموعة من أزواج المجموعات الجزئية منX{\displaystyle X}كل زوج من هذه الأزواج(د،ج)∈هـ{\displaystyle (D,C)\in E}يُطلق عليه اسم الحافة أو الحافة الفائقة ؛ مجموعة الرؤوسد{\displaystyle D}يُعرف باسم ذيله أو نطاقه ، وج{\displaystyle C}كرأسها أو نطاقها المشترك .

ترتيب الرسم البياني الفائق(X،هـ){\displaystyle (X,E)}يمثل عدد الرؤوس فيX{\displaystyle X}حجم الرسم البياني الفائق هو عدد الحواف فيههـ{\displaystyle E}رتبة الحافةهـ=(د،ج){\displaystyle e=(D,C)}في الرسم البياني الفائق الموجه هو|هـ|=(|د|،|ج|){\displaystyle |e|=(|D|,|C|)}أي عدد الرؤوس في ذيله متبوعًا بعدد الرؤوس في رأسه.

يُعمم التعريف أعلاه من الرسم البياني الموجه إلى الرسم البياني الفائق الموجه عن طريق تعريف رأس أو ذيل كل حافة كمجموعة من الرؤوس (ج⊆X{\displaystyle C\subseteq X}أود⊆X{\displaystyle D\subseteq X}بدلاً من اعتبارها رأسًا واحدًا. الرسم البياني هو الحالة الخاصة التي تحتوي فيها كل مجموعة من هذه المجموعات على عنصر واحد فقط. ومن ثم، فإن أي مفهوم قياسي في نظرية الرسم البياني مستقل عن ترتيب الحواف|هـ|{\displaystyle |e|}سيتم تعميم ذلك على نظرية الرسم البياني الفائق.

بالنظر إلى مجموعة X{\displaystyle {X}} بمجموعة الطاقة الخاصة بها P(X){\displaystyle {{\mathcal {P}}\left(X\right)}}بالإضافة إلى مجموعة هـ{\displaystyle {E}} مع هـ⊆P(X){\displaystyle {E\subseteq {\mathcal {P}}\left(X\right)}}الزوجان (X،هـ){\displaystyle {\left(X,E\right)}} يُطلق عليه اسم الرسم البياني الفائق غير الموجه.

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

للمخططات الفائقة أسماء أخرى عديدة. في الهندسة الحسابية ، يُطلق على المخطط الفائق غير الموجه أحيانًا اسم فضاء المدى ، وتُسمى حينها الحواف الفائقة بالمدى . [ 2 ] في نظرية الألعاب التعاونية ، تُسمى المخططات الفائقة بالألعاب البسيطة (ألعاب التصويت)؛ ويُطبق هذا المفهوم لحل مسائل نظرية الاختيار الاجتماعي . في بعض المراجع، يُشار إلى الحواف بالروابط التشعبية أو الموصلات . [ 3 ]

مجموعة الرسوم البيانية الفائقة هي فئة تحتوي على تماثلات الرسوم البيانية الفائقة كتشاكلات .

التطبيقات

تُعدّ المخططات الفائقة غير الموجهة مفيدة في نمذجة مسائل مثل مسائل الإرضاء، [ 4 ] وقواعد البيانات، [ 5 ] والتعلم الآلي، [ 6 ] ومسائل شجرة شتاينر . [ 7 ] وقد استُخدمت على نطاق واسع في مهام التعلم الآلي كنموذج بيانات وتنظيم للمصنف . [ 8 ] تشمل التطبيقات أنظمة التوصية (المجتمعات كحواف فائقة)، [ 9 ] [ 10 ] واسترجاع الصور (الارتباطات كحواف فائقة)، [ 11 ] والمعلوماتية الحيوية (التفاعلات الكيميائية الحيوية كحواف فائقة). [ 12 ] تتضمن تقنيات تعلم المخططات الفائقة التمثيلية التجميع الطيفي للمخططات الفائقة الذي يوسع نظرية المخطط الطيفي باستخدام لابلاس المخطط الفائق، [ 13 ] والتعلم شبه الموجه للمخططات الفائقة الذي يُضيف تكلفة هيكلية إضافية للمخطط الفائق لتقييد نتائج التعلم. [ 14 ] بالنسبة للمخططات الفائقة واسعة النطاق، يتوفر أيضًا إطار عمل موزع [ 6 ] مبني باستخدام أباتشي سبارك . قد يكون من المستحسن دراسة المخططات الفائقة التي تتساوى فيها جميع الحواف الفائقة في عدد العناصر؛ فالمخطط الفائق المنتظم من الرتبة k هو مخطط فائق تكون فيه جميع حوافه الفائقة من الرتبة k . (بمعنى آخر، أحد هذه المخططات الفائقة هو مجموعة من المجموعات، كل مجموعة منها حافة فائقة تربط k عقدة). لذا، فإن المخطط الفائق المنتظم من الرتبة 2 هو مخطط، والمخطط الفائق المنتظم من الرتبة 3 هو مجموعة من الثلاثيات غير المرتبة، وهكذا.

يمكن استخدام الرسوم البيانية الموجهة لنمذجة أمور تشمل تطبيقات الاتصالات الهاتفية، [ 15 ] وكشف غسيل الأموال ، [ 16 ] وبحوث العمليات، [ 17 ] وتخطيط النقل. كما يمكن استخدامها لنمذجة قابلية إرضاء هورن . [ 18 ]

تعميمات للمفاهيم من الرسوم البيانية

تنطبق العديد من النظريات والمفاهيم المتعلقة بالرسوم البيانية أيضًا على الرسوم البيانية الفائقة، على وجه الخصوص:

في الرسوم البيانية الفائقة الموجهة: الإغلاق المتعدي ، ومسائل أقصر مسار. [ 17 ]

رسم بياني فائق

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

على الرغم من أن رسم المخططات الفائقة على الورق أصعب من رسم المخططات العادية، فقد درس العديد من الباحثين طرقًا لتصور المخططات الفائقة.

في أحد التمثيلات المرئية الممكنة للرسوم البيانية الفائقة، على غرار أسلوب رسم الرسوم البيانية القياسي الذي تُستخدم فيه المنحنيات في المستوى لتصوير حواف الرسم البياني، تُصوَّر رؤوس الرسم البياني الفائق كنقاط أو أقراص أو مربعات، وتُصوَّر حوافه الفائقة كأشجارٍ تُشكِّل رؤوسها أوراقها. [ 19 ] [ 20 ] إذا مُثِّلت الرؤوس كنقاط، فيمكن أيضًا عرض الحواف الفائقة كمنحنيات سلسة تربط مجموعات من النقاط، أو كمنحنيات مغلقة بسيطة تُحيط بمجموعات من النقاط. [ 21 ] [ 22 ] [ 23 ]

مخطط فين من الرتبة 4، والذي يمكن تفسيره على أنه رسم تقسيم فرعي لمخطط فائق يحتوي على 15 رأسًا (المناطق الملونة الـ 15) و 4 حواف فائقة (الأشكال البيضاوية الأربعة).

في أسلوب آخر لتصوير المخططات الفائقة، وهو نموذج تقسيم المخططات الفائقة [ 24 ] ، يُقسّم المستوى إلى مناطق، تمثل كل منها رأسًا واحدًا من رؤوس المخطط الفائق. تُمثَّل الحواف الفائقة للمخطط الفائق بمجموعات فرعية متجاورة من هذه المناطق، ويمكن الإشارة إليها بالتلوين، أو برسم حدود حولها، أو كليهما. على سبيل المثال، يمكن اعتبار مخطط فين من الرتبة n رسمًا لتقسيم مخطط فائق ذي n حافة فائقة (المنحنيات التي تُعرّف المخطط) و2 n - 1 رأسًا (مُمثَّلة بالمناطق التي تُقسّم إليها هذه المنحنيات المستوى). على عكس التعرف على المخططات المستوية في وقت متعدد الحدود، فإن تحديد ما إذا كان للمخطط الفائق رسم تقسيم مستوٍ يُعد مسألة NP-كاملة [ 25 ]، ولكن يمكن اختبار وجود رسم من هذا النوع بكفاءة عندما يكون نمط تجاور المناطق مقيدًا بأن يكون مسارًا أو دورة أو شجرة. [ 26 ]  

يُظهر الشكل أعلى هذه المقالة تمثيلاً بديلاً للرسم البياني الفائق يُسمى PAOH [ 1 ] . الحواف عبارة عن خطوط رأسية تربط الرؤوس، والرؤوس مُرتبة على اليسار. يُظهر مفتاح الرسم على اليمين أسماء الحواف. صُمم هذا التمثيل للرسوم البيانية الفائقة الديناميكية، ولكنه يُمكن استخدامه أيضاً للرسوم البيانية الفائقة البسيطة.

تلوين الرسم البياني الفائق

تلوين الرسم البياني الفائق الكلاسيكي هو تعيين أحد الألوان من مجموعة{1،2،3،...،λ}{\displaystyle \{1,2,3,...,\لامدا \}}يُطبَّق التلوين على كل رأس من رؤوس الرسم البياني الفائق بحيث يحتوي كل ضلع فائق على رأسين على الأقل بلونين مختلفين. بعبارة أخرى، لا يجوز وجود ضلع فائق أحادي اللون بعدد عناصر لا يقل عن 2. وبهذا المعنى، يُعدّ التلوين تعميمًا مباشرًا لتلوين الرسوم البيانية. يُطلق على الحد الأدنى لعدد الألوان المختلفة المستخدمة في جميع عمليات التلوين اسم العدد اللوني للرسم البياني الفائق.

تُسمى الرسوم البيانية الفائقة التي يمكن تلوينها باستخدام ما يصل إلى k لونًا بالرسوم البيانية ذات k لونًا . أما الرسوم البيانية الفائقة ذات لونين فهي تحديدًا الرسوم البيانية ثنائية الأجزاء.

توجد العديد من التعميمات لتلوين المخططات الفائقة الكلاسيكية. أحدها ما يُسمى بتلوين المخططات الفائقة المختلطة، حيث يُسمح باستخدام حواف أحادية اللون. بعض المخططات الفائقة المختلطة غير قابلة للتلوين بأي عدد من الألوان. ولا يوجد معيار عام لعدم قابلية التلوين. عندما يكون المخطط الفائق المختلط قابلاً للتلوين، يُطلق على الحد الأدنى والحد الأقصى لعدد الألوان المستخدمة اسمي العددين اللونيين الأدنى والأعلى على التوالي. [ 27 ]

خصائص الرسوم البيانية الفائقة

يمكن أن يمتلك الرسم البياني الفائق خصائص متنوعة، مثل:

  • فارغ - ليس له حواف.
  • غير بسيط (أو متعدد ) - يحتوي على حلقات (حواف فائقة ذات رأس واحد) أو حواف متكررة، مما يعني أنه يمكن أن يكون هناك حافتان أو أكثر تحتويان على نفس مجموعة الرؤوس.
  • بسيط - لا يحتوي على حلقات ولا حواف متكررة.
  • د{\displaystyle d}-منتظم- لكل رأس درجةد{\displaystyle d}أي، موجود في بالضبطد{\displaystyle d}الحواف الفائقة.
  • قابل للتلوين بلونين - يمكن تقسيم رؤوسه إلى فئتين U و V بحيث يحتوي كل ضلع فائق ذو عدد عناصر لا يقل عن 2 على رأس واحد على الأقل من كلتا الفئتين. مصطلح بديل هو الخاصية B.
  • ك{\displaystyle k}-موحد - كل حافة فائقة تحتوي بدقةك{\displaystyle k}الرؤوس.
  • ك{\displaystyle k}-partite - يتم تقسيم الرؤوس إلىك{\displaystyle k}أجزاء، وكل حافة فائقة تحتوي على رأس واحد بالضبط من كل نوع.
    • كلك{\displaystyle k}الرسم البياني الفائق ذو الأجزاء (لـ)ك≥2{\displaystyle k\geq 2}) هو كلاهماك{\displaystyle k}-موحد وثنائي الأجزاء (وقابل للتلوين بلونين).
  • مُختزل : [ 28 ] لا يوجد ضلع فائق مجموعة جزئية صارمة من ضلع فائق آخر؛ أو بعبارة أخرى، كل ضلع فائق يكون أقصى ما يمكن تضمينه. اختزال الرسم البياني الفائق هو الرسم البياني الفائق المُختزل الناتج عن إزالة كل ضلع فائق مُضمن في ضلع فائق آخر.
  • مغلق تنازليًا - كل مجموعة جزئية من حواف الرسم البياني الفائق غير الموجه هي أيضًا حافة فائقة. يُطلق على الرسم البياني الفائق المغلق تنازليًا عادةً اسم مُركب تبسيطي مجرد . وهو غير مُختزل عمومًا، إلا إذا كانت جميع الحواف الفائقة ذات عدد عناصر يساوي 1.
    • يُطلق على المركب التبسيطي المجرد الذي يتمتع بخاصية التضخيم اسم الماترويد .
  • صفائحي : بالنسبة لأي حافتين فائقتين، إما أن تكونا منفصلتين، أو أن إحداهما مضمنة في الأخرى. بعبارة أخرى، تشكل مجموعة الحواف الفائقة عائلة مجموعات صفائحية .
  • متصل : للجميعS⊆X{\displaystyle S\subseteq X}مع∅≠S≠X{\displaystyle \emptyset \neq S\neq X}هنالكهـ∈هـ{\displaystyle e\in E}هذا يلبي كلا الأمرينS{\displaystyle S}وX∖S{\displaystyle X\setminus S}. يُطلق على الرسم البياني الفائق غير المتصل اسم الرسم البياني المنفصل .

نظراً لأن روابط الرسم البياني الفائق يمكن أن يكون لها أي عدد من العناصر، فهناك العديد من المفاهيم لمفهوم الرسم البياني الفرعي، والتي تسمى الرسوم البيانية الفائقة الفرعية ، والرسوم البيانية الفائقة الجزئية ، والرسوم البيانية الفائقة المقطعية .

يتركح=(X،هـ){\displaystyle H=(X,E)}ليكن الرسم البياني الفائق المكون من رؤوس

X={xأنا|أنا∈أناv}،{\displaystyle X=\lbrace x_{i}\mid i\in I_{v}\rbrace ,}

ووجود حافة محددة

هـ={هـأنا|أنا∈أناهـ،هـأنا⊆X،هـأنا≠∅}،{\displaystyle E=\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq X,e_{i}\neq \emptyset \rbrace ,}

أينأناv{\displaystyle I_{v}}وأناهـ{\displaystyle I_{e}}تمثل مجموعات الفهرس للرؤوس والحواف على التوالي.

الرسم البياني الفرعي الفائق هو رسم بياني فائق تم حذف بعض رؤوسه. رسميًا، الرسم البياني الفرعي الفائقحأ{\displaystyle H_{A}}ناتج عنأ⊆X{\displaystyle A\subseteq X}يُعرَّف بأنه

حأ=(أ،{هـ∩أ|هـ∈هـ،هـ∩أ≠∅}).{\displaystyle H_{A}=\left(A,\lbrace e\cap A\mid e\in E,e\cap A\neq \emptyset \rbrace \right).}

مصطلح بديل هو تقييد H على A. [ 29 ] : 468

مكون متصل منح{\displaystyle H}هو رسم بياني فرعي متصل أقصى منح{\displaystyle H}أي، رسم بياني فرعيحأ{\displaystyle H_{A}}لح{\displaystyle H}ناتج عنأ{\displaystyle A}بحيثحأ{\displaystyle H_{A}}متصل ولا يوجد رسم بياني فرعيحأ′{\displaystyle H_{A'}}معأ⊊أ′{\displaystyle A\subsetneq A'}متصل.

امتداد الرسم البياني الفرعي الفائق هو رسم بياني فائق حيث كل حافة فائقة منح{\displaystyle H}والذي يقع جزئياً ضمن الرسم البياني الفرعي الفائقحأ{\displaystyle H_{A}}يتم تضمينها بالكامل في الامتدادهـx(حأ){\displaystyle Ex(H_{A})}رسميًا

هـx(حأ)=(أ∪أ′،هـ′){\displaystyle Ex(H_{A})=(A\cup A',E')}معأ′=⋃هـ∈هـهـ∖أ{\displaystyle A'=\bigcup _{e\in E}e\setminus A}وهـ′={هـ∈هـ|هـ⊆(أ∪أ′)}{\displaystyle E'=\lbrace e\in E\mid e\subseteq (A\cup A')\rbrace }.

الرسم البياني الفائق الجزئي هو رسم بياني فائق تم حذف بعض حوافه. [ 29 ] : 468 معطى مجموعة جزئيةج⊂أناهـ{\displaystyle J\subset I_{e}}من مجموعة مؤشرات الحواف، الرسم البياني الفائق الجزئي الناتج عنج{\displaystyle J}هو الرسم البياني الفائق

(X،{هـأنا|أنا∈ج}).{\displaystyle \left(X,\lbrace e_{i}\mid i\in J\rbrace \right).}

بالنظر إلى مجموعة جزئيةأ⊆X{\displaystyle A\subseteq X}، الرسم البياني الفائق المقطعي هو الرسم البياني الفائق الجزئي

ح×أ=(أ،{هـأنا|أنا∈أناهـ،هـأنا⊆أ}).{\displaystyle H\times A=\left(A,\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq A\rbrace \right).}

الثنائي​ح*{\displaystyle H^{*}}لح{\displaystyle H}هو رسم بياني فائق يتم فيه تبديل رؤوسه وحوافه، بحيث يتم تحديد الرؤوس بواسطة{هـأنا}{\displaystyle \lbrace e_{i}\rbrace }والتي تُعطى حوافها بواسطة{Xم}{\displaystyle \lbrace X_{m}\rbrace }أين

Xم={هـأنا|xم∈هـأنا}.{\displaystyle X_{m}=\lbrace e_{i}\mid x_{m}\in e_{i}\rbrace .}

عندما يتم تعريف مفهوم المساواة بشكل صحيح، كما هو موضح أدناه، فإن عملية أخذ ثنائي الرسم البياني الفائق هي عملية انعكاس ، أي

(ح*)*=ح.{\displaystyle \left(H^{*}\right)^{*}=H.}

يُطلق على الرسم البياني المتصل G الذي له نفس مجموعة الرؤوس للرسم البياني الفائق المتصل H اسم الرسم البياني المضيف لـ H إذا كان كل ضلع فائق في H يُنشئ رسمًا بيانيًا فرعيًا متصلًا في G. أما بالنسبة للرسم البياني الفائق غير المتصل H ، فيُطلق على G اسم الرسم البياني المضيف إذا وُجد تقابل بين المكونات المتصلة لـ G و H ، بحيث يكون كل مكون متصل G ' من G هو مضيف للرسم البياني H ' المقابل .

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

مصفوفة الحدوث

يتركV={v1،v2، ...، vن}{\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}}وهـ={هـ1،هـ2، ... هـم}{\displaystyle E=\{e_{1},e_{2},~\ldots ~e_{m}\}}كل رسم بياني فائق لهن×م{\displaystyle n\times m}مصفوفة الحدوث .

بالنسبة للرسم البياني الفائق غير الموجه،أنا=(بأناج){\displaystyle I=(b_{ij})}أين

بأناج={1أناو vأنا∈هـج0oتحهـرwأناsهـ.{\displaystyle b_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}

التحويل​أنات{\displaystyle I^{t}}تحدد مصفوفة الحدوث رسمًا بيانيًا فائقًاح*=(V*، هـ*){\displaystyle H^{*}=(V^{*},\ E^{*})}يُطلق عليه اسم ثنائيح{\displaystyle H}، أينV*{\displaystyle V^{*}}هي مجموعة مكونة من m عنصرًا وهـ*{\displaystyle E^{*}}هي مجموعة مكونة من n عنصر من مجموعات جزئية منV*{\displaystyle V^{*}}. لvج*∈V*{\displaystyle v_{j}^{*}\in V^{*}}وهـأنا*∈هـ*، vج*∈هـأنا*{\displaystyle e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}}إذا وفقط إذابأناج=1{\displaystyle b_{ij}=1}.

بالنسبة للرسم البياني الفائق الموجه، رؤوس وذيول كل حافة فائقةهـج{\displaystyle e_{j}}يُشار إليها بـح(هـج){\displaystyle H(e_{j})}وتي(هـج){\displaystyle T(e_{j})}على التوالي. [ 18 ]أنا=(بأناج){\displaystyle I=(b_{ij})}أين

بأناج={-1أناو vأنا∈تي(هـج)1أناو vأنا∈ح(هـج)0oتحهـرwأناsهـ.{\displaystyle b_{ij}=\left\{{\begin{matrix}-1&\mathrm {if} ~v_{i}\in T(e_{j})\\1&\mathrm {if} ~v_{i}\in H(e_{j})\\0&\mathrm {otherwise} .\end{matrix}}\right.}

رسم بياني للحالات

يمكن تمثيل الرسم البياني الفائق H بواسطة رسم بياني ثنائي الأجزاء BG على النحو التالي: المجموعات X و E هي أجزاء من BG ، و ( x 1 ، e 1 ) متصلة بحافة إذا وفقط إذا كان الرأس x 1 موجودًا في الحافة e 1 في H.

في المقابل، يُمثل أي رسم بياني ثنائي الأجزاء ذو ​​أجزاء ثابتة ولا يحتوي على عقد غير متصلة في الجزء الثاني رسمًا بيانيًا فائقًا على النحو الموصوف أعلاه. ويُسمى هذا الرسم البياني الثنائي أيضًا برسم بياني للوقوع .

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

يمكن استخلاص تشابه بين مصفوفة التجاور للرسم البياني الفائق ومصفوفة التجاور للرسم البياني. ففي حالة الرسم البياني، تكون مصفوفة التجاور مصفوفة مربعة تُشير إلى ما إذا كان زوجا الرؤوس متجاورين أم لا . وبالمثل، يمكننا تعريف مصفوفة التجاورأ=(أأناج){\displaystyle A=(a_{ij})}بالنسبة للرسم البياني الفائق بشكل عام حيث تكون الحواف الفائقةهـك≤م{\displaystyle e_{k\leq m}}لها أوزان حقيقيةwهـك∈R{\displaystyle w_{e_{k}}\in \mathbb {R} }مع

أأناج={wهـكأناو (vأنا،vج)∈هـ0oتحهـرwأناsهـ.{\displaystyle a_{ij}=\left\{{\begin{matrix}w_{e_{k}}&\mathrm {if} ~(v_{i},v_{j})\in E\\0&\mathrm {otherwise} .\end{matrix}}\right.}

دورات

على عكس الرسوم البيانية غير الموجهة العادية التي يوجد لها مفهوم طبيعي واحد للدورات والرسوم البيانية غير الدورية ، توجد في الرسوم البيانية الفائقة تعريفات طبيعية متعددة غير متكافئة للدورات، والتي تؤول إلى المفهوم العادي للدورة عند النظر في حالة الرسم البياني.

دورات بيرج

قدّم كلود بيرج أول مفهوم للدورة . [ 30 ] دورة بيرج في الرسم البياني الفائق هي سلسلة متناوبة من الرؤوس والحواف المتميزة(v1،هـ1،...،vن،هـن){\displaystyle (v_{1},e_{1},\dots ,v_{n},e_{n})}، أينن≥2{\displaystyle n\geq 2}وvأنا،vأنا+1{\displaystyle v_{i},v_{i+1}}كلاهما فيهـأنا{\displaystyle e_{i}}لكلأنا∈[ن]{\displaystyle i\in [n]}(مع أخذ المؤشرات بترددن{\displaystyle n}).

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

دورات ضيقة

يُستخدم هذا التعريف بشكل خاص لـك{\displaystyle k}- الرسوم البيانية الفائقة المنتظمة، حيث تكون جميع الحواف الفائقة بحجمك{\displaystyle k}دورة قصيرة من الطولن{\displaystyle n}في الرسم البياني الفائقح{\displaystyle H}هي سلسلة من الرؤوس المتميزةv1،...،vن{\displaystyle v_{1},\dots ,v_{n}}بحيث يكون كل متتاليك{\displaystyle k}-مترابطة بيانية{vأنا،...،vأنا+ك-1}{\displaystyle \{v_{i},\dots ,v_{i+k-1}\}}(المؤشرات moduloن{\displaystyle n}) يشكل حافة فائقة فيح{\displaystyle H}قدّم كاتونا وكيرستيد هذا المفهوم [ 31 ] ، ومنذ ذلك الحين حظي باهتمام كبير، لا سيما في دراسة الهاميلتونية في التوافقية المتطرفة. [ 32 ] [ 33 ]

أظهر Rödl وSzemerédi وRuciński ذلكن{\displaystyle n}-vertexك{\displaystyle k}- رسم بياني فائق منتظمح{\displaystyle H}حيث كل(ك-1){\displaystyle (k-1)}مجموعة فرعية من الرؤوس تحتوي على الأقلن/2+o(ن){\displaystyle n/2+o(n)}تحتوي الحواف الفائقة على دورة هاميلتون. وهذا يتوافق مع امتداد تقريبي للرسوم البيانية الفائقة لنظرية ديراك الشهيرة حول دورات هاميلتون في الرسوم البيانية. [ 34 ]

الحد الأقصى لعدد الحواف الفائقة في بنية غير دورية (مُحكمة)ك{\displaystyle k}لا يزال الرسم البياني الفائق المنتظم غير معروف.ك=2{\displaystyle k=2}من المعروف أن هذا الرقم هون-1{\displaystyle n-1}. لك≥3{\displaystyle k\geq 3}تُظهر أفضل الحدود المعروفة، والتي وضعها جانزر [ 35 ] وليتزر [ 36 ] ، أن هذا العدد الأقصى يقع بينΩ(نك-1سجل⁡ن/سجل⁡سجل⁡ن){\displaystyle \Omega (n^{k-1}\log n/\log \log n)}ويا(نك-1(سجل⁡ن)5){\displaystyle O(n^{k-1}(\log n)^{5})}تكون الحدود مثالية حتى عامل متعدد اللوغاريتمات.

أنل{\displaystyle l}تُعمم الدورة - مفهوم الدورة المحكمة. وهي تتكون من سلسلة من الرؤوسv1،...،vن{\displaystyle v_{1},\dots ,v_{n}}والحواف الفائقةهـ1،...،هـت{\displaystyle e_{1},\dots ,e_{t}}حيث كلهـأنا{\displaystyle e_{i}}يتكون منك{\displaystyle k}الرؤوس المتتالية في التسلسل و|هـأنا∩هـأنا+1|=ل{\displaystyle |e_{i}\cap e_{i+1}|=l}لكل1≤أنا≤ت{\displaystyle 1\leq i\leq t}بما أن كل حافة منل{\displaystyle l}-cycle يحتوي بالضبطك-ل{\displaystyle k-l}الرؤوس التي لا تقع ضمن الحافة السابقة،ن{\displaystyle n}يجب أن يكون قابلاً للقسمة علىك-ل{\displaystyle k-l}. لاحظ أنل=ك-1{\displaystyle l=k-1}يستعيد تعريف الدورة المحكمة.

عدم انتظام ألفا

قد يبدو تعريف بيرج-الدورية مقيدًا للغاية: على سبيل المثال، إذا كان للرسم البياني الفائق زوج ماv≠v′{\displaystyle v\neq v'}من الرؤوس وبعض الأزواجو≠و′{\displaystyle f\neq f'}من الحواف الفائقة بحيثv،v′∈و{\displaystyle v,v'\in f}وv،v′∈و′{\displaystyle v,v'\in f'}إذن فهو دوري بيرج.

يمكننا تعريف مفهوم أضعف لعدم وجود دورات في المخططات الفائقة، [ 5 ] والذي يُطلق عليه لاحقًا اسم عدم وجود دورات من النوع ألفا. يُكافئ هذا المفهوم عدم وجود دورات في المخطط الفائق كونه متطابقًا (أي أن كل زمرة من المخطط الأولي مغطاة بحافة فائقة ما) وأن يكون المخطط الأولي وتريًا ؛ كما يُكافئ أيضًا إمكانية الاختزال إلى المخطط الفارغ من خلال خوارزمية GYO [ 37 ] [ 38 ] (المعروفة أيضًا باسم خوارزمية غراهام)، وهي عملية تكرارية متقاربة تُزيل الحواف الفائقة باستخدام تعريف مُعمم للآذان . في مجال نظرية قواعد البيانات ، من المعروف أن مخطط قاعدة البيانات يتمتع بخصائص مرغوبة معينة إذا كان مخططه الفائق الأساسي غير دوري من النوع ألفا. [ 39 ] بالإضافة إلى ذلك، يرتبط عدم وجود دورات من النوع ألفا أيضًا بقدرة التعبير للجزء المحمي من منطق الرتبة الأولى .

يمكننا اختبار ما إذا كان الرسم البياني الفائق غير دوري من النوع ألفا في وقت خطي . [ 40 ]

تجدر الإشارة إلى أن خاصية عدم الدورية من النوع ألفا (α-acyclicity) تتسم بخاصية غير بديهية، وهي أن إضافة حواف فائقة إلى رسم بياني فائق دوري من النوع ألفا (α-cyclic) قد تجعله غير دوري من النوع ألفا (α-acyclic) (على سبيل المثال، إضافة حافة فائقة تحتوي على جميع رؤوس الرسم البياني الفائق ستجعله دائمًا غير دوري من النوع ألفا). وانطلاقًا جزئيًا من هذا القصور الملحوظ، عرّف رونالد فاجين [ 41 ] مفهومي عدم الدورية من النوع بيتا (β-acyclicity) وعدم الدورية من النوع غاما (γ-acyclicity) الأكثر قوة. ويمكننا تعريف عدم الدورية من النوع بيتا (β-acyclicity) بأنه الشرط الذي يجعل جميع الرسوم البيانية الفائقة الفرعية للرسم البياني الفائق غير دورية من النوع ألفا (α-acyclic)، وهو ما يكافئ [ 41 ] تعريفًا سابقًا لغراهام [ 38 ] . أما مفهوم عدم الدورية من النوع غاما (γ-acyclicity) فهو شرط أكثر تقييدًا، ويكافئ العديد من الخصائص المرغوبة لمخططات قواعد البيانات، ويرتبط بمخططات باخمان . ويمكن اختبار كل من عدم الدورية من النوع بيتا (β-acyclicity) وعدم الدورية من النوع غاما (γ-acyclicity) في وقت متعدد الحدود .

تتشابه هذه المفاهيم الأربعة لعدم الدورية: عدم الدورية من النوع غاما، والذي يستلزم عدم الدورية من النوع بيتا، والذي يستلزم بدوره عدم الدورية من النوع ألفا. علاوة على ذلك، فإن عدم الدورية من النوع بيرج يستلزم جميعها. ولا يصح أي من الاستلزام العكسي، بما في ذلك استلزام بيرج. بعبارة أخرى، هذه المفاهيم الأربعة مختلفة. [ 41 ]

التماثل، والتناظر، والمساواة

التماثل الفائق هو دالة من مجموعة رؤوس رسم بياني فائق إلى آخر بحيث يتم ربط كل حافة بحافة أخرى.

الرسم البياني الفائقح=(X،هـ){\displaystyle H=(X,E)}متماثل مع الرسم البياني الفائقجي=(Y،F){\displaystyle G=(Y,F)}، مكتوبة على النحو التاليح≃جي{\displaystyle H\simeq G}إذا كان هناك تقابل

ϕ:X→Y{\displaystyle \phi :X\to Y}

وتبديل​π{\displaystyle \pi }لأنا{\displaystyle I}بحيث

ϕ(هـأنا)=وπ(أنا){\displaystyle \phi (e_{i})=f_{\pi (i)}}

التقابلϕ{\displaystyle \phi }يُطلق على هذا اسم تماثل الرسوم البيانية. لاحظ أن

ح≃جي{\displaystyle H\simeq G}إذا وفقط إذاح*≃جي*{\displaystyle H^{*}\simeq G^{*}}.

عندما تُسمى حواف الرسم البياني الفائق بشكل صريح، يتوفر مفهوم إضافي هو التشاكل القوي . ويُقال أنح{\displaystyle H}متماثل بشكل كبير معجي{\displaystyle G}إذا كان التبديل هو العنصر المحايد. عندئذٍ يكتب المرءح≅جي{\displaystyle H\cong G}لاحظ أن جميع الرسوم البيانية المتماثلة بقوة متماثلة، ولكن ليس العكس.

عندما تُسمى رؤوس الرسم البياني الفائق بشكل صريح، فإن المرء يمتلك مفاهيم التكافؤ ، وكذلك المساواة . ويقول المرء أنح{\displaystyle H}يعادل​​جي{\displaystyle G}ويكتبح≡جي{\displaystyle H\equiv G}إذا كان التشاكلϕ{\displaystyle \phi }لديه

ϕ(xن)=yن{\displaystyle \phi (x_{n})=y_{n}}

و

ϕ(هـأنا)=وπ(أنا){\displaystyle \phi (e_{i})=f_{\pi (i)}}

لاحظ أن

ح≡جي{\displaystyle H\equiv G}إذا وفقط إذاح*≅جي*{\displaystyle H^{*}\cong G^{*}}

وإذا كان التبديل بالإضافة إلى ذلكπ{\displaystyle \pi }يقول أحدهم إن الهوية هيح{\displaystyle H}يساويجي{\displaystyle G}ويكتبح=جي{\displaystyle H=G}لاحظ أنه وفقًا لهذا التعريف للمساواة، فإن الرسوم البيانية ذاتية التناظر:

(ح*)*=ح{\displaystyle \left(H^{*}\right)^{*}=H}

التشاكل الذاتي للمخطط الفائق هو تماثل من مجموعة رؤوس إلى نفسها، أي إعادة تسمية الرؤوس. مجموعة التشاكلات الذاتية للمخطط الفائق H (= ( X , E )) هي زمرة تحت التركيب، تُسمى زمرة التشاكل الذاتي للمخطط الفائق وتُكتب Aut( H ). 

أمثلة

ضع في اعتبارك الرسم البياني الفائقح{\displaystyle H}بحواف

ح={هـ1={أ،ب}،هـ2={ب،ج}،هـ3={ج،د}،هـ4={د،أ}،هـ5={ب،د}،هـ6={أ،ج}}{\displaystyle H=\lbrace e_{1}=\lbrace a,b\rbrace ,e_{2}=\lbrace b,c\rbrace ,e_{3}=\lbrace c,d\rbrace ,e_{4}=\lbrace d,a\rbrace ,e_{5}=\lbrace b,d\rbrace ,e_{6}=\lbrace a,c\rbrace \rbrace }

و

جي={و1={α،β}،و2={β،γ}،و3={γ،دلتا}،و4={دلتا،α}،و5={α،γ}،و6={β،دلتا}}{\displaystyle G=\lbrace f_{1}=\lbrace \alpha ,\beta \rbrace ,f_{2}=\lbrace \beta ,\gamma \rbrace ,f_{3}=\lbrace \gamma ,\delta \rbrace ,f_{4}=\lbrace \delta ,\alpha \rbrace ,f_{5}=\lbrace \alpha ,\gamma \rbrace ,f_{6}=\lbrace \beta ,\delta \rbrace \rbrace }

ثم نقطةح{\displaystyle H}وجي{\displaystyle G}متماثلة (معϕ(أ)=α{\displaystyle \phi (a)=\alpha }إلخ ) ، لكنها ليست متماثلة تمامًا. على سبيل المثال، فيح{\displaystyle H}، رأسأ{\displaystyle a}يلتقي بالحواف 1 و4 و6، بحيث،

هـ1∩هـ4∩هـ6={أ}{\displaystyle e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace }

في الرسم البيانيجي{\displaystyle G}، لا يوجد أي رأس يلتقي بالحواف 1 و 4 و 6:

و1∩و4∩و6=∅{\displaystyle f_{1}\cap f_{4}\cap f_{6}=\varnothing }

في هذا المثال،ح{\displaystyle H}وجي{\displaystyle G}متكافئان،ح≡جي{\displaystyle H\equiv G}والمزدوجات متماثلة بقوة:ح*≅جي*{\displaystyle H^{*}\cong G^{*}}.

التناظر

الرتبةر(ح){\displaystyle r(H)}من الرسم البياني الفائقح{\displaystyle H}يمثل k الحد الأقصى لعدد عناصر أي من حواف الرسم البياني الفائق. إذا كانت جميع الحواف لها نفس العدد k ، يُقال إن الرسم البياني الفائق منتظم أو k-منتظم ، أو يُسمى رسمًا بيانيًا فائقًا من الرتبة k . الرسم البياني هو ببساطة رسم بياني فائق منتظم من الرتبة 2.

درجة الرأس v هي عدد الحواف التي تحتوي عليه. يكون H منتظمًا من الدرجة k إذا كانت درجة كل رأس k .

إن ثنائي الرسم البياني الفائق المنتظم يكون منتظماً والعكس صحيح.

يُقال عن رأسين x و y من H أنهما متناظران إذا وُجد تماثل ذاتي بحيثϕ(x)=y{\displaystyle \phi (x)=y}حافتانهـأنا{\displaystyle e_{i}}وهـج{\displaystyle e_{j}}يُقال إنها متناظرة إذا وُجد تماثل ذاتي بحيثϕ(هـأنا)=هـج{\displaystyle \phi (e_{i})=e_{j}}.

يُقال عن الرسم البياني الفائق أنه متعدٍّ على الرؤوس (أو متناظر الرؤوس ) إذا كانت جميع رؤوسه متناظرة. وبالمثل، يكون الرسم البياني الفائق متعدّيًا على الحواف إذا كانت جميع حوافه متناظرة. إذا كان الرسم البياني الفائق متناظرًا على الحواف والرؤوس معًا، فإنه يُسمى ببساطة متعدّيًا .

بسبب ازدواجية الرسم البياني الفائق، فإن دراسة انتقال الحواف هي نفسها دراسة انتقال الرؤوس.

التقسيمات

تنص نظرية التقسيم التي وضعها إي. داوبر [ 42 ] على أنه بالنسبة للرسم البياني الفائق المتعدي الحوافح=(X،هـ){\displaystyle H=(X,E)}يوجد تقسيم

(X1،X2،⋯،Xك){\displaystyle (X_{1},X_{2},\cdots ,X_{K})}

مجموعة الرؤوسX{\displaystyle X}بحيث يكون الرسم البياني الفرعيحXك{\displaystyle H_{X_{k}}}تم إنشاؤه بواسطةXك{\displaystyle X_{k}}متعدية لكل1≤ك≤ك{\displaystyle 1\leq k\leq K}، وعلى هذا النحو

∑ك=1كر(حXك)=ر(ح){\displaystyle \sum _{k=1}^{K}r\left(H_{X_{k}}\right)=r(H)}

أينر(ح){\displaystyle r(H)}هي رتبة H.

وكنتيجة لذلك، فإن الرسم البياني الفائق المتعدي على الحواف والذي ليس متعديًا على الرؤوس يكون ثنائي اللون.

تُستخدم تقنية تقسيم الرسوم البيانية (وخاصةً تقسيم الرسوم البيانية الفائقة) في العديد من تطبيقات تصميم الدوائر المتكاملة [ 43 ] والحوسبة المتوازية [ 44 ] [ 45 ] [ 46 ] . كما تُعدّ خوارزميات تقسيم الرسوم البيانية الفائقة الفعّالة والقابلة للتوسع مهمةً لمعالجة الرسوم البيانية الفائقة واسعة النطاق في مهام التعلّم الآلي [ 6 ] .

تعميمات إضافية

أحد التعميمات الممكنة للرسم البياني الفائق هو السماح للحواف بالإشارة إلى حواف أخرى. [ 47 ] يوجد نوعان من هذا التعميم. في أحدهما، لا تتكون الحواف من مجموعة رؤوس فحسب، بل قد تحتوي أيضًا على مجموعات جزئية من الرؤوس، ومجموعات جزئية من مجموعات جزئية من الرؤوس، وهكذا إلى ما لا نهاية . في جوهرها، كل حافة هي مجرد عقدة داخلية لشجرة أو رسم بياني موجه غير دوري ، والرؤوس هي العقد الطرفية. وبالتالي، فإن الرسم البياني الفائق هو مجرد مجموعة من الأشجار ذات العقد المشتركة (أي أن عقدة داخلية أو ورقة معينة قد تظهر في عدة أشجار مختلفة). [ 48 ] [ 49 ] على العكس من ذلك، يمكن فهم أي مجموعة من الأشجار على أنها هذا الرسم البياني الفائق المعمم. نظرًا لأن الأشجار تُستخدم على نطاق واسع في علوم الحاسوب والعديد من فروع الرياضيات الأخرى، يمكن القول إن الرسوم البيانية الفائقة تظهر بشكل طبيعي أيضًا. [ 50 ] لذلك، على سبيل المثال، ينشأ هذا التعميم بشكل طبيعي كنموذج لجبر الحدود ؛ تمثل الحواف الحدود ، وتمثل الرؤوس الثوابت أو المتغيرات. [ 51 ]

بالنسبة لمثل هذا الرسم البياني الفائق، توفر عضوية المجموعة ترتيبًا، لكن هذا الترتيب ليس ترتيبًا جزئيًا ولا ترتيبًا مسبقًا ، لأنه ليس متعديًا. [ 52 ] الرسم البياني المقابل لرسم ليفي البياني لهذا التعميم هو رسم بياني موجه غير دوري . [ 53 ] لنأخذ، على سبيل المثال، الرسم البياني الفائق المعمم الذي تكون مجموعة رؤوسه هيV={أ،ب}{\displaystyle V=\{a,b\}}وحوافهاهـ1={أ،ب}{\displaystyle e_{1}=\{a,b\}}وهـ2={أ،هـ1}{\displaystyle e_{2}=\{a,e_{1}\}}ثم، على الرغم منب∈هـ1{\displaystyle b\in e_{1}}وهـ1∈هـ2{\displaystyle e_{1}\in e_{2}}ليس صحيحاً أنب∈هـ2{\displaystyle b\in e_{2}}ومع ذلك، فإن الإغلاق المتعدي لعضوية المجموعة لمثل هذه الرسوم البيانية الفائقة يؤدي إلى ترتيب جزئي ، و"يُسطّح" الرسم البياني الفائق إلى مجموعة مرتبة جزئيًا . [ 54 ]

بدلاً من ذلك، يمكن السماح للحواف بالإشارة إلى حواف أخرى، بغض النظر عن شرط ترتيب الحواف كرسوم بيانية موجهة وغير دورية. [ 47 ] [ 48 ] وهذا يسمح بوجود رسوم بيانية ذات حلقات حواف، والتي لا يشترط أن تحتوي على رؤوس على الإطلاق. على سبيل المثال، لنأخذ الرسم البياني الفائق المعمم المكون من حافتين.هـ1{\displaystyle e_{1}}وهـ2{\displaystyle e_{2}}، وصفر من الرؤوس، بحيثهـ1={هـ2}{\displaystyle e_{1}=\{e_{2}\}}وهـ2={هـ1}{\displaystyle e_{2}=\{e_{1}\}}بما أن هذه الحلقة متكررة بلا حدود، فإن المجموعات التي تمثل الحواف تُخالف بديهية الأساس . [ 48 ] على وجه الخصوص، لا يوجد إغلاق متعدٍ لعضوية المجموعة لمثل هذه الرسوم البيانية الفائقة. على الرغم من أن هذه البنى قد تبدو غريبة في البداية، إلا أنه يمكن فهمها بسهولة من خلال ملاحظة أن التعميم المكافئ لمخطط ليفي الخاص بها لم يعد ثنائي الأجزاء ، بل هو بالأحرى مجرد مخطط موجه عام . [ 55 ]

مصفوفة الوقوع المعممة لمثل هذه المخططات الفائقة هي، بحكم تعريفها، مصفوفة مربعة، رتبتها تساوي العدد الإجمالي للرؤوس والحواف. [ 56 ] وبالتالي، بالنسبة للمثال أعلاه، فإن مصفوفة الوقوع هي ببساطة

[0110]{\displaystyle \left[{\begin{matrix}0&1\\1&0\end{matrix}}\right]}.

انظر أيضاً

ملحوظات

  1. 1 2 فالديفيا، باولا؛ بونو، باولو؛ بليزانت، كاثرين؛ دوفورنو، نيكول؛ فيكيت، جان-دانيال (2020). "تحليل الرسوم البيانية الفائقة الديناميكية باستخدام التصور المتوازي المجمع للرسوم البيانية الفائقة المرتبة" (ملف PDF) . معاملات IEEE في التصور ورسومات الحاسوب . 26 (1 ) . IEEE: 12. doi : 10.1109/TVCG.2019.2933196 . eISSN 1941-0506 . hdl : 11586/518500 . ISSN 1077-2626 . PMID 31398121. S2CID 199518871. مؤرشف (PDF) من الأصل في 2021-01-26 . تم الاطلاع عليه بتاريخ 2020-09-08 .    
  2. ↑ هاوسلر، ديفيد ؛ ويلزل، إيمو (1987)، "شبكات إبسيلون واستعلامات نطاق سيمبلكس"، الهندسة المنفصلة والحسابية ، 2 (2): 127-151 ، doi : 10.1007/BF02187876 ، MR 0884223 .
  3. ↑ بيرل، جوديا (1984). الاستدلالات: استراتيجيات بحث ذكية لحل مشكلات الحاسوب . شركة أديسون-ويسلي للنشر. ص 25. ISBN  978-0-201-05594-8أُرشف من المصدر الأصلي بتاريخ 4 فبراير 2023. تم الاطلاع عليه بتاريخ 12 يونيو 2021 .
  4. ↑ فيج، أورييل؛ كيم، جيونغ هان؛ أوفيك، إران (2006). "شهود على عدم قابلية إرضاء صيغ 3CNF العشوائية الكثيفة". المؤتمر السنوي السابع والأربعون لمؤسسة IEEE حول أسس علوم الحاسوب (FOCS'06) . IEEE. الصفحات 497-508 . doi : 10.1109/FOCS.2006.78 . ISBN  0-7695-2720-5.
  5. 1 2 بيري، سي.؛ فاجين، ر .؛ ماير، د.؛ ياناكاكيس، م. (1983). "حول استصواب مخططات قواعد البيانات غير الدورية" ( ملف PDF) . مجلة ACM . 30 (3): 479-513 . doi : 10.1145/2402.322389 . S2CID 2418740. مؤرشف (ملف PDF) من الأصل بتاريخ 21-04-2021 . تم الاسترجاع بتاريخ 03-01-2021 . 
  6. 1 2 3 هوانغ، جين؛ تشانغ، روي؛ يو، جيفري شو (2015). "تعلم ومعالجة الرسوم البيانية الفائقة القابلة للتوسع". المؤتمر الدولي لهندسة الكهرباء والإلكترونيات لعام 2015 حول استخراج البيانات (ملف PDF) . الصفحات 775-780 . doi : 10.1109/ICDM.2015.33 . ISBN  978-1-4673-9504-5S2CID 5130573. مؤرشف (PDF) من الأصل بتاريخ 26-01-2021 . تم الاطلاع عليه بتاريخ 08-01-2021 . 
  7. ↑ برازيل، م؛ زاخارياسن، م (2015). "أشجار شتاينر في الرسوم البيانية والرسوم البيانية الفائقة" . أشجار الربط الأمثل في المستوى . الخوارزميات والتوافقية. المجلد 29. سبرينغر. الصفحات 301-317 . doi : 10.1007/978-3-319-13915-9_5 . ISBN   978-3-319-13915-9أُرشف من المصدر الأصلي بتاريخ 29 يناير 2021. تم الاطلاع عليه بتاريخ 20 يناير 2021 .
  8. ↑ تشو، دينغيونغ؛ هوانغ، جيايوان؛ شولكوف، برنارد (2006)، "التعلم باستخدام الرسوم البيانية الفائقة: التجميع والتصنيف والتضمين" ، التقدم في أنظمة معالجة المعلومات العصبية ، مطبعة معهد ماساتشوستس للتكنولوجيا، ص 1601-1608 ، ISBN  978-0-262-25691-9تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 22 أكتوبر 2021 ، وتمت معاينته بتاريخ 24 يوليو 2021.
  9. ↑ غوشال، غوراب؛ زلاتيتش، فينكو؛ كالداريلي، غيدو؛ نيومان، مارك إي جيه (2009). "الرسوم البيانية الفائقة العشوائية وتطبيقاتها". مجلة Physical Review E. 79 ( 6) 066118. arXiv : 0903.0419 . Bibcode : 2009PhRvE..79f6118G . doi : 10.1103/PhysRevE.79.066118 . PMID 19658575. S2CID 6391099 .  
  10. ↑ تان، شولونغ؛ بو، جياجون؛ تشين، تشون؛ شو، بين؛ وانغ، كان؛ هي، شياوفي (أكتوبر 2011)، "استخدام معلومات وسائل التواصل الاجتماعي الغنية لتوصية الموسيقى عبر نموذج الرسم البياني الفائق" ، معاملات ACM في الحوسبة متعددة الوسائط والاتصالات والتطبيقات ، 7S (1)، المقالة 22، Bibcode : 2011smma.book..213T ، doi : 10.1145/2037676.2037679 ، S2CID 432036 
  11. ↑ ليو، تشينغشان؛ هوانغ، يوتشي؛ ميتاكساس، ديميتريس ن. (2013)، "الرسم البياني الفائق مع أخذ العينات لاسترجاع الصور"، التعرف على الأنماط ، 44 ( 10-11 ): 2255-2262 ، doi : 10.1016/j.patcog.2010.07.014
  12. ↑ باترو، روب؛ كينغسفورد، كارل (2013)، "التنبؤ بتفاعلات البروتين من خلال استدلال تاريخ الشبكة المقتصد"، المعلوماتية الحيوية ، 29 ( 10-11 ): 237-246 ، doi : 10.1093/bioinformatics/btt224 ، PMC 3694678 ، PMID 23812989  
  13. ↑ غاو، تو؛ وانغ، مينغ؛ تشا، تشنغ-جون؛ شين، جيالي؛ لي، شولونغ؛ وو، شيندونغ (2013)، "التعلم المشترك للصلة المرئية والنصية للبحث الاجتماعي عن الصور القائم على الوسوم" ، معاملات IEEE في معالجة الصور ، 22 (1): 363-376 ، Bibcode : 2013ITIP...22..363Y ، doi : 10.1109/tip.2012.2202676 ، PMID 22692911 ، S2CID 7432373 ، مؤرشف من الأصل في 23-09-2017 ، تم استرجاعه في 22-09-2017  
  14. ↑ تيان، زي؛ هوانغ، تاي هيون؛ كوانغ، روي (2009)، "خوارزمية تعلم قائمة على الرسم البياني الفائق لتصنيف بيانات التعبير الجيني وبيانات التهجين الجينومي المقارن المصفوفي باستخدام المعرفة المسبقة"، المعلوماتية الحيوية ، 25 (21): 2831-2838 ، doi : 10.1093/bioinformatics/btp467 ، PMID 19648139 
  15. ↑ غولدشتاين، أ. (1982). "قاعدة بيانات الرسم البياني الموجه: نموذج لشبكة الهاتف المحلية" . مجلة بيل سيستم التقنية . 61 (9): 2529-2554 . doi : 10.1002/j.1538-7305.1982.tb03439.x . S2CID 11290643 . 
  16. ↑ رانشوس، ستيفن؛ جوسلين، كليف؛ كريلينج، شون؛ نواك، كاثلين؛ ساماتوفا، ناجيزا؛ ويست، كورتيس؛ وينترز، صموئيل (2017). استخراج أنماط التبادل في الرسم البياني الموجه لمعاملات بيتكوين (ملف PDF) . التشفير المالي وأمن البيانات. سبرينغر. doi : 10.1007/978-3-319-70278-0_16 . مؤرشف (ملف PDF) من الأصل بتاريخ 15 يوليو 2021. تم الاطلاع عليه بتاريخ 20 يناير 2021 .
  17. 1 2 أوسييلو، جورجيو؛ لورا، لويجي (2017). "الرسوم البيانية الفائقة الموجهة: مقدمة وخوارزميات أساسية - دراسة استقصائية" . علوم الحاسوب النظرية . 658 : 293-306 . doi : 10.1016/j.tcs.2016.03.016 .
  18. 1 2 غالو، ج.؛ لونغو، ج.؛ بالوتينو، س.؛ نغوين، س. (1993). "الرسوم البيانية الفائقة الموجهة وتطبيقاتها" . الرياضيات التطبيقية المنفصلة . 42 ( 2-3 ): 177-201 . doi : 10.1016/0166-218X(93)90045-P .
  19. ↑ ساندر، ج. (2003)، "تخطيط المخططات الفائقة الموجهة ذات الحواف الفائقة المتعامدة" ، وقائع الندوة الدولية الحادية عشرة حول رسم المخططات (GD 2003) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 2912، سبرينغر، الصفحات 381-386 ، ISBN   978-3-540-24595-7تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 18 يوليو 2011 ، وتمت معاينته بتاريخ 17 مايو 2010..
  20. ↑ إيشباخ، توماس؛ غونتر، فولفغانغ؛ بيكر، بيرند (2006)، "رسم المخططات الفائقة المتعامدة لتحسين الرؤية" (ملف PDF) ، مجلة خوارزميات وتطبيقات الرسوم البيانية ، 10 (2): 141-157 ، doi : 10.7155/jgaa.00122 ، مؤرشف (ملف PDF) من الأصل بتاريخ 18-07-2011 ، تم استرجاعه بتاريخ 17-05-2010.
  21. ↑ ماكينين، إركي (1990)، "كيفية رسم مخطط فائق"، المجلة الدولية للرياضيات الحاسوبية ، 34 (3): 177-185 ، doi : 10.1080/00207169008803875.
  22. ↑ بيرتو، فرانسوا؛ إيدز، بيتر (2001)، "رسم المخططات الفائقة في معيار المجموعات الفرعية"، رسم المخططات ، سلسلة محاضرات في علوم الحاسوب، المجلد 1984، سبرينغر-فيرلاغ، الصفحات 45-76 ، doi : 10.1007/3-540-44541-2_15 ، ISBN   978-3-540-41554-1.
  23. ↑ ناهد أنجم، عرفات؛ بريسان، ستيفان (2017)، "رسم المخططات الفائقة عن طريق التحديد الموجه بالقوة"، تطبيقات قواعد البيانات وأنظمة الخبراء ، سلسلة محاضرات في علوم الحاسوب، المجلد 10439، دار نشر سبرينغر الدولية، الصفحات 387-394 ، doi : 10.1007/978-3-319-64471-4_31 ، ISBN   978-3-319-64470-7.
  24. ^ كوفمان، مايكل. فان كريفيلد، مارك؛ Speckmann، Bettina (2009)، “رسومات التقسيم الفرعي للرسومات الفائقة”، رسم الرسم البياني ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 5417، سبرينغر فيرلاغ، ص 396-407 ، دوى : 10.1007 / 978-3-642-00219-9_39 ، ISBN   978-3-642-00218-2.
  25. ↑ جونسون، ديفيد س .؛ بولاك، HO (2006)، "تسطيح الرسم البياني الفائق وتعقيد رسم مخططات فين"، مجلة نظرية الرسم البياني ، 11 (3): 309-325 ، doi : 10.1002/jgt.3190110306.
  26. ^ بوتشين ، كيفن. فان كريفيلد، مارك؛ ماير، هينك. سبيكمان، بيتينا. Verbeek، Kevin (2010)، “On Planar Supports for Hypergraphs”، رسم الرسم البياني ، ملاحظات المحاضرة في علوم الكمبيوتر، المجلد. 5849، سبرينغر-فيرلاغ، ص 345-356 ، دوى : 10.1007 / 978-3-642-11805-0_33 ، ISBN   978-3-642-11804-3.
  27. ↑ "فيتالي فولوشين: موقع تلوين الرسوم البيانية المختلطة" . spectrum.troy.edu . مؤرشف من الأصل بتاريخ 20 يناير 2022. تم الاطلاع عليه بتاريخ 27 أبريل 2022 .
  28. ↑ فاجين، رونالد (1983-07-01). "درجات عدم الدورية في المخططات الفائقة ومخططات قواعد البيانات العلائقية" . مجلة ACM . 30 (3): 514-550 . doi : 10.1145/2402.322390 . ISSN 0004-5411 . 
  29. 1 2 لوفاسز, لازلو ; بلامر ، دكتوراه في الطب (1986)، نظرية المطابقة ، حوليات الرياضيات المنفصلة، ​​المجلد. 29، شمال هولندا، ISBN  0-444-87916-1، MR 0859549 
  30. ↑ بيرج، كلود (1973). الرسوم البيانية والرسوم البيانية الفائقة . أمستردام: نورث هولاند. ISBN 0-7204-2450-X.
  31. ^ كاتونا، ج . كيرستيد، ها (1999). “سلاسل هاملتون في الرسوم البيانية الفوقية”. مجلة نظرية الرسم البياني . 30 (3): 205–212 . دوى : 10.1002/(SICI)1097-0118(199903)30:3 < 205::AID-JGT5 > 3.0.CO ; 2-يا .
  32. ↑ تشاو، ي. (2016). "التطورات الحديثة في مسائل ديراك للرسوم البيانية الفائقة". الاتجاهات الحديثة في التوافقية . مجلدات IMA في الرياضيات وتطبيقاتها. المجلد 159. الصفحات 145-165 . arXiv : 1508.06170 . doi : 10.1007/978-3-319-24298-9_6 . ISBN   978-3-319-24296-5.
  33. ↑ كوهن، د .؛ أوستوس، د. (2014). "دورات هاميلتون في الرسوم البيانية والرسوم البيانية الفائقة: منظور متطرف" (ملف PDF) . وقائع المؤتمر الدولي للرياضيات : 381-406 . ISBN 978-89-6105-807-0.
  34. ↑ رودل، ف .؛ سزيميريدي، إ .؛ روسينسكي، أ. (2008). "نظرية تقريبية من نوع ديراك للرسوم البيانية الفائقة المنتظمة من الرتبة k". كومبيناتوريكا . 28 (2): 229-260 . doi : 10.1007/s00493-008-2295-z .
  35. ↑ جانزر، ب. (2021). "الرسوم البيانية الفائقة الكبيرة بدون دورات ضيقة". نظرية التوافقية . 1 : ورقة رقم 12، 4. arXiv : 2012.07726 . doi : 10.5070/C61055374 .
  36. ↑ ليتزر، س. (2023). "الرسوم البيانية الفائقة بدون دورات ضيقة". وقائع الجمعية الرياضية الأمريكية . 151 : 455-462 . arXiv : 2106.12082v2 . doi : 10.1090/proc/16043 .
  37. ↑ يو، سي تي؛ أوزسوي أوغلو، إم زد (1979). "خوارزمية لتحديد عضوية استعلام الشجرة في استعلام موزع" (ملف PDF) . وقائع المؤتمر الدولي الثالث لتطبيقات برامج الحاسوب وجمعية مهندسي الكهرباء والإلكترونيات (IEEE)، 1979. الصفحات 306-312 . doi : 10.1109/CMPSAC.1979.762509 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2018-09-02 . تم الاطلاع عليه بتاريخ 2018-09-02 . 
  38. 1 2 غراهام، إم إتش (1979). "حول العلاقة العالمية". تقرير فني . تورنتو، أونتاريو، كندا: جامعة تورنتو.
  39. ↑ أبيتبول، س .؛ هول، ر.ب .؛ فيانو، ف. (1995). أسس قواعد البيانات . أديسون-ويسلي. ISBN 0-201-53771-0.
  40. ↑ تارجان، ر . إي .؛ ياناكاكيس، م. (1984). "خوارزميات بسيطة ذات زمن خطي لاختبار وترية الرسوم البيانية، واختبار عدم دورية الرسوم البيانية الفائقة، وتقليل الرسوم البيانية الفائقة غير الدورية بشكل انتقائي". مجلة SIAM للحوسبة . 13 (3): 566-579 . doi : 10.1137/0213035 .
  41. 1 2 3 فاجين، رونالد (1983). "درجات عدم الدورية للرسوم البيانية الفائقة ومخططات قواعد البيانات العلائقية" . مجلة ACM . 30 (3): 514-550 . doi : 10.1145/2402.322390 . S2CID 597990 . 
  42. ↑ هاراري، ف. (2018) [1969]. نظرية الرسم البياني . مطبعة سي آر سي. ص 172. ISBN  978-0-429-96231-8أُرشف من الأصل بتاريخ 4 فبراير 2023. تم الاطلاع عليه بتاريخ 12 يونيو 2021. نورد فيما يلي نظريةً لإيلين داوبر، والتي تصف نتائجها خصائص الرسوم البيانية المتناظرة خطيًا. لاحظ الملاحظة البديهية، ولكنها مهمة، وهي أن كل رسم بياني متناظر خطيًا يكون منتظمًا خطيًا.
  43. ↑ Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (March 1999), "Multilevel hypergraph partitioning: applications in VLSI domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 7 (1): 69– 79, Bibcode : 1999ITVL....7...69K , CiteSeerX 10.1.1.553.2367 , doi : 10.1109/92.748202 . {{citation}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  44. ↑ هندريكسون، ب.، كولدا، تي جي (2000)، "نماذج تقسيم الرسوم البيانية للحوسبة المتوازية" ، الحوسبة المتوازية (مخطوطة مقدمة)، 26 (12): 1519-1545 ، Bibcode : 2000ParC...26.1519H ، doi : 10.1016/S0167-8191(00)00048-X ، OSTI 4179 ، مؤرشف من الأصل في 2021-01-26 ، تم استرجاعه في 2018-10-13 . {{citation}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  45. ↑ كاتاليوريك، يو في؛ أيكانات، سي. (1995). نموذج الرسم البياني الفائق لرسم خرائط عمليات حساب ضرب المصفوفة المتفرقة المتكررة في المتجه على الحواسيب المتعددة . وقائع المؤتمر الدولي للحوسبة عالية الأداء (HiPC'95).
  46. ↑ Catalyurek, UV; Aykanat, C. (1999), "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems , 10 (7): 673– 693, Bibcode : 1999ITPDS..10..673C , CiteSeerX 10.1.1.67.2498 , doi : 10.1109/71.780863 . 
  47. 1 2 "مقدمة مبسطة في رياضيات المخططات الفائقة - وثائق HyperNetX 2.4.1" . HyperNetX . 2021. تم الاطلاع عليه بتاريخ 19 نوفمبر 2025 .
  48. 1 2 3 ديفلين، كيث (1993). "الفصل 7. نظرية المجموعات غير المؤسسة جيدًا". متعة المجموعات: أساسيات نظرية المجموعات المعاصرة ( الطبعة الثانية). ص 143-184 . doi : 10.1007/978-1-4612-0903-4_7 .  
  49. ↑ فيبستاس، ليناس (24 مارس 2013). "لماذا الرسوم البيانية الفائقة؟" . OpenCog Brainwave . تم الاسترجاع في 19 نوفمبر 2025 .
  50. ^ بيرتشينجر، دانيال. المعلولي، نقولا؛ كلايست، ليندا؛ ميلتزو، تيلمان. ويبر، سيمون (2025). "تعقيد التعرف على الرسوم البيانية الفوقية الهندسية" . الابتكارات في نظرية الرسم البياني (باللغة الفرنسية). 2 : 157– 190. دوى : 10.5802/igt.9 . ISSN 3050-743X . 
  51. ↑ كانين، رافي؛ هوبكروفت، جون. "الفصل 4" (ملف PDF) . 4 الرسوم البيانية العشوائية (ملف PDF) . ص 16. 
  52. ↑ أساري، أمير؛ حسين زاده، نرجس؛ ماكفرسون، دوغالد (2023). "الرسوم البيانية الفائقة المتجانسة للمجموعات" . مجلة الجمعية الرياضية بلندن . 108 (5): 1852-1885 . doi : 10.1112/jlms.12796 . ISSN 1469-7750 . 
  53. ^ بوب ، ميرتن. شلاغ، سيباستيان. شولتز، كريستيان؛ سيماير ، دانيال (2020-10-15). “تقسيم Hypergraph متعدد المستويات الحلقي”. أرخايف : 2002.02962 [ cs.DS ].
  54. ↑ بوشاو، نيل؛ كيتل، ناثان (نوفمبر 2011). "أعداد توران للمسارات المتعددة والغابات متساوية الأجزاء" . التوافقية، الاحتمالات والحوسبة . 20 (6): 837-853 . arXiv : 1106.5904 . doi : 10.1017/S0963548311000460 . ISSN 1469-2163 . 
  55. ↑ بيسانسكي، ت.؛ بوبين، م.؛ ماروسيتش، د.؛ أوربانيك، أ.؛ غراوفاك، أ. (28 يناير 2004). "الأقفاص العشرية والتكوينات المشتقة منها" . الرياضيات المتقطعة . 275 (1): 265-276 . doi : 10.1016/S0012-365X(03)00110-9 . ISSN 0012-365X . 
  56. ↑ باروي، ساميرون (2025). "حول مصفوفات الوقوع للرسوم البيانية الفائقة". الجبر الخطي والمتعدد الخطوط . 73 ( 17): 3861-3880 . arXiv : 2409.16055 . doi : 10.1080/03081087.2025.2568155 .

مراجع

  • PAOHVis : نظام PAOHVis مفتوح المصدر لتصور الرسوم البيانية الفائقة الديناميكية.