مركز الرسم البياني: هل تكفي أعلى درجة؟

الخلاصة السريعة

لا؛ أعلى درجة لا تكفي لتحديد المركز. في الرسم AB AC AD AE AF FG GH، يكون F المركز الوحيد رغم أن درجته2، بينما درجة A تساوي5. أبعد مسافة عن F تساوي2، وعن A تساوي3؛ نصف قطر الرسم2 وقطره4. الاختيار يتبع أبعد المسافات الأقصر، لا عدد الجيران وحده.

• مركز الرسم هو مجموعة الرؤوس التي تساوي أبعد مسافة عنها نصف قطر الرسم. [1] قد تضم المجموعة رأسًا واحدًا أو أكثر؛ نحددها من المسافات، لا من مواضع الدوائر في الصورة. في الرسم المتصل، أبعد مسافة عن رأس هي أكبر مسافة منه إلى أي رأس آخر؛ أصغر هذه القيم هو نصف القطر، وأكبرها هو القطر. [2] سنعد الحواف في أقصر طريق، بلا أوزان أو اتجاهات.
• نثبت ثمانية رؤوس بالحواف AB AC AD AE AF FG GH. A درجته5 وأبعد مسافة عنه3 إلى H؛ F درجته2 وأبعد مسافة عنه2، فيكون مرشحًا أفضل لهذا الهدف.
• مسافات F إلى A B C D E F G H هي (1,2,2,2,2,0,1,2). قوائم جميع الرؤوس تعطي F وحده قيمة2؛ والطريق B→A→F→G→H طوله4، فيثبت نصف القطر2 والقطر4.
• لدورة من خمسة رؤوس أبعد مسافة2 عند كل رأس، لذا جميع رؤوسها مراكز، ونصف قطرها2 وقطرها2. ليست r=D/2 مساواة عامة؛ الحد الذي نثبته هنا هو r≤D≤2r.
• في نجمة ثمانية رؤوس بالحواف AB AC AD AE AF AG AH، يكون A أعلى درجة7 والمركز الوحيد: نصف القطر1 والقطر2. نجاح اختيار أعلى درجة في النجمة لا يضمن نجاحه في مثالنا الأول.
• راجعنا1024 رسمًا مسمى على خمسة رؤوس، منها728 متصلًا، وقارنّا18200 خانة مسافة بين بحث العرض وحساب فلويد. تحقق حد r≤D≤2r في المدخلات المتصلة؛ النطاق لا يشمل كل رسوم الرؤوس الثمانية أو الأوزان والاتجاهات.

نقلل أكبر مسافة بعد حساب الأقصر

مركز الرسم هو مجموعة الرؤوس التي تساوي أبعد مسافة عنها نصف قطر الرسم. [1] قد تضم المجموعة رأسًا واحدًا أو أكثر؛ نحددها من المسافات، لا من مواضع الدوائر في الصورة.

في الرسم المتصل، أبعد مسافة عن رأس هي أكبر مسافة منه إلى أي رأس آخر؛ أصغر هذه القيم هو نصف القطر، وأكبرها هو القطر. [2] سنعد الحواف في أقصر طريق، بلا أوزان أو اتجاهات.

نبدأ برأس مرشح ونحسب المسافة إلى كل رأس آخر. المسافة هنا أقل عدد من الحواف في طريق يصل بين الطرفين. إذا وجد طريق بحافتين وآخر بأربع حواف، نستعمل2 في المقارنة؛ لا نبحث عن أطول طريق بسيط يمكن رسمه.

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

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

نعمل برسوم بسيطة متصلة وغير موجهة وغير موزونة. لكل حافة طرفان مختلفان، وAB هي BA نفسها. طول الخط المطبوع لا يدخل الحساب؛ كل حافة تعد خطوة واحدة، وتقاطع خطين لا يضيف رأسًا بلا اسم في المدخل.

خمس وصلات محلية لا تحسم المركز

