الرسم البياني الوسيطي

في نظرية المخططات ، وهي فرع من فروع الرياضيات ، يُعرف المخطط الوسيط بأنه مخطط غير موجه تكون فيه كل ثلاث رؤوس${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$لها وسيط فريد : رأس${\displaystyle m(a,b,c)}$التي تنتمي إلى أقصر المسارات بين كل زوج من${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$.

لقد دُرِس مفهوم الرسوم البيانية الوسيطة منذ زمن طويل، على سبيل المثال من قِبَل بيركوف وكيس (1947) أو (بشكل أكثر وضوحًا) من قِبَل أفان (1961) ، ولكن يبدو أن أول ورقة بحثية أطلقت عليها اسم "الرسوم البيانية الوسيطة" هي ورقة نيبسكي (1971) . وكما كتب تشونغ وغراهام وساكس، "تنشأ الرسوم البيانية الوسيطة بشكل طبيعي في دراسة المجموعات المرتبة والشبكات التوزيعية المنفصلة ، ​​ولها أدبيات واسعة النطاق". ^{[ 1 ]} في علم الوراثة العرقي ، يُعد رسم بونيمان البياني الذي يُمثل جميع أشجار التطور ذات الحد الأقصى من الاقتصاد رسمًا بيانيًا وسيطًا. ^{[ 2 ]} كما تظهر الرسوم البيانية الوسيطة في نظرية الاختيار الاجتماعي : إذا كانت مجموعة من البدائل لها بنية رسم بياني وسيط، فمن الممكن استنتاج تفضيل الأغلبية بينها بطريقة لا لبس فيها. ^{[ 3 ]}

تم تقديم دراسات استقصائية إضافية للرسوم البيانية الوسيطة بواسطة كلافزار ومولدر (1999) ، وبانديلت وشيبوي (2008) ، وكنوث (2008) .

كل شجرة هي رسم بياني وسيط. ولتوضيح ذلك، لاحظ أنه في الشجرة، يمثل اتحاد أقصر ثلاثة مسارات بين أزواج الرؤوس الثلاثة${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$إما أن يكون مسارًا بحد ذاته، أو شجرة فرعية تتكون من ثلاثة مسارات تلتقي عند عقدة مركزية واحدة من الدرجة الثالثة. إذا كان اتحاد المسارات الثلاثة مسارًا بحد ذاته، فإن الوسيط${\displaystyle m(a,b,c)}$يساوي أحد ما يلي${\displaystyle a}$،${\displaystyle b}$، أو${\displaystyle c}$أيًّا من هذه الرؤوس الثلاثة يقع بين الرأسين الآخرين في المسار. إذا لم تكن الشجرة الفرعية المتكونة من اتحاد المسارات الثلاثة مسارًا، فإن الوسيط بين الرؤوس الثلاثة هو العقدة المركزية من الدرجة الثالثة في الشجرة الفرعية. ^{[ 4 ]}

تُقدم الرسوم البيانية الشبكية أمثلة إضافية على الرسوم البيانية للوسيط . في الرسم البياني الشبكي، إحداثيات الوسيط${\displaystyle m(a,b,c)}$يمكن إيجادها كمتوسط ​​إحداثيات${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$وعلى العكس من ذلك، اتضح أنه في كل رسم بياني وسيط، يمكن تسمية الرؤوس بنقاط في شبكة عددية صحيحة بطريقة تسمح بحساب الوسائط حسب الإحداثيات بهذه الطريقة. ^{[ 5 ]}

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

الرسم البياني البسيط${\displaystyle \kappa (G)}$لرسم بياني غير موجه عشوائي${\displaystyle G}$يحتوي على رأس لكل زمرة (رسم بياني فرعي كامل) من${\displaystyle G}$رأسان من${\displaystyle \kappa (G)}$ترتبط المجموعات المتناظرة بحافة إذا كانت تختلف برأس واحد من رؤوسها.${\displaystyle G}$. الرسم البياني البسيط هو دائمًا رسم بياني وسيط، حيث يمكن تكوين الوسيط لثلاثية معينة من الزمر باستخدام قاعدة الأغلبية لتحديد رؤوس الزمر التي يجب تضمينها. ^{[ 8 ]}

لا يمكن لأي رسم بياني دوري بطول غير أربعة أن يكون رسمًا بيانيًا وسيطًا. كل دورة من هذا النوع لها ثلاثة رؤوس.${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$بحيث تلتف أقصر ثلاثة مسارات حول الدائرة بالكامل دون أن تتقاطع في أي نقطة. بالنسبة لمثل هذه الرؤوس الثلاثة، لا يمكن أن يكون هناك وسيط.

في أي رسم بياني، لكل رأسين${\displaystyle a}$و${\displaystyle b}$، ويُطلق على أقل عدد من الحواف بينهما اسم المسافة بينهما ، ويُرمز لها بـ${\displaystyle d(x,y)}$الفترة الزمنية بين الرؤوس التي تقع على أقصر المسارات بين${\displaystyle a}$و${\displaystyle b}$يُعرَّف بأنه ${\displaystyle I(a,b)=\{\,v\mid d(a,b)=d(a,v)+d(v,b)\,\}.}$

يُعرَّف الرسم البياني الوسيط بالخاصية التي تنص على أنه لكل ثلاثة رؤوس${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$، تتقاطع هذه الفترات في نقطة واحدة:

للجميع${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$،

${\displaystyle |I(a,b)\cap I(a,c)\cap I(b,c)|=1.}$

وبصورة مكافئة، لكل ثلاثة رؤوس${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$يمكن للمرء أن يجد رأسًا${\displaystyle m(a,b,c)}$بحيث تحقق المسافات غير الموزونة في الرسم البياني المتساويات ${\displaystyle {\begin{aligned}d(a,b)&=d{\bigl (}a,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),b{\bigr )},\\d(a,c)&=d{\bigl (}a,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),c{\bigr )},\\d(b,c)&=d{\bigl (}b,m(a,b,c){\bigr )}+d{\bigl (}m(a,b,c),c{\bigr )},\end{aligned}}}$ و${\displaystyle m(a,b,c)}$هو الرأس الوحيد الذي تنطبق عليه هذه المتساويات.

من الممكن أيضًا تعريف الرسوم البيانية الوسيطة على أنها مجموعات حلول مسائل الإرضاء من الدرجة الثانية ، وعلى أنها امتدادات المكعبات الفائقة ، وعلى أنها رسوم بيانية لجبر الوسيط المحدود ، وعلى أنها رسوم بيانية لبونمان لأنظمة هيلي المنقسمة، وعلى أنها رسوم بيانية لـ windex${\displaystyle 2}$انظر الأقسام أدناه.

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

في الشبكة التوزيعية، عملية الوسيط الثلاثية ذاتية الازدواجية لبيركوف ^{[ 9 ]}${\displaystyle m(a,b,c)=(a\land b)\lor (a\land c)\lor (b\land c)=(a\lor b)\land (a\lor c)\land (b\lor c),}$يُحقق بعض البديهيات الأساسية، والتي يشترك فيها مع الوسيط المعتاد للأعداد في النطاق من${\displaystyle 0}$ل${\displaystyle 1}$وبشكل أعم، ينطبق الأمر نفسه على الجبر الوسيطي :

• التكرار :${\displaystyle m(a,a,b)=a}$للجميع${\displaystyle a}$و${\displaystyle b}$.
• خاصية التبديل :${\displaystyle m(a,b,c)=m(a,c,b)=m(b,a,c)=m(b,c,a)=m(c,a,b)=m(c,b,a)}$للجميع${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$.
• خاصية التوزيع :${\displaystyle m(a,m(b,c,d),e)=m(m(a,b,e),c,m(a,d,e))}$للجميع${\displaystyle a}$،${\displaystyle b}$،${\displaystyle c}$،${\displaystyle d}$، و${\displaystyle e}$.
• عناصر الهوية :${\displaystyle m(0,a,1)=a}$للجميع${\displaystyle a}$.

يمكن استبدال قانون التوزيع بقانون التجميع: ^{[ 10 ]}

• الترابط الاجتماعي :${\displaystyle m(x,w,m(y,w,z))=m(m(x,w,y),w,z)}$

يمكن أيضًا استخدام عملية الوسيط لتعريف مفهوم الفترات للشبكات التوزيعية: ^{[ 11 ]}$${\displaystyle I(a,b)=\{x\mid m(a,x,b)=x\}=\{x\mid a\land b\leq x\leq a\lor b\}.}$$

يحتوي الرسم البياني لشبكة توزيعية محدودة على حافة بين الرؤوس${\displaystyle a}$و${\displaystyle b}$حينما${\displaystyle I(a,b)={a,b}}$لكل رأسين${\displaystyle a}$و${\displaystyle b}$في هذا الرسم البياني، الفترة${\displaystyle I(a,b)}$يتكون ما تم تعريفه أعلاه بمصطلحات نظرية الشبكة من الرؤوس الموجودة على أقصر المسارات من${\displaystyle a}$ل${\displaystyle b}$وبالتالي يتطابق مع الفترات النظرية للرسم البياني المحددة سابقًا. لكل ثلاثة عناصر شبكية${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$،${\displaystyle m(a,b,c)}$هو التقاطع الفريد للفترات الثلاث${\displaystyle I(a,b)}$،${\displaystyle I(a,c)}$، و${\displaystyle I(b,c)}$^{[ 12 ]} لذلك ، فإن الرسم البياني لأي شبكة توزيعية محدودة هو رسم بياني وسيط. والعكس صحيح، إذا كان الرسم البياني الوسيط${\displaystyle G}$يحتوي على رأسين${\displaystyle 0}$و${\displaystyle 1}$بحيث يقع كل رأس آخر على أقصر مسار بين الرأسين (أو ما يعادله،${\displaystyle m(0,a,1)=a}$للجميع${\displaystyle a}$)، عندئذٍ يمكننا تعريف شبكة توزيعية يكون فيها${\displaystyle a\land b=m(a,0,b)}$و${\displaystyle a\lor b=m(a,1,b)}$، و${\displaystyle G}$سيكون هذا هو الرسم البياني لهذه الشبكة. ^{[ 13 ]}

يصف دوفوس وريفال (1983) رسوم الشبكات التوزيعية مباشرةً بأنها انكماشات تحافظ على القطر للمكعبات الفائقة. وبشكل أعم، ينتج عن كل رسم بياني وسيط عملية ثلاثية.${\displaystyle m}$تحقق خاصية التكرار، والتبديل، والتوزيع، ولكن ربما بدون عناصر الوحدة في الشبكة التوزيعية. كل عملية ثلاثية على مجموعة منتهية تحقق هذه الخصائص الثلاث (ولكن ليس بالضرورة أن تمتلك${\displaystyle 0}$و${\displaystyle 1}$^{[ 14 ]}​

في الرسم البياني الوسيط، مجموعة${\displaystyle S}$يُقال إن مجموعة الرؤوس محدبة إذا كان لكل رأسين${\displaystyle a}$و${\displaystyle b}$ينتمي إلى${\displaystyle S}$الفترة الزمنية الكاملة${\displaystyle I(a,b)}$هي مجموعة فرعية من${\displaystyle S}$وبالمثل، بالنظر إلى التعريفين المذكورين أعلاه للفترات،${\displaystyle S}$تكون محدبة إذا احتوت على كل أقصر مسار بين رأسين من رؤوسها، أو إذا احتوت على الوسيط لكل مجموعة من ثلاث نقاط على الأقل اثنتان منها من${\displaystyle S}$لاحظ أن تقاطع كل زوج من المجموعات المحدبة هو نفسه محدب. ^{[ 15 ]}

تتمتع المجموعات المحدبة في الرسم البياني الوسيط بخاصية هيلي : إذا${\displaystyle F}$إذا كانت عائلة عشوائية من المجموعات المحدبة المتقاطعة مثنى مثنى، فإن جميع المجموعات في${\displaystyle F}$يتقاطعان في نقطة مشتركة. ^{[ 16 ]} لأنه، إذا${\displaystyle F}$يحتوي على ثلاث مجموعات محدبة فقط${\displaystyle S}$،${\displaystyle T}$، و${\displaystyle U}$فيه، مع${\displaystyle a}$في تقاطع الزوج${\displaystyle S}$و${\displaystyle T}$،${\displaystyle b}$في تقاطع الزوج${\displaystyle T}$و${\displaystyle U}$، و${\displaystyle c}$في تقاطع الزوج${\displaystyle S}$و${\displaystyle U}$ثم كل أقصر مسار من${\displaystyle a}$ل${\displaystyle b}$يجب أن يكمن في الداخل${\displaystyle T}$بسبب التحدب، وبالمثل، يجب أن يقع كل مسار أقصر بين الزوجين الآخرين من الرؤوس ضمن المجموعتين الأخريين؛ ولكن${\displaystyle m(a,b,c)}$ينتمي إلى المسارات بين جميع أزواج الرؤوس الثلاثة، لذا فهو يقع ضمن المجموعات الثلاث، ويشكل جزءًا من تقاطعها المشترك. إذا${\displaystyle F}$إذا احتوت المجموعة على أكثر من ثلاث مجموعات محدبة، فإن النتيجة تتبع بالاستقراء على عدد المجموعات، لأنه يمكن استبدال أي زوج من المجموعات في${\displaystyle F}$عن طريق تقاطعها، باستخدام النتيجة لثلاثيات من المجموعات لإظهار أن العائلة المستبدلة لا تزال متقاطعة بشكل زوجي.

تُعد المجموعات التالية عائلة مهمة بشكل خاص من المجموعات المحدبة في الرسم البياني الوسيط، وتلعب دورًا مشابهًا لدور أنصاف الفضاءات في الفضاء الإقليدي :${\displaystyle W_{uv}=\{\,w\mid d(w,u)<d(w,v)\,\}}$

محدد لكل حافة${\displaystyle uv}$من الرسم البياني. بكلمات أخرى،${\displaystyle W_{uv}}$يتكون من الرؤوس الأقرب إلى${\displaystyle u}$بدلاً من${\displaystyle v}$أو ما يعادلها من رؤوس${\displaystyle w}$بحيث يكون هناك مسار أقصر من${\displaystyle v}$ل${\displaystyle w}$يمر عبر${\displaystyle u}$لإظهار ذلك${\displaystyle W_{uv}}$محدبة، ليكن${\displaystyle w_{1}w_{2}\dots w_{k}}$ليكن أقصر مسار عشوائي يبدأ وينتهي داخل${\displaystyle W_{uv}}$؛ ثم${\displaystyle w_{2}}$يجب أن يكون ذلك ضمن${\displaystyle W_{uv}}$وإلا فإن النقطتين${\displaystyle m_{1}=m(u,w_{1},w_{k})}$و${\displaystyle m_{2}=m(m_{1},w_{2},\dots ,w_{k})}$يمكن إثبات (من خلال النظر في المسافات المحتملة بين الرؤوس) أنها وسائط متميزة لـ${\displaystyle u}$،${\displaystyle w_{1}}$، و${\displaystyle w_{k}}$وهذا يناقض تعريف الرسم البياني الوسيط الذي يشترط أن تكون الوسائط فريدة. وبالتالي، فإن كل رأس متتالٍ على أقصر مسار بين رأسين من${\displaystyle W_{uv}}$كما يقع ضمن${\displaystyle W_{uv}}$، لذا${\displaystyle W_{uv}}$يحتوي على جميع أقصر المسارات بين عقده، وهو أحد تعريفات التحدب.

خاصية Helly للمجموعات${\displaystyle W_{uv}}$يلعب دورًا رئيسيًا في توصيف الرسوم البيانية الوسيطة كحل لحالات الرضا من الدرجة 2، كما هو موضح أدناه.

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

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

${\displaystyle (x_{11}\lor x_{12})\land (x_{21}\lor x_{22})\land \cdots \land (x_{n1}\lor x_{n2})\land \cdots .}$

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

وعلى العكس من ذلك، فإن كل رسم بياني وسيط${\displaystyle G}$يمكن تمثيلها بهذه الطريقة كمجموعة حلول لمسألة إرضاء من الدرجة الثانية. لإيجاد هذا التمثيل، أنشئ مسألة إرضاء من الدرجة الثانية حيث يصف كل متغير اتجاه أحد الحواف في الرسم البياني (تحديد اتجاه للحافة مما يجعل الرسم البياني موجهًا بدلًا من غير موجه)، ويسمح كل قيد لحافتين بمشاركة زوج من الاتجاهات فقط عندما يوجد رأس${\displaystyle v}$بحيث يقع كلا الاتجاهين على طول أقصر المسارات من الرؤوس الأخرى إلى${\displaystyle v}$كل رأس${\displaystyle v}$ل${\displaystyle G}$يتوافق هذا مع حل لمسألة الرضا من الدرجة الثانية حيث تكون جميع الحواف موجهة نحو${\displaystyle v}$يجب أن يأتي كل حل للمسألة من رأس ما${\displaystyle v}$بهذه الطريقة، حيث${\displaystyle v}$هو التقاطع المشترك للمجموعات${\displaystyle W_{uw}}$للحواف الموجهة من${\displaystyle w}$ل${\displaystyle u}$يوجد هذا التقاطع المشترك بسبب خاصية هيلي للمجموعات${\displaystyle W_{uw}}$لذلك، فإن حلول هذه المسألة ذات قابلية الإرضاء من الدرجة الثانية تتطابق تمامًا مع رؤوس${\displaystyle G}$.

تراجع عن رسم بياني${\displaystyle G}$هي خريطة تحافظ على التجاور من${\displaystyle G}$إلى أحد رسومها البيانية الفرعية. ^{[ 18 ]} وبشكل أدق، هو تماثل بياني${\displaystyle \varphi }$من${\displaystyle G}$لنفسه بحيث${\displaystyle \varphi (v)=v}$لكل رأس${\displaystyle v}$في الرسم البياني الفرعي${\displaystyle \varphi (G)}$تُسمى صورة الانكماش صورة انكماش${\displaystyle G}$.

تُعدّ عمليات التراجع أمثلة على الخرائط المترية : المسافة بين${\displaystyle \varphi (v)}$و${\displaystyle \varphi (w)}$لكل${\displaystyle v}$و${\displaystyle w}$، يساوي على الأكثر المسافة بين${\displaystyle v}$و${\displaystyle w}$ويكون متساوياً كلما${\displaystyle v}$و${\displaystyle w}$كلاهما ينتميان إلى${\displaystyle \varphi (G)}$لذلك، يجب أن يكون الانكماش رسمًا بيانيًا فرعيًا متساوي القياس من${\displaystyle G}$المسافات في منطقة التراجع تساوي تلك الموجودة في${\displaystyle G}$.

لو${\displaystyle G}$هو رسم بياني للوسيط، و${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$هي رؤوس ثلاثة عشوائية لـ retract${\displaystyle \varphi (G)}$، ثم${\displaystyle \varphi (m(a,b,c))}$يجب أن يكون وسيطًا لـ${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$وبالتالي يجب أن يساوي${\displaystyle m(a,b,c)}$. لذلك،${\displaystyle \varphi (G)}$يحتوي على وسائط جميع ثلاثيات رؤوسه، ويجب أن يكون أيضًا رسمًا بيانيًا وسيطيًا. بعبارة أخرى، فإن عائلة الرسوم البيانية الوسيطية مغلقة تحت عملية الانكماش. ^{[ 19 ]}

رسم بياني مكعب فائق ، حيث تتوافق الرؤوس مع جميع الاحتمالات الممكنة${\displaystyle k}$المتجهات الثنائية ذات n بت، والتي يكون فيها رأسان متجاورين عندما يختلف المتجهان الثنائيان المقابلان في بت واحد فقط، هي حالة خاصة من${\displaystyle k}$رسم بياني شبكي ذو أبعاد n، وبالتالي فهو رسم بياني وسيطي. الوسيط لثلاثة متجهات ثنائية${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$يمكن حساب ذلك عن طريق حساب دالة الأغلبية لبتات كل موضع بت .${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$بما أن الرسوم البيانية الوسيطة مغلقة تحت الانكماش، وتشمل المكعبات الفائقة، فإن كل انكماش لمكعب فائق هو رسم بياني وسيط.

على النقيض من ذلك، يجب أن يكون كل رسم بياني وسيطي هو انكماش مكعب فائق. ^{[ 20 ]} يمكن ملاحظة ذلك من خلال العلاقة الموضحة أعلاه بين الرسوم البيانية الوسيطية وقابلية الإرضاء من الدرجة الثانية: ليكن${\displaystyle G}$ليكن الرسم البياني حلول مسألة إرضاء من الدرجة الثانية؛ دون فقدان للعمومية، يمكن صياغة هذه المسألة بحيث لا يكون أي متغيرين متساويين دائمًا أو غير متساويين دائمًا في كل حل. عندئذٍ، يشكل فضاء جميع قيم الصواب لمتغيرات هذه المسألة مكعبًا فائقًا. لكل عبارة، مُشكَّلة كفصل بين متغيرين أو مكملاتهما، في مسألة الإرضاء من الدرجة الثانية، يمكن تكوين انكماش للمكعب الفائق حيث تُحوَّل قيم الصواب التي تُخالف هذه العبارة إلى قيم صواب يُحقق فيها كلا المتغيرين العبارة، دون تغيير المتغيرات الأخرى في قيمة الصواب. يُعطي تركيب الانكماشات المُشكَّلة بهذه الطريقة لكل عبارة انكماشًا للمكعب الفائق على فضاء حلول المسألة، وبالتالي يُعطي تمثيلًا لـ${\displaystyle G}$باعتبارها انكماشًا لمكعب فائق. على وجه الخصوص، تُعدّ الرسوم البيانية الوسيطة رسومًا بيانية فرعية متساوية القياس لمكعبات فائقة، وبالتالي فهي مكعبات جزئية . مع ذلك، ليست كل المكعبات الجزئية رسومًا بيانية وسيطة؛ على سبيل المثال، الرسم البياني الدوري ذو الستة رؤوس هو مكعب جزئي ولكنه ليس رسمًا بيانيًا وسيطًا.

كما يصف إمريش وكلافزار (2000) ، يمكن إنشاء تضمين متساوي القياس للرسم البياني الوسيط في مكعب فائق في وقت${\displaystyle O(m\log n)}$، أين${\displaystyle n}$و${\displaystyle m}$يمثل عدد رؤوس وحواف الرسم البياني على التوالي. ^{[ 21 ]}

لقد دُرست مشكلتا اختبار ما إذا كان الرسم البياني رسمًا بيانيًا وسيطيًا، وما إذا كان الرسم البياني خاليًا من المثلثات ، دراسةً وافيةً عندما لاحظ إمريش وكلافزار ومولدر (1999) أنهما، من وجهة نظر معينة، متكافئتان حسابيًا. ^{[ 22 ]} ولذلك، فإن أفضل حد زمني معروف لاختبار ما إذا كان الرسم البياني خاليًا من المثلثات،${\displaystyle O(m^{1.41})}$ينطبق [ ^{23 ] أيضًا على اختبار ما إذا كان} الرسم البياني هو رسم بياني وسيط، وأي تحسين في خوارزميات اختبار الرسم البياني الوسيط سيؤدي أيضًا إلى تحسين في خوارزميات اكتشاف المثلثات في الرسوم البيانية.

في اتجاه واحد، لنفترض أن لدينا رسمًا بيانيًا كمدخل.${\displaystyle G}$ويجب اختبار ما إذا${\displaystyle G}$خالٍ من المثلثات. من${\displaystyle G}$قم بإنشاء رسم بياني جديد${\displaystyle H}$تحتوي كل مجموعة من صفر أو رأس واحد أو رأسين متجاورين على رؤوس من${\displaystyle G}$مجموعتان من هذا القبيل متجاورتان في${\displaystyle H}$عندما يختلفان برأس واحد فقط. وصف مكافئ لـ${\displaystyle H}$وهي تتكون من خلال تقسيم كل حافة من${\displaystyle G}$إلى مسار ذي حافتين، وإضافة رأس جديد متصل بجميع الرؤوس الأصلية لـ${\displaystyle G}$هذا الرسم البياني${\displaystyle H}$هو مكعب جزئي بحكم بنائه، ولكنه رسم بياني وسيط فقط عندما${\displaystyle G}$خالٍ من المثلثات: إذا${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$شكّل مثلثًا في${\displaystyle G}$، ثم${\displaystyle \{a,b\}}$،${\displaystyle \{a,c\}}$، و${\displaystyle \{b,c\}}$ليس لها وسيط في${\displaystyle H}$، لأن الوسيط من هذا القبيل يجب أن يتوافق مع المجموعة${\displaystyle \{a,b,c\}}$، ولكن مجموعات من ثلاثة رؤوس أو أكثر من${\displaystyle G}$لا تشكل رؤوسًا في${\displaystyle H}$. لذلك،${\displaystyle G}$تكون خالية من المثلثات إذا وفقط إذا${\displaystyle H}$هو رسم بياني للوسيط. في حالة أن${\displaystyle G}$خالٍ من المثلثات،${\displaystyle H}$هو رسمه البياني البسيط . خوارزمية لاختبار ما إذا كان${\displaystyle H}$يمكن استخدام الرسم البياني الوسيط، وفقًا لهذا البناء، لاختبار ما إذا كان${\displaystyle G}$وهي خالية من المثلثات. يحافظ هذا التحويل على التعقيد الحسابي للمسألة، بالنسبة لحجمها.${\displaystyle H}$يتناسب مع ذلك${\displaystyle G}$.

يُعدّ الاختزال في الاتجاه المعاكس، من اكتشاف المثلثات إلى اختبار الرسم البياني الوسيط، أكثر تعقيدًا ويعتمد على خوارزمية التعرف على الرسم البياني الوسيط السابقة لهاغاور وإمريش وكلافزار (1999) ، والتي تختبر عدة شروط ضرورية للرسوم البيانية الوسيطة في وقت شبه خطي. تتمثل الخطوة الجديدة الرئيسية في استخدام بحث العرض أولًا لتقسيم رؤوس الرسم البياني إلى مستويات وفقًا لبُعدها عن رأس جذر مُختار عشوائيًا، وتكوين رسم بياني من كل مستوى يكون فيه رأسان متجاورين إذا كان لهما جار مشترك في المستوى السابق، والبحث عن مثلثات في هذه الرسوم البيانية. يجب أن يكون وسيط أي مثلث من هذا القبيل جارًا مشتركًا لرؤوس المثلث الثلاثة؛ إذا لم يكن هذا الجار المشترك موجودًا، فإن الرسم البياني ليس رسمًا بيانيًا وسيطًا. إذا كانت جميع المثلثات التي تم العثور عليها بهذه الطريقة تحتوي على وسائط، ووجدت الخوارزمية السابقة أن الرسم البياني يُلبي جميع الشروط الأخرى لكونه رسمًا بيانيًا وسيطًا، فإنه يجب أن يكون بالفعل رسمًا بيانيًا وسيطًا. لا تتطلب هذه الخوارزمية القدرة على اختبار وجود مثلث فحسب، بل تتطلب أيضًا قائمة بجميع المثلثات في الرسم البياني للمستوى. في الرسوم البيانية العشوائية، قد يتطلب سرد جميع المثلثات أحيانًا${\displaystyle \Omega (m^{3/2})}$الوقت، حيث أن بعض الرسوم البيانية تحتوي على هذا العدد من المثلثات، ومع ذلك يوضح هاجاور وآخرون أن عدد المثلثات الناشئة في الرسوم البيانية للمستوى لاختزالها خطي تقريبًا، مما يسمح باستخدام تقنية Alon et al. السريعة القائمة على ضرب المصفوفات لإيجاد المثلثات.

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

وصف بونيمان (1971) طريقةً لاستنتاج السلالات التطورية المثالية للخصائص الثنائية، إن وُجدت. وتُعمَّم طريقته تلقائيًا لإنشاء رسم بياني وسيط لأي مجموعة من الأنواع والخصائص الثنائية، والذي يُسمى الشبكة الوسيطة أو رسم بونيمان البياني ^{[ 24 ]} ، وهو نوع من الشبكات التطورية . تندمج كل شجرة تطورية ذات اقتصاد أقصى في رسم بونيمان البياني، بمعنى أن حواف الشجرة تتبع مسارات في الرسم البياني، وأن عدد تغيرات قيم الخصائص على حافة الشجرة هو نفسه عددها في المسار المقابل. يكون رسم بونيمان البياني شجرةً إذا وفقط إذا وُجدت سلالة تطورية مثالية؛ ويحدث هذا عندما لا توجد خاصيتان غير متوافقتين تُلاحظ فيهما جميع التوليفات الأربع لقيم الخصائص.

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

يمكن وصف مجموعة من الخصائص الثنائية، بشكل مكافئ، بأنها نظام منقسم ، أي عائلة من المجموعات تتميز بأن المجموعة المكملة لكل مجموعة في هذه العائلة تنتمي إليها أيضًا. يحتوي هذا النظام المنقسم على مجموعة لكل قيمة خاصية، تتكون من الأنواع التي تحمل تلك القيمة. عند تضمين الرؤوس الكامنة، يتمتع النظام المنقسم الناتج بخاصية هيلي : كل عائلة فرعية متقاطعة ثنائياً لها تقاطع مشترك. بمعنى ما، تُوصف الرسوم البيانية الوسيطة بأنها ناتجة عن أنظمة هيلي المنقسمة: الأزواج${\displaystyle (W_{uv},\,W_{vu})}$ تُعرَّف لكل حافة uv من الرسم البياني الوسيط نظام تقسيم هيلي، لذلك إذا طُبِّقَ بناء رسم بياني بونيمان على هذا النظام، فلن تكون هناك حاجة إلى رؤوس كامنة وستكون النتيجة هي نفسها الرسم البياني الأولي. ^{[ 25 ]}

يصف كل من Bandelt et al. (1995) و Bandelt و Macaulay & Richards (2000) تقنيات الحساب اليدوي المبسط لمخطط Buneman، ويستخدمون هذا البناء لتصور العلاقات الجينية البشرية.

• حاصل الضرب الديكارتي لكل رسمين بيانيين للوسيط هو رسم بياني وسيط آخر. يمكن حساب الوسيط في الرسم البياني الناتج عن طريق إيجاد الوسيط في العاملين بشكل مستقل، تمامًا كما يمكن حساب الوسيط في الرسوم البيانية الشبكية عن طريق إيجاد الوسيط في كل بُعد خطي بشكل مستقل.
• يقيس مؤشر ويندكس للرسم البياني مقدار التطلع المسبق اللازم لحل مشكلة ما على النحو الأمثل، حيث يُعطى المرء سلسلة من رؤوس الرسم البياني.${\displaystyle s_{i}}$ويجب أن يجد كناتج سلسلة أخرى من الرؤوس${\displaystyle t_{i}}$تقليل مجموع المسافات d (${\displaystyle s_{i}}$،${\displaystyle t_{i}}$) و د (${\displaystyle t_{i-1}}$،${\displaystyle t_{i}}$الرسوم البيانية الوسيطة هي بالضبط الرسوم البيانية التي يكون فيها مؤشر التداخل 2. في الرسم البياني الوسيط، يكون الخيار الأمثل هو تحديد${\displaystyle t_{i}=m(t_{i-1},s_{i},s_{i+1})}$[ ^{1 ]​}
• تُسمى خاصية وجود وسيط فريد أيضًا بخاصية نقطة شتاينر الفريدة . ^{[ 1 ]} شجرة شتاينر مثالية لثلاثة رؤوس${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$في الرسم البياني الوسيط، يمكن إيجاد المسار على أنه اتحاد أقصر ثلاثة مسارات، من${\displaystyle a}$،${\displaystyle b}$، و${\displaystyle c}$ل${\displaystyle m(a,b,c)}$درس باندلت وبارتيليمي (1984) بشكل أعم مشكلة إيجاد الرأس الذي يقلل مجموع المسافات إلى كل رأس من مجموعة معينة من الرؤوس، وأظهرا أن لها حلاً وحيداً لأي عدد فردي من الرؤوس في الرسم البياني الوسيط. كما أظهرا أن هذا الوسيط لمجموعة${\displaystyle S}$عدد الرؤوس في الرسم البياني الوسيط يحقق معيار كوندورسيه للفائز في الانتخابات : بالمقارنة مع أي رأس آخر، يكون أقرب إلى أغلبية الرؤوس في${\displaystyle S}$.
• كما هو الحال مع المكعبات الجزئية بشكل عام، فإن كل رسم بياني وسيط مع${\displaystyle n}$تحتوي الرؤوس على الأكثر${\displaystyle (n/2)\log _{2}n}$الحواف. ومع ذلك، لا يمكن أن يكون عدد الحواف صغيرًا جدًا: فقد أثبت كلافزار ومولدر وشكريكوفسكي (1998) أنه في كل رسم بياني وسيط، تكون المتباينة${\displaystyle 2n-m-k\leq 2}$يحجز، حيث${\displaystyle m}$هو عدد الحواف و${\displaystyle k}$يمثل بُعد المكعب الفائق الذي يمثل الرسم البياني انعكاسًا له. هذه المتباينة تصبح مساواة إذا وفقط إذا لم يحتوي الرسم البياني الوسيط على أي مكعبات. هذه نتيجة لهوية أخرى للرسوم البيانية الوسيطة: خاصية أويلر.${\displaystyle \sum (-1)^{\dim(Q)}}$يساوي دائمًا واحدًا، حيث يتم حساب المجموع على جميع الرسوم البيانية الفرعية للمكعب الفائق${\displaystyle Q}$من الرسم البياني الوسيط المعطى. ^{[ 26 ]}
• الرسوم البيانية الوسيطة المنتظمة الوحيدة هي المكعبات الفائقة. ^{[ 27 ]}
• كل رسم بياني وسيط هو رسم بياني معياري . الرسوم البيانية المعيارية هي فئة من الرسوم البيانية التي يكون فيها لكل ثلاثية من الرؤوس وسيط، ولكن ليس من الضروري أن تكون الوسائط فريدة. ^{[ 28 ]}

• الرسوم البيانية الوسيطة ، نظام معلومات لتضمين فئات الرسوم البيانية.
• برنامج Network ، برنامج مجاني لتحليل الشبكات التطورية. يقوم برنامج Network بإنشاء أشجار وشبكات تطورية من البيانات الجينية واللغوية وغيرها.
• PhyloMurka ، برنامج مفتوح المصدر لحسابات الشبكة الوسيطة من البيانات البيولوجية.