رسم بياني غير متماثل

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
الرسوم البيانية الثمانية غير المتماثلة ذات 6 رؤوس
الرسم البياني فروشت ، وهو أحد أصغر خمسة رسوم بيانية مكعبة غير متماثلة .

في نظرية الرسم البياني ، وهي فرع من فروع الرياضيات ، يُطلق على الرسم البياني غير الموجه اسم الرسم البياني غير المتماثل إذا لم يكن لديه أي تناظرات غير تافهة .

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

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

أمثلة

أصغر الرسوم البيانية غير التافهة غير المتناظرة تتكون من 6 رؤوس. [ 1 ] أصغر الرسوم البيانية المنتظمة غير المتناظرة تتكون من 10 رؤوس؛ وتوجد رسوم بيانية غير متناظرة ذات 10 رؤوس ، وهي منتظمة من الدرجة 4 ومنتظمة من الدرجة 5. [ 2 ] [ 3 ] أحد أصغر خمسة رسوم بيانية مكعبة غير متناظرة [ 4 ] هو رسم فروشت ذو الاثني عشر رأسًا، والذي اكتُشف عام 1939. [ 5 ] وفقًا لنسخة مُحسّنة من نظرية فروشت ، يوجد عدد لا نهائي من الرسوم البيانية المكعبة غير المتناظرة.

ملكيات

تُعتبر فئة الرسوم البيانية غير المتناظرة مغلقة تحت نظام المكملات : يكون الرسم البياني G غير متناظر إذا وفقط إذا كان مكمله كذلك. [ 1 ] يمكن جعل أي رسم بياني غير متناظر ذي n رأس متناظرًا بإضافة وإزالة ما مجموعه n /2  +  o( n ) من الحواف على الأكثر. [ 1 ]

الرسوم البيانية العشوائية

تتناقص نسبة الرسوم البيانية ذات n رأسًا والتي تمتلك تماثلًا ذاتيًا غير تافه مع ازدياد n ، وهو ما يُعبَّر عنه بشكل غير رسمي بعبارة " جميع الرسوم البيانية المنتهية تقريبًا غير متناظرة". في المقابل، وبشكل غير رسمي أيضًا، "جميع الرسوم البيانية اللانهائية تقريبًا تمتلك تناظرات غير تافهة". وبشكل أكثر تحديدًا، فإن الرسوم البيانية العشوائية اللانهائية القابلة للعد في نموذج إردوش-ريني متماثلة ، باحتمالية 1 ، مع الرسم البياني رادو عالي التناظر . [ 1 ]

الأشجار

أصغر شجرة غير متناظرة تتكون من سبعة رؤوس: تتألف من ثلاثة مسارات بأطوال 1 و2 و3، متصلة بنقطة نهاية مشتركة. [ 6 ] على عكس حالة الرسوم البيانية، فإن جميع الأشجار تقريبًا متناظرة. على وجه الخصوص، إذا تم اختيار شجرة عشوائيًا وبشكل منتظم من بين جميع الأشجار على n عقدة مُصنفة، فإن احتمالًا يقترب من 1 مع ازدياد n ، سيحتوي على ورقتين متجاورتين لنفس العقدة، وستكون هناك تناظرات تتبادل هاتين الورقتين. [ 1 ]

مراجع

  1. 1 2 3 4 5 إردوس، ب . Rényi، A. (1963)، “الرسوم البيانية غير المتماثلة”، Acta Mathematica Hungarica ، 14 (3): 295–315 ، دوى : 10.1007 / BF01895716.
  2. ^ بارون، ج. Imrich، W. (1969)، “Asymmetrische reguläre Graphen”، Acta Mathematica Academiae Scientiarum Hungaricae , 20 ( 1– 2): 135– 142، دوى : 10.1007 / BF01894574 ، السيد 0238726 .
  3. ^ جويرتز ، آلان. هيل، أنتوني. Quintas، Louis V. (1969)، “الحد الأدنى لعدد النقاط للرسوم البيانية غير المتماثلة المنتظمة”، Universidad Técnica Federico Santa Maria. ساينتيا ، 138 : 103-111 ، م.ر 0266818 .
  4. ↑ بوسماكر، إف سي؛ كوبيليتش، إس؛ تسفيتكوفيتش، دي إم؛ سيدل، جيه جيه (1976)، دراسة حاسوبية للرسوم البيانية المكعبة ، تقرير جامعة آيندهوفن للتكنولوجيا، المجلد 76-WSK-01، قسم الرياضيات وعلوم الحاسوب، جامعة آيندهوفن للتكنولوجيا 
  5. ^ فروشت، ر. (1939)، “Herstellung von Graphen mit vorgegebener abstrakter Gruppe.” ، Compositio Mathematica (باللغة الألمانية)، 6 : 239–250 ، ISSN 0010-437X ، Zbl 0020.07804  .
  6. ↑ كوينتاس، لويس ف. (1967)، "القيم القصوى المتعلقة بالرسوم البيانية غير المتناظرة"، مجلة نظرية التوافيق ، 3 (1): 57-82 ، doi : 10.1016/S0021-9800(67)80018-8.