نثبت الرؤوس A B C D E F G H، والحواف AB وAC وAD وAE وAF وFG وGH. B وC وD وE أوراق متصلة بـA، ثم يمتد فرع من A إلى F إلى G إلى H. لدينا ثمانية رؤوس وسبع حواف، والرسم كله متصل.

قائمة الدرجات في ترتيب الأسماء هي (5,1,1,1,1,2,2,1). A وحده درجته5، بينما F وG درجتهما2. من A نصل مباشرة إلى الأوراق الأربعة وإلى F، ثم نحتاج خطوة أخرى إلى G وثالثة إلى H.

إذن مسافات A بالترتيب هي (0,1,1,1,1,1,2,3)، وأكبرها3. الجيران الكثيرون جعلوا خمس وجهات قريبة بخطوة واحدة، لكن H ظل عند نهاية فرع من ثلاث حواف؛ تلك الوجهة هي التي تحدد أسوأ مسافة لهذا المرشح.

من F نصل إلى A وG بخطوة واحدة. نصل إلى كل ورقة عبر A بحافتين، وإلى H عبر G بحافتين. قائمة المسافات هي (1,2,2,2,2,0,1,2)، وأكبرها2، رغم أن F لا يملك سوى جارين مباشرين.

الصورة الرئيسية ترسم المدخل نفسه مرتين. في لوحة A تلون الرؤوس بحسب مسافاتها من A، وفي لوحة F بحسب مسافاتها من F. اللون يصف عدد الحواف في أقصر طريق؛ لا يصف طول الخط أو درجة الرأس، ولا تتغير الحواف بين اللوحتين.

المقارنة تكفي لرفض A كأفضل مرشح لأن F يعطي قيمة أقل. لكنها لا تكفي وحدها لإعلان أن F هو الوحيد أو أن القيمة2 هي الأصغر الممكنة؛ لذلك نراجع المرشحين الآخرين وحدًا أدنى في الخطوة التالية.

جدول كامل وشاهد يثبتان القيمة الدنيا

نحسب أبعد مسافة عند كل اسم، فنحصل على (3,4,4,4,4,2,3,4). الأوراق B وC وD وE تبعد أربع حواف عن H. G يبعد ثلاث حواف عن كل ورقة، وH يبعد أربعًا عنها. F وحده له القيمة2.

الجدول يجمع الدرجة وأبعد مسافة وعضوية المركز. لا نفرز الأسماء بحسب الدرجة قبل قراءة المسافات؛ كل صف يخص الرأس نفسه في القائمتين. درجة5 في صف A لا تقلل عدد3 المسجل في عمود أبعد مسافة.

يمكن إثبات الحد الأدنى من زوج طرفين أيضًا. الطريق B→A→F→G→H طوله4، وهو الطريق الوحيد بين B وH في هذا المدخل: B له جار واحد A، وH له جار واحد G، والفرع بينهما معلن بلا وصلات إضافية.

لأي مرشح x، المسافة4 بين B وH لا تزيد على مجموع المسافتين من B إلى x ثم من x إلى H. لو كانت المسافتان كلتاهما أقل من2، لكان مجموعهما أقل من4، وهذا مستحيل. إذن أبعد مسافة عن أي مرشح لا تقل عن2.

ولدينا F يصل إلى كل رأس بمسافة لا تتجاوز2، فيحقق هذا الحد الأدنى. إذن نصف القطر2. وأكبر قيمة في قوائم جميع الرؤوس4، مع شاهد الزوج B وH، فيكون القطر4؛ ليست3 عند A قطر الرسم كله.

وحدانية المركز جاءت من القائمة الكاملة: كل اسم سوى F له أبعد مسافة3 أو4. لا تأتي الوحدانية من رسم F في منتصف الصفحة أو من مشاهدة مسارين فقط. إذا أضفنا وصلة جديدة، وجب إعادة المسافات والجدول؛ لا ننقل النتيجة القديمة تلقائيًا.

