مخطط هاس

في نظرية الترتيب ، يُعد مخطط هاس ( بالإنجليزية : Hasse diagram ) نوعًا من المخططات الرياضية المستخدمة لتمثيل مجموعة مرتبة جزئيًا منتهية ، وذلك على شكل رسم لاختزالها المتعدي . وبشكل أكثر تحديدًا، بالنسبة لمجموعة مرتبة جزئيًا${\displaystyle (S,\leq )}$يمثل واحد كل عنصر من عناصر${\displaystyle S}$كرأس في المستوى ويرسم قطعة مستقيمة أو منحنى يتجه لأعلى من أحد الرؤوس${\displaystyle x}$إلى رأس آخر${\displaystyle y}$حينما${\displaystyle y}$أغطية${\displaystyle x}$(أي، كلما${\displaystyle x\neq y}$،${\displaystyle x\leq y}$ولا يوجد${\displaystyle z}$متميز عن${\displaystyle x}$و${\displaystyle y}$مع${\displaystyle x\leq z\leq y}$قد تتقاطع هذه المنحنيات، ولكن يجب ألا تلامس أي رؤوس أخرى غير نهاياتها. يحدد هذا الرسم التخطيطي، مع تسمية الرؤوس، ترتيبه الجزئي بشكل فريد.

سُميت مخططات هاس نسبةً إلى هيلموت هاس (1898-1979)؛ ووفقًا لغاريت بيركوف ، سُميت كذلك نظرًا لاستخدام هاس الفعال لها. ^{[ 1 ]} مع ذلك، لم يكن هاس أول من استخدم هذه المخططات. يوجد مثال أقدم من هاس في عمل لهنري غوستاف فوغت عام 1895. ^{[ 2 ] [ 3 ]} على الرغم من أن مخططات هاس صُممت في الأصل كتقنية لرسم المجموعات المرتبة جزئيًا يدويًا، فقد تم إنشاؤها مؤخرًا تلقائيًا باستخدام تقنيات الرسم البياني . ^{[ 4 ]}

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

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

يوضح المثال التالي هذه المسألة. لنفترض مجموعة القوى لمجموعة مكونة من 4 عناصر مرتبة حسب الاحتواء.${\displaystyle \subseteq }$فيما يلي أربعة مخططات هاس مختلفة لهذا الترتيب الجزئي. تحتوي كل مجموعة فرعية على عقدة تحمل ترميزًا ثنائيًا يوضح ما إذا كان عنصر معين موجودًا في المجموعة الفرعية (1) أم لا (0):

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

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

• إذا كان الترتيب الجزئي المراد رسمه عبارة عن شبكة ، فيمكن رسمه بدون تقاطعات إذا وفقط إذا كان بُعد ترتيبه لا يتجاوز اثنين. ^{[ 6 ]} في هذه الحالة، يمكن إيجاد رسم بدون تقاطعات عن طريق اشتقاق الإحداثيات الديكارتية للعناصر من مواقعها في الترتيبين الخطيين اللذين يحققان بُعد الترتيب، ثم تدوير الرسم عكس اتجاه عقارب الساعة بزاوية 45 درجة.
• إذا كان الترتيب الجزئي يحتوي على عنصر أدنى واحد على الأكثر ، أو يحتوي على عنصر أقصى واحد على الأكثر ، فإنه يمكن اختبار ما إذا كان يحتوي على مخطط هاس غير متقاطع في وقت خطي . ^{[ 7 ]}
• يُعدّ تحديد ما إذا كان بالإمكان رسم ترتيب جزئي ذي مصادر ومصارف متعددة كمخطط هاس خالٍ من التقاطعات مسألةً من فئة NP-complete . ^{[ 8 ]} ومع ذلك، فإن إيجاد مخطط هاس خالٍ من التقاطعات يصبح قابلاً للحل باستخدام معلمات ثابتة عند تحديدها بعدد نقاط التمفصل والمكونات ثلاثية الاتصال للاختزال المتعدي للترتيب الجزئي. ^{[ 9 ]}
• إذا تم تحديد إحداثيات y لعناصر ترتيب جزئي، فإنه يمكن إيجاد مخطط هاس خالٍ من التقاطعات يحترم هذه الإحداثيات في زمن خطي، إن وُجد مثل هذا المخطط. ^{[ 10 ]} على وجه الخصوص، إذا كانت مجموعة الترتيب الجزئي المدخلة مجموعة ترتيب جزئي متدرجة ، فمن الممكن تحديد ما إذا كان هناك مخطط هاس خالٍ من التقاطعات يكون فيه ارتفاع كل رأس متناسبًا مع رتبته، وذلك في زمن خطي.

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

• الوسائط ذات الصلة على ويكيميديا ​​كومنز:
  • مخطط هاس (معرض الصور)
  • مخططات هاس (الفئة)
• وايسستين، إريك دبليو ، “مخطط هاس” ، MathWorld