تسمية أنيقة

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

يعود اسم "التسمية الرشيقة" إلى سولومون دبليو غولومب ؛ وقد أطلق ألكسندر روزا على هذا النوع من التسمية في الأصل اسم "التسمية بيتا" في ورقة بحثية عام 1967 حول تسميات الرسوم البيانية. ^{[ 2 ]}

تُعدّ حدسية الشجرة الرشيقة ، أو حدسية رينجل-كوتزيج ، نسبةً إلى غيرهارد رينجل وأنطون كوتزيج ، وتُختصر أحيانًا إلى GTC (لا ينبغي الخلط بينها وبين حدسية كوتزيج حول الرسوم البيانية المتصلة بانتظام)، من أهم المسائل المفتوحة في نظرية الرسوم البيانية . ^{[ 3 ]} تفترض هذه الحدسية أن جميع الأشجار رشيقة. ولا تزال حدسية مفتوحة، على الرغم من إثبات حدسية أخرى ذات صلة، ولكنها أضعف ، تُعرف باسم "حدسية رينجل"، جزئيًا في عام 2020 من قِبل مونتغمري وبوكروفسكي وسوداكوف . ^{[ 4 ] [ 5 ] [ 6 ]}

وصف كوتزيج ذات مرة الجهد المبذول لإثبات الفرضية بأنه "مرض". ^{[ 7 ]}

هناك نسخة أضعف من التسمية الرشيقة وهي التسمية شبه الرشيقة ، حيث يمكن تسمية الرؤوس باستخدام مجموعة فرعية من الأعداد الصحيحة على [0، m + 1] بحيث لا يشترك أي رأسين في تسمية واحدة، ويتم تحديد كل حافة بشكل فريد من خلال الفرق المطلق بين نقاط نهايتها (يقع هذا المقدار على [1، m + 1] ).

ومن الفرضيات الأخرى في نظرية الرسم البياني فرضية روزا ، التي سميت على اسم ألكسندر روزا، والتي تنص على أن جميع الصبارات المثلثة رشيقة أو شبه رشيقة. ^{[ 8 ]}

يُفترض أن الرسم البياني الأنيق ذو الحواف من 0 إلى m يحتوي على ما لا يقل عن${\displaystyle \left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor }$بسبب نتائج المسطرة المتفرقة ، فإن عدد الرؤوس أقل من 213. وقد تم التحقق من هذه الفرضية لجميع الرسوم البيانية التي تحتوي على 213 حافة أو أقل. وهناك فرضية أخرى ذات صلة، وهي أن أصغر رسم بياني أنيق ذي تكافؤ 2m يحتوي على${\displaystyle 3m^{2}}$الحواف، مع توضيح حالة التكافؤ السداسي أدناه.

• في ورقته البحثية الأصلية، أثبت روزا أن الرسم البياني الأويلري الذي يحتوي على عدد من الحواف m ≡ 1 (mod 4) أو m ≡ 2 (mod 4) لا يمكن أن يكون أنيقًا. ^{[ 2 ]}
• كما أثبت روزا في ورقته الأصلية أن الدورة C _n تكون أنيقة إذا وفقط إذا كان n ≡ 0 (mod 4) أو n ≡ 3 (mod 4).
• جميع مخططات المسار ومخططات اليرقة تتميز بالرشاقة. ^{[ 2 ]}
• جميع مخططات جراد البحر التي تتطابق تمامًا تكون أنيقة. ^{[ 9 ]}
• جميع الأشجار التي تحتوي على 27 رأسًا أو أكثر تُعتبر أشجارًا رشيقة؛ وقد أثبت ألدريد وماكاي هذه النتيجة عام 1998 باستخدام برنامج حاسوبي. ^{[ 10 ] [ 11 ]} وتم توسيع نطاق هذه النتيجة لتشمل الأشجار التي تحتوي على 29 رأسًا أو أكثر في أطروحة التخرج لمايكل هورتون. ^{[ 12 ]} وفي عام 2010، أعلن مشروع التحقق من الأشجار الرشيقة، وهو مشروع حوسبة موزعة بقيادة وينجي فانغ، عن توسيع نطاق هذه النتيجة لتشمل الأشجار التي تحتوي على 35 رأسًا. ^{[ 13 ]}
• جميع الرسوم البيانية للعجلات ، والرسوم البيانية للشبكة، والرسوم البيانية للدفة ، والرسوم البيانية للتروس ، والشبكات المستطيلة أنيقة. ^{[ 10 ]}
• جميع المكعبات الفائقة ذات الأبعاد n تتميز بالرشاقة. ^{[ 14 ]}
• جميع الرسوم البيانية المتصلة البسيطة ذات أربعة رؤوس أو أقل تُعتبر رسومًا بيانية أنيقة. أما الرسوم البيانية المتصلة البسيطة غير الأنيقة ذات خمسة رؤوس فهي: الدورة الخماسية ( الخماسي )؛ والرسم البياني الكامل K⁵ _؛ ورسم الفراشة البياني . ^{[ 15 ]}

• تسمية أنيقة الحواف
• قائمة التخمينات

• فيديو من قناة Numberphile حول تخمين الشجرة الرشيقة
• التسمية الأنيقة في عالم الرياضيات

• (ك. إشغي) مقدمة في الرسوم البيانية الرشيقة ، جامعة شريف للتكنولوجيا، 2002.
• (يو إن ديشموخ وفاسانتي إن بهات ناياك)، عائلات جديدة من أشجار الموز الرشيقة - وقائع العلوم الرياضية، 1996 - سبرينغر
• (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
• ( بينغ تشانغ )، نظرة متعددة الأوجه لتلوين الرسوم البيانية، سلسلة سبرينغر الموجزة في الرياضيات، 2016 - سبرينغر