حدود العلاقة بين نصف القطر والقطر

نسمي نصف القطر r والقطر D. أصغر أبعد مسافة لا تزيد على أكبر أبعد مسافة، لذلك r≤D. ويمكن إعطاء حد آخر باستعمال مركز c: لأي رأسين u وv، نمر من u إلى c ثم من c إلى v.

المسافة الأقصر بين u وv لا تزيد على طول هذا الطريق المركب. والمسافتان إلى c لا تزيد كل منهما على r، فتكون المسافة بين u وv لا تزيد على2r. وبأخذ أبعد زوج نحصل على D≤2r، أي r≤D≤2r.

في المدخل الأول D=4 وr=2، فيتحقق الحد الأعلى بالمساواة. لكنه حد وليس قاعدة تقول إن r=D/2 في كل رسم. ولا نحدد العلاقة من كلمة نصف في الاسم أو من هندسة دائرة مرسومة حول الشبكة.

نثبت دورة على A B C D E بالحواف AB وBC وCD وDE وAE. لكل رأس جاران على الدورة؛ جاراه يبعدان خطوة واحدة، والرأسان الباقيان خطوتين. إذن أبعد مسافة تساوي2 عند كل رأس.

هنا r=2 وD=2، وجميع الرؤوس الخمسة مراكز. القيمة D/2 تساوي1، ولا تحقق أبعد مسافة عند أي مرشح. الدورة تقدم مثالًا صغيرًا يرفض تحويل الحد D≤2r إلى مساواة عامة.

نستعمل المسافات الصحيحة في النموذج غير الموزون. يمكن صياغة الحد الأدنى أيضًا بتقريب D/2 إلى الأعلى، لكن ذلك يبقى حدًا؛ في الدورة الخماسية التقريب يعطي1، بينما القيمة الحقيقية2. لا يكفي حد عددي وحده لتعيين المركز.

قد تنجح أعلى درجة في مدخل آخر

للمقارنة نأخذ نجمة على الأسماء الثمانية نفسها، بالحواف AB وAC وAD وAE وAF وAG وAH. A يتصل بكل رأس آخر مباشرة، ولا توجد حواف بين الأوراق. درجة A تساوي7، ودرجة كل ورقة1.

أبعد مسافة عن A هي1. ومن أي ورقة إلى أي ورقة أخرى نحتاج حافتين عبر A، فتكون أبعد مسافة عن كل ورقة2. لذلك المركز الوحيد A، ونصف القطر1، والقطر2.

هذه النجمة تجعل أعلى درجة اختيارًا صحيحًا للمركز. لكنها ليست المدخل الأول: ألغينا امتداد الفرع FG وGH وجعلنا G وH متصلين مباشرة بـA. تغيرت الحواف والمسافات، لا أسماء الرؤوس وحدها.

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

المركز مجموعة حتى لو كانت من عنصر واحد. يجوز أن يكون فيها الجميع كما في الدورة، أو أن تستبعد أعلى درجة كما في المدخل الأول. كذلك لا نطلب تساوي درجات المراكز كشرط في تعريفها؛ المعيار هو أبعد مسافة.

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

مراجعة المسافات والنطاق الذي شمله الحساب

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

راجعنا كذلك جميع1024 قائمة حواف ممكنة على خمسة رؤوس ثابتة. منها728 مدخلًا متصلًا. لكل منها قارنا25 خانة في مصفوفة المسافات بين الطريقتين، فكان عدد خانات المسافة المقارنة728×25=18200.

تحقق حد r≤D≤2r في كل مدخل متصل، وكانت المراكز هي الأسماء التي تحقق أصغر قيمة من أكبر مسافات الصفوف. هذا فحص محدود لرسوم مسماة؛ لا يعني1024 نوعًا مختلفًا بعد حذف إعادة الأسماء، ولا يشمل جميع رسوم الرؤوس الثمانية.

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

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

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