خوارزمية هافيل-حكيمي

الموسوعة الحرة

خوارزمية هافيل-هاكيمي هي خوارزمية في نظرية المخططات تُستخدم لحل مشكلة تمثيل المخططات . أي أنها تجيب على السؤال التالي: إذا أُعطيت قائمة منتهية من الأعداد الصحيحة غير السالبة مرتبة ترتيبًا تنازليًا، فهل يوجد مخطط بسيط بحيث تكون متتالية درجاته هي هذه القائمة تحديدًا؟ المخطط البسيط لا يحتوي على حواف مزدوجة أو حلقات . [ 1 ] متتالية الدرجات هي قائمة من الأعداد مرتبة ترتيبًا تنازليًا تُشير إلى عدد الحواف المتصلة بكل رأس في المخطط. [ 2 ] إذا وُجد مخطط بسيط لمتتالية الدرجات المُعطاة تحديدًا، تُسمى قائمة الأعداد الصحيحة " مخططًا" . تُنشئ خوارزمية هافيل-هاكيمي حلًا خاصًا إذا وُجد مخطط بسيط لمتتالية الدرجات المُعطاة، أو تُثبت أنه لا يُمكن إيجاد حل إيجابي. يعتمد هذا الإنشاء على خوارزمية تكرارية . نُشرت الخوارزمية بواسطة هافيل (1955) ، ولاحقًا بواسطة هاكيمي (1962) .

الخوارزمية

تعتمد خوارزمية هافيل-حكيمي على النتيجة التالية.

