ثراكلي

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

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

افترض جون إتش. كونواي بشكل عام أن كل شبكة ثلاثية الأضلاع تحتوي على عدد من الحواف يساوي على الأكثر عدد رؤوسها. ومن المعروف أن عدد الحواف لا يتجاوز قيمة ثابتة مضروبة في عدد الرؤوس.

الثراكل الخطي هو ثراكل مرسوم بحيث تكون حوافه قطعًا مستقيمة. وكما لاحظ بول إردوش ، فإن لكل ثراكل خطي عدد من الحواف يساوي على الأكثر عدد رؤوسه. ويتضمن برهان إردوش دراسة الحالة الخاصة للثراكل الخطي الذي يحتوي على رأس${\displaystyle v}$التي تشكل نقطة نهاية لثلاثة حواف أو أكثر${\displaystyle vw}$،${\displaystyle vx}$، و${\displaystyle vy}$إذا كان ضلعان من هذه الأضلاع ينتميان إلى نفس الخط، فلن يتمكن أي ضلع آخر من عبور كليهما، وبالتالي سيعبر واحد على الأقل من هذه الأضلاع الثلاثة (مثلاً)${\displaystyle vw}$يجب أن تقع ) على خط يفصل بين ضلعين آخرين. ثم،${\displaystyle w}$يجب أن تكون الدرجة الأولى، لأنه لا يوجد قطعة مستقيمة تنتهي عند${\displaystyle w}$، بخلاف${\displaystyle vw}$، يمكن لمس كليهما${\displaystyle vx}$و${\displaystyle vy}$إزالة${\displaystyle w}$و${\displaystyle vw}$ينتج عن ذلك شبكة أصغر، دون تغيير الفرق بين عدد الحواف وعدد الرؤوس. بعد عمليات الإزالة هذه التي تؤدي إلى شبكة يكون لكل رأس فيها جارين على الأكثر، وبحسب نظرية المصافحة، فإن عدد الحواف يكون على الأكثر مساوياً لعدد الرؤوس. ^{[ 2 ]}

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

قدم ميشا بيرلز دليلاً بسيطاً آخر على أن${\displaystyle n}$- تحتوي السلاسل الخطية الرأسية على الأكثر${\displaystyle n}$تستند هذه الخاصية إلى حقيقة أن كل حافة في المضلع الخطي لها نقطة نهاية تشكل عندها زاوية لا تتجاوز 180 درجة، وتكون عندها الحافة الأقرب إلى اتجاه عقارب الساعة ضمن هذه الزاوية. فلو لم تكن لحافة المضلع الخطي هذه الخاصية، لوجدت حافتان متصلتان بنقطتي نهاية متقابلتين للحافة وتقعان على جانبي الخط المار بها، ولا يمكنهما التقاطع. ولكن كل رأس لا يمكن أن يمتلك هذه الخاصية إلا بالنسبة لحافة واحدة، لذا فإن عدد الحواف لا يتجاوز عدد الرؤوس. ^{[ 3 ]}

كما لاحظ إردوش أيضًا، يجب أن تُشكّل مجموعة أزواج النقاط التي تُمثّل قطر مجموعة نقاط خطًا مستقيمًا: لا يمكن أن يكون قطران منفصلين عن بعضهما البعض، لأنه إذا كانا كذلك، فإن نقاط نهايتهما الأربع ستكون لها أزواج على مسافة أبعد من المسافة بين الحافتين المنفصلتين. لهذا السبب، فإن كل مجموعة من${\displaystyle n}$يمكن أن تحتوي النقاط في المستوى على أكثر من${\displaystyle n}$^{أزواج الأقطار، إجابةً على} سؤال طرحه هاينز هوبف وإريكا بانويتز عام 1934. ^{[ 4} ] افترض أندرو فازوني حدودًا لعدد أزواج الأقطار في الأبعاد الأعلى، معممًا بذلك هذه المسألة. ^{[ 2 ]}

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

تشكل أقطار مضلعات راينهارت خطوطًا ثلاثية متساوية في عدد الحواف والرؤوس. ويمكن استخدام تعداد هذه الخطوط الثلاثية لحل مسألة أكبر مضلع صغير ، أي إيجاد...${\displaystyle n}$مضلع ذو مساحة قصوى نسبة إلى قطره. ^{[ 7 ]}

افترض جون إتش. كونواي أن عدد الحواف في أي ثراكل لا يتجاوز عدد الرؤوس. وقد استخدم كونواي نفسه مصطلحي " المسارات" و"النقاط" (للحواف والرؤوس على التوالي ) ، لذا فقد صيغت فرضية كونواي حول الثراكل في الأصل على النحو التالي: كل ثراكل يحتوي على عدد من النقاط يساوي على الأقل عدد المسارات. وقدّم كونواي جائزة قدرها 1000 دولار أمريكي لإثبات هذه الفرضية أو دحضها، وذلك ضمن مجموعة من مسائل الجوائز التي شملت أيضًا مسألة كونواي المتعلقة بالرسوم البيانية الـ 99 ، والحد الأدنى للتباعد بين مجموعات دانزر ، والفائز بعملة سيلفر بعد النقلة 16. ^{[ 8 ]}

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

