عرض نطاق الرسم البياني

في نظرية المخططات ، يمكن تصور مشكلة عرض نطاق المخطط على أنها وضع رؤوس مخطط معين في مواقع عددية صحيحة مميزة على طول خط الأعداد بحيث يتم تقليل طول أطول حافة. ​​يُطلق على هذا الوضع اسم ترتيب المخطط الخطي ، أو تخطيط المخطط الخطي ، أو وضع المخطط الخطي . ^{[ 1 ]} ويمكن صياغته رسميًا على أنه تسمية${\displaystyle n}$الرؤوس${\displaystyle v_{i}}$رسم بياني${\displaystyle G}$بأعداد صحيحة مميزة${\displaystyle f(v_{i})}$بحيث تكون الكمية${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$يتم تقليلها إلى الحد الأدنى، حيث${\displaystyle E}$هي مجموعة الحواف لـ${\displaystyle G}$[ ^{2 ]​}

تُعدّ مشكلة عرض النطاق الترددي للرسم البياني الموزون تعميمًا يتم فيه تعيين أوزان للحواف.${\displaystyle w_{ij}}$ودالة التكلفة التي يجب تقليلها هي حاصل ضرب الوزن في الطول،${\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$.

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

بالنسبة للعديد من عائلات الرسوم البيانية، فإن عرض النطاق الترددي${\displaystyle \varphi (G)}$يتم تحديدها بصيغة صريحة.

عرض النطاق الترددي لمخطط المسار${\displaystyle P_{n}}$على${\displaystyle n}$عدد الرؤوس يساوي  1، وعرض النطاق الترددي للرسم البياني الكامل${\displaystyle K_{m}}$يكون${\displaystyle \varphi (K_{n})=n-1}$للحصول على الرسم البياني الثنائي الكامل${\displaystyle K_{m,n}}$، $${\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n,}$$بافتراض${\displaystyle m\geq n\geq 1}$. كحالة خاصة من هذه الصيغة، الرسم البياني النجمي${\displaystyle S_{k}=K_{k,1}}$على${\displaystyle k+1}$تتمتع الرؤوس بعرض نطاق ترددي${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$[ ^{4 ]​}

بالنسبة للرسم البياني المكعب الفائق${\displaystyle Q_{n}}$على${\displaystyle 2^{n}}$الرؤوس، عرض النطاق الترددي هو ^{[ 5 ]}$${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$$

عرض النطاق الترددي لـ${\displaystyle m\times n}$رسم بياني شبكي مربع${\displaystyle P_{m}\times P_{n}}$أي، حاصل الضرب الديكارتي لمخططين مساريين على${\displaystyle m}$و${\displaystyle n}$الرؤوس، يساوي${\displaystyle \min\{m,n\}}$[ ^{6 ]​}

يمكن تحديد عرض نطاق الرسم البياني بدلالة العديد من معلمات الرسم البياني الأخرى. على سبيل المثال، إذا رمزنا للعدد اللوني للرسم البياني G بالرمز χ( G ) ،

${\displaystyle \varphi (G)\geq \chi (G)-1;}$

إذا رمزنا بـ diam( G ) إلى قطر G ، فإن المتباينات التالية صحيحة: ^{[ 2 ]}

${\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}$

أين${\displaystyle n}$يمثل عدد الرؤوس في${\displaystyle G}$.

إذا كان للرسم البياني G عرض نطاق k ، فإن عرض مساره لا يتجاوز k ، ^{[ 3 ]} وعمق شجرته لا يتجاوز k  log( n / k ). ^{[ 7 ]} في المقابل، وكما ذُكر في القسم السابق، فإن الرسم البياني النجمي S _{_k} ، وهو مثال بسيط جدًا من الناحية الهيكلية للشجرة ، يتمتع بعرض نطاق كبير نسبيًا. لاحظ أن عرض مسار S _{_k} هو  1، وعمق شجرته هو  2.

بعض عائلات الرسوم البيانية ذات الدرجة المحدودة لها عرض نطاق فرعي خطي: ​​إذا كانت T شجرة ذات درجة قصوى لا تتجاوز ∆، فإن ^{[ 8 ]}

${\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}$

وبشكل أكثر عمومية، بالنسبة للرسوم البيانية المستوية ذات الدرجة القصوى المحدودة على الأكثر ∆ ، فإن حدًا مشابهًا ينطبق: ^{[ 9 ]}

${\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}$

يُعد كل من الإصدارين غير الموزون والموزون حالتين خاصتين من مسألة تخصيص عنق الزجاجة التربيعية . تُصنف مسألة عرض النطاق الترددي ضمن المسائل الصعبة حسابيًا (NP-hard) ، حتى في بعض الحالات الخاصة. ^{[ 10 ]} فيما يتعلق بوجود خوارزميات تقريب فعالة ، من المعروف أن تقريب عرض النطاق الترددي ضمن أي قيمة ثابتة يُعد مسألة صعبة حسابيًا (NP-hard)، ويظل هذا صحيحًا حتى عندما تقتصر الرسوم البيانية المدخلة على أشجار اليرقة ذات طول شعر أقصى يساوي 2. ^{[ 11 ]} بالنسبة للرسوم البيانية العشوائية ذات${\displaystyle n}$أفضل نسبة تقريب معروفة للرؤوس هي${\displaystyle O(\log ^{3}n{\sqrt {\log \log n}})}$باستخدام البرمجة شبه المحددة . ^{[ 12 ]} في حالة الرسوم البيانية الكثيفة، توجد خوارزمية تقريبية من الدرجة الثالثة. ^{[ 13 ]} من ناحية أخرى، توجد عدة حالات خاصة قابلة للحل في وقت متعدد الحدود. ^{[ 1 ]} خوارزمية كوثيل-مكي هي خوارزمية استدلالية للحصول على تخطيطات خطية للرسوم البيانية ذات نطاق ترددي منخفض . تم اقتراح خوارزمية متعددة المستويات سريعة لحساب نطاق ترددي للرسوم البيانية. ^{[ 14 ]}

ينبع الاهتمام بهذه المشكلة من بعض مجالات التطبيق.

أحد المجالات هو معالجة المصفوفات المتفرقة / مصفوفات النطاق ، ويمكن تطبيق الخوارزميات العامة من هذا المجال، مثل خوارزمية Cuthill-McKee ، لإيجاد حلول تقريبية لمشكلة عرض النطاق الترددي للرسم البياني.

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

• Cutwidth و pathwidth ، وهما مشكلتان مختلفتان من مشاكل التحسين NP-complete تتضمنان تخطيطات خطية للرسوم البيانية.

• مشكلة الحد الأدنى لعرض النطاق الترددي ، في: بييرلويجي كريشينزي وفيجو كان (محرران)، مجموعة من مسائل التحسين NP. تم الاطلاع عليه في 26 مايو 2010.