تسمية الرسوم البيانية

يُعرف الرسم البياني بأنه أنيق إذا كانت رؤوسه مُرقمة من 0 إلى | E | ، وهو حجم الرسم البياني، وإذا كان ترقيم الرؤوس هذا يُؤدي إلى ترقيم الحواف من 1 إلى | E | . بالنسبة لأي حافة e ، يكون ترقيمها هو الفرق الموجب بين ترقيمَي الرأسين المتصلين بها . بعبارة أخرى، إذا كانت e متصلة برأسين مُرقمَين i و j ، فإن ترقيم e سيكون | i - j | . بالتالي، يكون الرسم البياني G = ( V , E ) أنيقًا إذا وفقط إذا وُجد تقابل من V إلى {0, ..., | E | } يُؤدي إلى تقابل من E إلى {1, ..., | E | } .

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

يُعرَّف الترقيم المُراعي للحواف على رسم بياني بسيط خالٍ من الحلقات أو الحواف المتعددة، على p رأس و q حافة، بأنه ترقيم للحواف بأعداد صحيحة مميزة في المجموعة {1، ...، q } بحيث يُسند الترقيم على الرؤوس، الناتج عن ترقيم رأس بمجموع الحواف المتصلة به بتردد p، جميع القيم من 0 إلى p - 1 إلى الرؤوس. ويُقال إن الرسم البياني G "مُرعى للحواف" إذا كان يقبل ترقيمًا مُراعيًا للحواف.

تم تقديم تسميات الحواف الأنيقة لأول مرة بواسطة شينغ بينغ لو في عام 1985. ^{[ 7 ]}

الشرط الضروري لكي يكون الرسم البياني أنيق الحواف هو "شرط لو":

${\displaystyle q(q+1)={\frac {p(p-1)}{2}}\mod p.}$

يُعرَّف "التسمية المتناسقة" على الرسم البياني G بأنها دالة أحادية من رؤوس G إلى مجموعة الأعداد الصحيحة بتردد k ، حيث k هو عدد حواف G ، تُنشئ تقابلاً بين حواف G والأعداد بتردد k، وذلك بجعل تسمية الحافة ( x , y ) مجموع تسميات الرأسين x و y (بتردد k ) . الرسم البياني "المتناسق" هو ​​الرسم البياني الذي يتميز بتسمية متناسقة. تُعد الدورات الفردية متناسقة، وكذلك رسوم بيترسن البيانية . يُفترض أن جميع الأشجار متناسقة إذا سُمح بإعادة استخدام تسمية رأس واحد. ^{[ 8 ]} _{يُقدم الرسم البياني} للكتاب _ذي الصفحات السبع K1,7 × K2 مثالاً على رسم بياني غير متناسق. ^{[ 9 ]}

تلوين الرسم البياني هو فئة فرعية من تصنيفات الرسم البياني. يقوم تلوين الرؤوس بتعيين تصنيفات مختلفة للرؤوس المتجاورة، بينما يقوم تلوين الحواف بتعيين تصنيفات مختلفة للحواف المتجاورة. ^{[ 10 ]}

التسمية المحظوظة للرسم البياني G هي تعيين أعداد صحيحة موجبة لرؤوس G بحيث إذا كان S ( v ) يمثل مجموع التسميات على جيران v ، فإن S يمثل تلوينًا لرؤوس G. ويُعرف "العدد المحظوظ" لـ G بأنه أصغر قيمة k بحيث يكون لـ G تسمية محظوظة بالأعداد الصحيحة {1، ...، k }. ^{[ 11 ]}

التسمية المضادة للسحر للرسم البياني G هي تعيين واحد لواحد للأعداد الصحيحة الموجبة {1، ...، | E | } لحواف G بحيث تكون جميع أوزان الرؤوس المستحثة متميزة، حيث يكون وزن الرأس هو مجموع التسميات على جميع الحواف المتصلة به. ^{[ 12 ]}

التسمية السحرية (المسافة) للرسم البياني G هي تعيينٌ فردي للأعداد الصحيحة الموجبة {1، ...، | V | } لرؤوس G بحيث تكون جميع أوزان الرؤوس مساوية لعدد صحيح موجب k . وزن الرأس هو مجموع تسميات جميع الرؤوس المجاورة له. يُسمى هذا الثابت k ، إن وُجد، بالثابت السحري للرسم البياني.