النظرية [ 3 ] ليكن​أ=(s،ت1،...،تs،د1،...،دن){\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}لتكن قائمة منتهية من الأعداد الصحيحة غير السالبة وغير متزايدة .أ′=(ت1-1،...،تs-1،د1،...،دن){\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}لتكن قائمة ثانية منتهية من الأعداد الصحيحة غير السالبة، أعيد ترتيبها لتكون غير متزايدة.أ{\displaystyle A}يكون الرسم بيانيًا إذا وفقط إذا كان مدرجًاأ′{\displaystyle A'}يحتوي على رسومات بيانية.

إذا كانت القائمة المعطاةأ{\displaystyle A}إذا كان الرسم بيانيًا، فسيتم تطبيق النظرية على الأكثرن-1{\displaystyle n-1}تحديد الأوقات في كل خطوة لاحقةأ:=أ′{\displaystyle A:=A'}لاحظ أنه قد يكون من الضروري إعادة فرز هذه القائمة. تنتهي هذه العملية عند فرز القائمة بأكملها.أ′{\displaystyle A'}يتكون من أصفار. ليكنجي{\displaystyle G}ليكن رسمًا بيانيًا بسيطًا مع متتالية الدرجاتأ{\displaystyle A}لنفترض أن الرأسS{\displaystyle S}حاصل على درجة علميةs{\displaystyle s}دع الرؤوستي1،...،تيs{\displaystyle T_{1},...,T_{s}}يحمل كل منها درجة علمية مناسبةت1،...،تs{\displaystyle t_{1},...,t_{s}}دع الرؤوسد1،...،دن{\displaystyle D_{1},...,D_{n}}يحمل كل منها درجة علمية مناسبةد1،...،دن{\displaystyle d_{1},...,d_{n}}في كل خطوة من خطوات الخوارزمية، يتم إنشاء حواف الرسم البياني ذي الرؤوس.تي1،...،تيs{\displaystyle T_{1},...,T_{s}}—أي، إذا كان من الممكن تقليص القائمةأ{\displaystyle A}لأ′{\displaystyle A'}ثم نضيف الحواف{S،تي1}،{S،تي2}،⋯،{S،تيs}{\displaystyle \{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}}عندما تكون القائمةأ{\displaystyle A}لا يمكن اختزالها إلى قائمةأ′{\displaystyle A'}من الأعداد الصحيحة غير السالبة في أي خطوة من هذا النهج، تثبت النظرية أن القائمةأ{\displaystyle A}ليس الأمر مصوراً منذ البداية.

دليل

فيما يلي ملخص يستند إلى برهان خوارزمية هافيل-حكيمي في كتاب Invitation to Combinatorics (شهرياري 2022).

لإثبات أن خوارزمية هافيل-هاكيمي تعمل دائمًا، افترض أنأ′{\displaystyle A'}هو رسم بياني، ويوجد رسم بياني بسيطجي′{\displaystyle G'}مع تسلسل الدرجاتأ′=(ت1-1،...،تs-1،د1،...،دن){\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}ثم نضيف رأسًا جديدًاv{\displaystyle v}بجوارs{\displaystyle s}رؤوس ذات درجاتت1-1،...،تs-1{\displaystyle t_{1}-1,...,t_{s}-1}للحصول على تسلسل الدرجاتأ{\displaystyle A}.

ولإثبات الاتجاه الآخر، افترض أنأ{\displaystyle A}هو رسم بياني، ويوجد رسم بياني بسيطجي{\displaystyle G}مع تسلسل الدرجاتأ=(s،ت1،...،تs،د1،...،دن){\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}والرؤوسS،تي1،...،تيs،د1،...،دن{\displaystyle S,T_{1},...,T_{s},D_{1},...,D_{n}}لا نعرف أيهماs{\displaystyle s}الرؤوس متجاورة معS{\displaystyle S}إذن لدينا حالتان محتملتان.

في الحالة الأولى،S{\displaystyle S}مجاور للرؤوستي1،...،تيs{\displaystyle T_{1},...,T_{s}}فيجي{\displaystyle G}في هذه الحالة، نقوم بإزالةS{\displaystyle S}مع جميع حوافها المتصلة للحصول على تسلسل الدرجاتأ′{\displaystyle A'}.

في الحالة الثانية،S{\displaystyle S}لا يجاور أي رأستيأنا{\displaystyle T_{i}}بالنسبة للبعض1≤أنا≤s{\displaystyle 1\leq i\leq s}فيجي{\displaystyle G}ثم يمكننا تغيير الرسم البيانيجي{\displaystyle G}لهذا السبب.S{\displaystyle S}يقع بجوارتيأنا{\displaystyle T_{i}}مع الحفاظ على نفس تسلسل الدرجاتأ{\displaystyle A}. منذS{\displaystyle S}حاصل على درجة علميةs{\displaystyle s}، الرأسS{\displaystyle S}يجب أن يكون مجاورًا لرأس مادج{\displaystyle D_{j}}فيجي{\displaystyle G}ل1≤ج≤ن{\displaystyle 1\leq j\leq n}لنفترض درجةدج{\displaystyle D_{j}}يكوندج{\displaystyle d_{j}}نحن نعلمتأنا≥دج{\displaystyle t_{i}\geq d_{j}}، كمتتابعة الدرجاتأ{\displaystyle A}مرتبة ترتيباً تنازلياً.

منذتأنا≥دج{\displaystyle t_{i}\geq d_{j}}لدينا احتمالان: إماتأنا=دج{\displaystyle t_{i}=d_{j}}، أوتأنا>دج{\displaystyle t_{i}>d_{j}}. لو تأنا=دج{\displaystyle t_{i}=d_{j}}ثم عن طريق تبديل أماكن الرؤوستيأنا{\displaystyle T_{i}}ودج{\displaystyle D_{j}}يمكننا التعديلجي{\displaystyle G}لهذا السبب.S{\displaystyle S}يقع بجوارتيأنا{\displaystyle T_{i}}بدلاً مندج.{\displaystyle D_{j}.}لوتأنا>دج{\displaystyle t_{i}>d_{j}}ثم بما أنتيأنا{\displaystyle T_{i}}تجاور رؤوسًا أكثر مندج{\displaystyle D_{j}}، لنفترض رأسًا آخردبليو{\displaystyle W}أن يكون مجاورًا لـتيأنا{\displaystyle T_{i}}وليسدج{\displaystyle D_{j}}ثم يمكننا التعديلجي{\displaystyle G}عن طريق إزالة الحواف{S،دج}{\displaystyle \left\{S,D_{j}\right\}}و{تيأنا،دبليو}{\displaystyle \left\{T_{i},W\right\}}وإضافة الحواف{S،تيأنا}{\displaystyle \left\{S,T_{i}\right\}}و{دبليو،دج}{\displaystyle \left\{W,D_{j}\right\}}يحافظ هذا التعديل على تسلسل الدرجات لـجي{\displaystyle G}لكن الرأسS{\displaystyle S}أصبح الآن مجاوراً لـتيأنا{\displaystyle T_{i}}بدلاً مندج{\displaystyle D_{j}}وبهذه الطريقة، أي رأس غير متصل بـS{\displaystyle S}ويمكن تعديلها وفقًا لذلك بحيثS{\displaystyle S}يقع بجوارتيأنا{\displaystyle T_{i}}مع الحفاظ على تسلسل الدرجات الأصليأ{\displaystyle A}لجي{\displaystyle G}وبالتالي، فإن أي رأس غير متصل بـS{\displaystyle S}يمكن توصيله بـS{\displaystyle S}باستخدام الطريقة المذكورة أعلاه، ثم نعود إلى الحالة الأولى مرة أخرى، والتي من خلالها يمكننا الحصول على متتالية الدرجاتأ′{\displaystyle A'}. لذلك،أ{\displaystyle A}يكون الرسم بيانيًا إذا وفقط إذاأ′{\displaystyle A'}وهو أيضاً يتضمن رسومات بيانية.

أمثلة

يترك6،3،3،3،3،2،2،2،2،1،1{\displaystyle 6,3,3,3,3,2,2,2,2,1,1}لتكن متتالية غير متزايدة ذات درجة منتهية من الأعداد الصحيحة غير السالبة. لاختبار ما إذا كانت هذه المتتالية بيانية، نطبق خوارزمية هافيل-حكيمي:

أولاً، نقوم بإزالة الرأس ذي الدرجة الأعلى - في هذه الحالة،6{\displaystyle 6}— وجميع جوانب الحادثة للحصول على2،2،2،2،1،1،2،2،1،1{\displaystyle 2,2,2,2,1,1,2,2,1,1}(بافتراض أن الرأس ذو الدرجة الأعلى مجاور لـ6{\displaystyle 6}الرؤوس ذات الدرجة الأعلى التالية). نعيد ترتيب هذا التسلسل بترتيب تنازلي للحصول على2،2،2،2،2،2،1،1،1،1{\displaystyle 2,2,2,2,2,2,1,1,1,1}نكرر العملية، ونزيل الرأس ذو الدرجة الأعلى التالية لنحصل على1،1،2،2،2،1،1،1،1{\displaystyle 1,1,2,2,2,1,1,1,1}وإعادة الترتيب للحصول على2،2،2،1،1،1،1،1،1{\displaystyle 2,2,2,1,1,1,1,1,1}نواصل عملية الإزالة هذه للحصول على1،1،1،1،1،1،1،1{\displaystyle 1,1,1,1,1,1,1,1}، وثم0،0،0،0،0،0،0،0{\displaystyle 0,0,0,0,0,0,0,0}هذا التسلسل واضحٌ بيانيًا، لأنه الرسم البياني البسيط لـ8{\displaystyle 8}رؤوس معزولة.

لإظهار مثال على متتالية غير بيانية، لنفترض6،5،5،4،3،2،1{\displaystyle 6,5,5,4,3,2,1}لتكن متتالية غير متزايدة ذات درجة منتهية من الأعداد الصحيحة غير السالبة. بتطبيق الخوارزمية، نقوم أولاً بإزالة الدرجة6{\displaystyle 6}الرأس وجميع حوافه المتصلة به للحصول على4،4،3،2،1،0{\displaystyle 4,4,3,2,1,0}نعلم بالفعل أن هذا التسلسل الدرجاتي ليس بيانيًا، لأنه يدعي أنه يحتوي على6{\displaystyle 6}الرؤوس التي لا يجاور أحد رؤوسها أيًا من الرؤوس الأخرى؛ وبالتالي، فإن أعلى درجة للرؤوس الأخرى هي4{\displaystyle 4}هذا يعني أن اثنين من الرؤوس متصلان بجميع الرؤوس الأخرى باستثناء الرأس المنعزل، لذا يجب أن تكون الدرجة الدنيا لكل رأس هي2{\displaystyle 2}ومع ذلك، يدعي التسلسل أن له رأسًا بدرجة1{\displaystyle 1}وبالتالي، فإن التسلسل ليس رسومياً.

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

انظر أيضاً

ملحوظات

  1. ↑ من شهرياري (2022، ص 48): " التعريف 2.17 (الرسوم البيانية والرسوم البيانية الفرعية). الرسم البياني البسيط (أو الرسم البياني فقط ) G هو زوج من المجموعات ( V، E ) حيث V هي مجموعة غير فارغة تُسمى مجموعة رؤوس G ، و E هي مجموعة (قد تكون فارغة) من أزواج غير مرتبة من العناصر المختلفة في V. تُسمى المجموعة E مجموعة حواف G. إذا كان عدد رؤوس G محدودًا، فإن G هو رسم بياني محدود (أو رسم بياني بسيط محدود )."
  2. ↑ من شهرياري (2022، ص 355): " التعريف 10.6 (متتالية درجات الرسم البياني؛ المتتاليات البيانية). متتالية درجات الرسم البياني هي قائمة درجات رؤوسه بترتيب تنازلي. تُسمى متتالية الأعداد الصحيحة غير السالبة تنازلية بيانية ، إذا وُجد رسم بياني بسيط تكون متتالية درجاته هي تلك المتتالية تحديدًا."
  3. ↑ ويست (2001)، النظرية 1.3.31.

مراجع