لقد ثبت أن كل رسم بياني دوري باستثناء الرسم البياني الدوري ذي الأربع رؤوس${\displaystyle C_{4}}$يحتوي على تضمين ثراكيل، مما يدل على أن التخمين دقيق . أي أن هناك ثراكيل لها نفس عدد النقاط وعدد المسارات. في المقابل، أسوأ سيناريو هو أن يكون عدد النقاط ضعف عدد المسارات؛ وهذا أيضًا ممكن.

من المعروف أن فرضية الثراكيل صحيحة بالنسبة للثراكيل المرسومة بطريقة يكون فيها كل ضلع عبارة عن${\displaystyle x}$منحنى رتيب، يتقاطع معه كل خط رأسي مرة واحدة على الأكثر. ^{[ 3 ]}

أثبت لوفاس، باتش، وسيجيدي (1997) أن كل رسم بياني ثنائي الأجزاء قابل للتقسيم هو رسم بياني مستوٍ ، على الرغم من أنه لا يُرسم بطريقة مستوية. ^{[ 1 ]} ونتيجة لذلك، أظهروا أن كل رسم بياني قابل للتقسيم مع${\displaystyle n}$تحتوي الرؤوس على الأكثر${\displaystyle 2n-3}$الحواف. ومنذ ذلك الحين، تم تحسين هذا الحد عدة مرات. ^{[ 10 ] [ 11 ]} الرقم القياسي الحالي هو${\displaystyle 1.393n}$[ ^{12 ]} لكل^​${\displaystyle \varepsilon >0}$توجد خوارزمية محدودة إما أن تحسن الحد إلى${\displaystyle (1+\varepsilon )n}$أو يدحض فرضية ثراكيل. ^{[ 11 ]}

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

يُعدّ تعريف الثراكل المعمم تخفيفًا هامًا للتعريف القياسي للثاركل . في رسم الثراكل المعمم، يُشترط أن يتقاطع أي زوج من الحواف عددًا فرديًا من المرات. ^{[ 13 ]} يمكن أن تكون هذه التقاطعات إما عند رأس مشترك أو عند نقطة تقاطع مناسبة. وهذا يختلف عن الثراكل الصارم، حيث يجب أن يلتقي كل زوج من الحواف مرة واحدة فقط. وبالتالي، فإن كل ثراكل هو أيضًا ثراكل معمّم، ولكن العكس غير صحيح. ومن الأمثلة البارزة على ذلك دورة الرؤوس الأربعة.${\displaystyle C_{4}}$، والتي لا يمكن رسمها كـ thrackle ولكن يمكن رسمها كـ thrackle معمم. ^{[ 11 ]}

تختلف خصائص الثراكلز المعممة اختلافًا كبيرًا عن تلك المفترضة للثراكلات القياسية. بينما يفترض تخمين كونواي أن الثراكل على${\displaystyle n}$يمكن أن تحتوي الرؤوس على أكثر من${\displaystyle n}$يمكن أن تكون الحواف، والشبكات المعممة، أكثر كثافة. باستخدام الاصطلاح الذي${\displaystyle n}$يمثل عدد الرؤوس و${\displaystyle m}$عدد الحواف في الرسم البياني، والحد الأعلى لعدد الحواف في نموذج ثراكل المعمم هو${\displaystyle m\leq 2n-2}$تتمثل إحدى النتائج الرئيسية في هذا المجال في أنه يمكن رسم الرسم البياني ثنائي الأجزاء كـ "ثراكل" معمّم إذا وفقط إذا كان مستويًا. ^{[ 10 ]} أما بالنسبة للرسوم البيانية غير ثنائية الأجزاء، فإن إمكانية رسمها كـ "ثراكل" معمّم ترتبط بمفهوم تضمين التكافؤ على سطح غير قابل للتوجيه. ^{[ 13 ]}

يُعدّ شبه التراكل نوعًا مشابهًا من التراكل المعمم، ولكنه يختلف عنه قليلًا . وهو نوع من التراكل المعمم مع قيد إضافي: فبينما يمكن للحواف غير المتجاورة أن تتقاطع عددًا فرديًا من المرات، لا يُسمح للحواف التي تشترك في رأس واحد بالتقاطع إلا عند ذلك الرأس المشترك، وليس في أي مكان آخر. وهذا يجعل تعريف شبه التراكل أكثر صرامة من تعريف التراكل المعمم، ولكنه يبقى أكثر مرونة من التراكل القياسي. الحد الأقصى لعدد الحواف في شبه التراكل مع${\displaystyle n}$تم تحديد الرؤوس على أنها${\displaystyle {\tfrac {3}{2}}(n-1)}$، وهو حد معروف بأنه الأفضل الممكن لعدد لا نهائي من قيم${\displaystyle n}$[ ^{14 ]​}

• thrackle.org — موقع إلكتروني حول المشكلة