الفصل العاشر
الشبكات
في المسألة التاسعة الواردة في الفصل السادس رأينا أن شبكة جسور كونيجزبرج لا يمكن عبورها مرة واحدة فقط لأن هذه الشبكة بها الكثير جدًّا من النقاط الفردية، أي العُقد المتصلة بعدد فردي من الأضلاع. وسندرس الآن هذا النوع من المسائل بشكل عام.
نحن نعني بكلمة «شبكة» أي مجموعة من العُقد (تُسمى أحيانًا رءوسًا وأحيانًا أخرى
مجرد
نقاط) وأضلاع تصل بين هذه العُقد. سوف نسمح للعديد من الأضلاع أن تربط بين نفس الزوج
من
العُقد (متعدد الأضلاع)، كما نسمح بوجود الحلقات، وهي أضلاع تبدأ وتنتهي عند نفس العُقدة.
علاوة على ذلك، بشكل عام ليس من الضروري أن تتكون الشبكة من قطعة واحدة متصلة، لكن يمكن
أن
تتكون من عدد من المُركبات. وقد تمر أضلاع الشبكة بعضها ببعض، وطبعًا في حالة وجود أضلاع
كثيرة لا يمكن تجنب ذلك. وعلى الرغم من ذلك، إذا أمكن رسم الشبكة دون أن تمر الأضلاع
بعضها
ببعض، في هذه الحالة تسمى الشبكة «شبكة مستوية». وتتضح كل هذه السمات في شكل ١٠-١.
هناك ملاحظة واحدة تنطبق على الكثير من الشبكات بصفة عامة. نعني بدرجة العقدة عدد
الأضلاع
المرتبطة بهذه العقدة (وتحسب الحلقة بضلعين). فمثلًا العُقدة في المثال السابق لها الدرجة . وإذا جمعنا كل درجات العُقد في الشبكة، فسوف نحصل على عدد يساوي بالضبط ضعف عدد الأضلاع ؛ لأن كل ضلع يساهم ﺑ في المجموع الكلي؛ لأنه يصل بين عقدتين فيحسب مرتين. في المثال الموضح في
شكل ١٠-١، عدد الأضلاع يساوي إجمالًا ضلعًا، وبجمع درجات العقد نحصل على:
وهو ما يتفق مع ملاحظتنا العامة أن .
شكل ١٠-١
لنرمز ﺑ لمجموع درجات كل العُقد الزوجية (أي العُقد ذات الدرجة الزوجية)، و لمجموع درجات العقد الفردية المناظر.
ومن ثم فإن . والآن بما أن هو مجموع أعداد زوجية، إذن فهو بالضرورة زوجي، وكذلك ؛ ومن ثم فإن عدد زوجي أيضًا. وبما أن هو مجموع أعداد فردية، فهذا غير ممكن إلا إذا كان عدد الأعداد المجموعة
في المجموع هو أيضًا عدد زوجي؛ بمعنى أن العدد الفعلي للعُقد الفردية في الشبكة يجب
أن يكون عددًا زوجيًّا. ونستنتج من ذلك أن أي شبكة لا بدَّ أن تتكون من عدد زوجي من العُقد
ذات الدرجة الفردية. (في المثال السابق يوجد عُقد فردية.) هذه الحقيقة، التي يُطلق عليها أحيانًا تمهيدية المصافحة،
مفيدة للغاية: ومن المهم أن ندرك إدراكًا كاملًا أنها صحيحة. فهي تخبرنا مثلًا أنه من
المستحيل تكوين شبكة من عُقد حيث كل عُقدة لها درجة . إذا حاولت تكوين مثل هذه الشبكة فلن تنجح في ذلك على الإطلاق، وهو ما
تؤكده تمهيدية المصافحة.
(١) إعادة النظر في مسألة كونيجزبرج
سوف نبحث الآن في سؤال عبور شبكة كونيجزبرج؛ أي مسألة إيجاد مسار عبر الشبكة نمرُّ فيه بكل ضلع مرة واحدة فقط.
الحُجة التي قدَّمناها فيما يخص جسور كونيجزبرج توضح أنه لتكون الشبكة قابلة للمرور عبرها، فإنها يجب ألا تحتوي على أكثر من عقدتين
فرديتين، ويجب أن تكونا عند طرفَي مسار المرور. أما إذا طالبنا بالمزيد وتطلعنا لمرور
دائري، أي إن مسار المرور يبدأ وينتهي عند نفس العُقدة، فإن حجة التزاوج الواردة في
الفصل السادس، توضح أن هذا سيكون مستحيلًا إلا إذا كانت كل العُقد زوجية الدرجة.
(المسار الدائري يجب أن يصل إلى أي عقدة ويغادرها عددًا متساويًا من المرات؛ ومن ثم يجب
أن يكون عدد الأضلاع المرتبطة بالعُقد زوجيًّا.) وقد تبين أن هذا الشرط الضروري هو
أيضًا كافٍ للمرور عبر الشبكة المتصلة ؛ أي إن يمكن المرور عبرها إذا — وفقط إذا — كانت جميع العُقد زوجية. (ومن
الواضح أننا من المستحيل أن نمر عبر شبكة تشتمل على عدة مكونات غير متصلة.)
هل يمكن أن نجد طريقة للقيام بذلك فعلًا؟ هل يمكن أن ينجح أي شيء؟ ربما إذا كان لدينا
مثل هذه الشبكة ويمكننا السير عبرها بأي شكل، باستخدام ضلع جديد في كل نقطة التقاء،
فسوف نجد أنفسنا في نهاية الأمر حيث بدأنا وقد استخدمنا جميع الأضلاع. هذا النهج بسيط
في التفكير ولا يصلح دائمًا؛ فإذا لم تكن حذرًا فستصبح في مأزق.
خذ المثال التالي (شكل ١٠-٢). هذه شبكة متصلة تتكون من عقد جميعها
ذات درجة زوجية. ومع ذلك، إذا بدأنا السير من العُقدة وكان المسار ، فسوف نوقع أنفسنا في مأزق. إذا كان لنا أن نتصور حرق الجسور التي
سرنا عليها، فلدى وصولنا إلى فإن الشبكة المتبقية سوف تنقسم إلى مكونين، وسنكون قد حوصرنا في
الناحية اليسرى. ومع ذلك فهذه هي الصعوبة الوحيدة التي يمكن أن تنشأ ويمكننا تفاديها
بسهولة. لسنا مضطرين إلى أن نكون في منتهى المهارة عندما نحدد مسارنا، ولسنا مضطرين إلى
أن نأخذ في اعتبارنا الخطوتين التاليتين — كل ما نحتاج إليه هو أن نتجنب اتخاذ خطوة
تؤدي إلى انقسام الشبكة المتبقية إلى اثنتين. يمكننا بالفعل إعطاء خوارزمية لعمل ذلك،
أو بعبارة أخرى صياغة عملية ميكانيكية نتجنب بها ضرورة اتخاذ القرار السليم أو التميز
بذكاء نادر.
شكل ١٠-٢
ابدأ عند أي عُقدة للمرور عبر الشبكة بالطريقة التي تحلو لك، ولكن:
-
(١)
ارسم صورة للشبكة واحذف أي ضلع استخدمته وأي عُقدة مررت بكل الأضلاع المتصلة بها.
-
(٢)
في كل خطوةٍ لا تستخدم ممرًّا، أي ضلعًا يصل بين جزأين لم يكونا ليتصلا من غيره، إلا إذا كان لا يوجد أي اختيار آخر.
لن تجد الآن أي صعوبة في المرور عبر الشبكة السابقة، بادئًا عند أي
عُقدة تريدها. (لاحظ أن الخطوة الثالثة من المسار الفاشل الذي اتخذناه تنتهك القاعدة الثانية عن طريق
استخدام ممر.)
إذا كانت الشبكة المتصلة بها عُقد ذات درجة فردية، فإنه يجب، بمقتضى «تمهيدية
المصافحة» أن يكون عددها على الأقل . فإذا كان هناك أكثر من اثنتين، نعلم أنه لا يوجد مسار للمرور عبرها؛
ولكن ماذا لو كان هناك بالضبط عُقدتان ذواتا درجةٍ فردية؟ فهل يمكن استخدام الطريقة
السابقة لإنتاج مسار للمرور حتى لو لم يكن دائريًّا؟ الإجابة: نعم، وسوف نشرح
الآن.
يمكننا أن نمر عبر الشبكة مبتدئين عند أيٍّ من العُقدتين الفرديتين ومنتهين عند
الأخرى. فلنسمِّ العُقدتين الفرديتين و على الترتيب. ارسم ضلعًا آخر في الشبكة من إلى. في هذه الشبكة المعدلة حتى الآن جميع العُقد زوجية الدرجة؛ ومن ثم
الخوارزمية السابقة تسمح لنا بإيجاد دائرة للمرور عبرها، بَدءًا من ، ويمكن أيضًا الإصرار على أن يكون الضلع الجديد الذي أضفناه هو الأول في الاستخدام. ومن ثم فهذه الدائرة ستتكون
بالسير من إلى عبر والباقي لا بدَّ أن يكون مسارًا للمرور من الشبكة الأصلية التي تبدأ
عند وتنتهي عند . فكر في المثال التالي الذي يحتوي على عقدتين من العقد الفردية، كما
هو موضح في شكل ١٠-٣.
يمكنك العثور على البرهان أن الخوارزمية السابقة صالحة دائمًا في أي كتاب جاد عن الشبكات ونظرية المخططات، وهو الاسم الذي يطلق غالبًا على دراسة الشبكات. وستجد أن البرهان ليس صعبًا ولا طويلًا ولكنه مزعج قليلًا إذا أصررت على تبرير كل التفاصيل، وهو ما لا تفضل الكثير من الكتب الخوض فيه حتى لا تفسد بساطة الفكرة.
شكل ١٠-٣
(٢) تقاطع الأسلاك: هل يمكن تفاديه؟
النوع الثاني من مسائل الألغاز التي ترتبط بالشبكات هو عندما يطلب منك رسم شبكة تشتمل
على روابط معينة بحيث تكون الأضلاع غير متقاطعة. ينطوي المثال القياسي على ثلاثة منازل
يجب إمدادها بمنافذ للغاز والماء والكهرباء. لتقليل احتمالية أن تقطع إحدى الخدمات
إمداد الخدمات الأخرى أثناء الصيانة، سيكون من الأفضل أن تُوضع الوصلات بحيث لا تعبر
خطوط الإمداد بعضها فوق بعض. فهل يمكن عمل ذلك؟ ويبين شكل ١٠-٤ شبكة
فاشلة كادت تنجح في تحقيق المطلوب.
شكل ١٠-٤
بإمكانك أن تصمم شبكة بالجودة نفسها، ولكن ليس بجودة أعلى. فكيف يمكنك إثبات أن هذا مستحيل؟ كيف يمكننا التأكد من أنه لا توجد طريقة ماهرة لفعل ذلك ولكننا لم نتمكن من اكتشافها؟ الصعوبة لا تكمن كثيرًا في كون المسألة معقدة في الأساس، ولكنها تكمن في أن المرء، بصرف النظر عن المبرر، سيحتاج إلى التأكيد على أنه من الواضح أن أحد الأضلاع لا بدَّ أن يمرَّ فوق ضلع آخر لأنه يجب أن يمر من داخل تكوين معين قامت الأضلاع الأخرى بإنشائه إلى خارجه. ولا حرج في ذلك، إلا أنه من الصعب جدًّا تبرير ذلك بشكل دقيق نظرًا لصعوبة التعامل مع المنحنيات المغلقة حتى البسيط منها في التصميم الكامل للشكل.
في الحقيقة، توجد شبكتان أساسيتان غير مستويتين؛ بمعنى أنه لا يمكن رسمهما بدون أن
يلتقيَ زوج واحد على الأقل من الأضلاع عند نقطة ليست عُقدة في الشبكة. الأولى التي سبق
أن ذكرناها هي وهي الشبكة التي تنشأ من توصيل كل عقدة في مجموعة مكونة من ثلاث عُقد
بمجموعة أخرى مكونة من ثلاث عُقد. أما الثانية فهي التي تسمى الشبكة الكاملة على عقد: تحتوي الشبكة الكاملة على عقد على ضلع واحد يصل بين كل زوج من العُقد (انظر شكل ١٠-٥).
شكل ١٠-٥
لا تكمن أهمية و في كونهما غير مستويتين فحسب، بل في حقيقة أن كل الشبكات تعتبر
مستوية إلا إذا احتوت على نسخة من إحدى هاتين الشبكتين المحظورتين. هذه النظرية، التي
يصعب وصفها بدقة وإثباتها، وضحها كوراتوفسكي عام ١٩٣٠. وقبل أن نتوغل في مناقشة الشبكات
المستوية، سنتوقف قليلًا لتوضيح بعض جوانب الوضع العام.
نحن لا نحتاج إلا إلى أن نهتم بالشبكات التي لا تحتوي على حلقات أو أضلاع متعددة،
وسوف نسمي هذه الشبكات «الشبكات البسيطة». والسبب في ذلك هو أنه إذا كانت الشبكة مستوية فإن الشبكة البسيطة الأساسية التي نحصل عليها بحذف جميع
الحلقات ودمج أي أضلاع متعددة بين عُقدتين في ضلع واحد بينهما، تكون أيضًا مستوية.
بالعكس إذا كانت الشبكة البسيطة الأساسية من الشبكة مستوية، فإنه يمكننا أن نستبدل بأي
ضلع وحيد من الشبكة البسيطة الأساسية، العدد المطلوب من الأضلاع المتعددة وإضافة أي عدد
من الحلقات نرغب فيه للصورة دون انتهاك للاستواء؛ لذلك إذا كانت الشبكة البسيطة
الأساسية مستوية فإن الشبكة نفسها مستوية كذلك.
سبق أن قمنا بحل مسألة حول الشبكات البسيطة في الفصل السادس، حيث رأينا أنه في أي حفل يوجد على الأقل اثنان من الأفراد لهما نفس عدد الأصدقاء في الحفل. يمكننا إعادة صياغة هذا السؤال ليصبح عن الشبكات البسيطة: ارسم شبكة تحتوي على عُقدة واحدة لكل شخص واربط بين أي عُقدتين بضلع إذا كان ثمة علاقة صداقة بين الشخصين اللذين تمثلهما العقدتان. ما برهنته الحجة التي سقناها في الفصل السادس هو أنه في أي شبكة بسيطة يجب أن يكون هناك عُقدتان على الأقل لهما نفس الدرجة.
ثمة فكرة سوف يتكرر ظهورها عدة مرات فيما تبقى من هذا الفصل، وهي مكملة أي شبكة بسيطة
. لتكن شبكة بسيطة حيث ترمز لمجموعة العُقد الموجودة فيها. مكملة الشبكة ، التي يرمز إليها بالرمز ، هي شبكة بسيطة لها نفس مجموعة العُقد مثل ، ولكن يوجد فيها عُقدتان يربط بينهما ضلع في ، بينما لم يكن هناك ما يربطهما في . ويترتب على ذلك إذا وضعنا مع المكملة فسنحصل على الشبكة الكاملة المشتملة على مجموعة العُقد . بأخذ مكملة المكملة للشبكة فإننا طبعًا نحصل على مرة أخرى: (انظر شكل ١٠-٦).
شكل ١٠-٦
في المسألة الثامنة في الفصل السادس رأينا أنه في
أي حفل يشارك فيه ستة أشخاص أو أكثر يوجد دائمًا مثلث من المعارف المشتركة أو مثلث من
الأشخاص الذين لا يعرف أحدهم الآخر. هذه المسألة يمكن صياغتها أيضًا في سياق الشبكات
والشبكات المكملة لها كشبكة المعارف وشبكة الغرباء وهما مكملتان إحداهما للأخرى:
المعرفة المتبادلة يُرمز لها بالأضلاع الموجودة في ، في حين أن الأضلاع في ترمز إلى عدم معرفة الشخصين أحدهما للآخر. ما تطلبه المسألة حقًّا هو
إثبات أنه في أي شبكة بسيطة تحتوي على ست عقد على الأقل، فإما أن تحتويَ على نسخة من (أي مثلث من الأضلاع) أو تحتوي الشبكة المكملة لها على هذه النسخة. ويمكن ملاحظة ذلك في المثال السابق حيث تحتوي على المثلث المطلوب على الرغم من أن لا تحتوي على مثل هذا المثلث. (بطبيعة الحال، من الممكن تمامًا أن
تحتوي كلٌّ من و على مثلثات عديدة.)
ثمة مثال إرشادي ينشأ إذا ألقينا نظرة على الشبكة على عُقد يمكن رسمها على شكل خماسي منتظم. وهذه قد سبق أن قابلناها في
الفصل السادس؛ إذ إنها عند التفكير فيها بوصفها تمثيلًا لخمسة ضيوف حول مائدة في حفل
عشاء تقدم مثالًا على حفل ليس به ثلاثة أشخاص يعرف أحدهم الآخر ولا ثلاثة أشخاص لا يعرف
أحدهم الآخر. الشكل الخماسي لا يحتوي على أي مثلث. ومع ذلك إذا رسمنا بالطريقة المعروفة فإن الصورة الناتجة لن تكون مفيدة (انظر شكل ١٠-٧). الشبكة تبدو أكثر تعقيدًا من ؛ إذ إنها لا تبدو حتى مستوية حيث إن أضلاعها يمر بعضها ببعض في مواضع
كثيرة. على أية حال، عند الفحص بدقة نجد أن لها نفس تكوين الشبكة ولا سيما أنها أيضًا تفتقر إلى المثلثات. لتوضيح ذلك لا تحتاج إلا
لترتيب الطريقة التي ندرج بها العُقد حول خارج الشكل الخماسي: بدلًا من أن يكون الترتيب
عكس عقارب الساعة سنرتبها على النحو التالي ؛ ومن ثم تصبح صورة الآن شكلًا خماسيًّا عاديًّا (وتصبح على شكل النجمة)؛ انظر شكل ١٠-٨.
شكل ١٠-٧
شكل ١٠-٨
من ثم يتبيَّن لنا أن الشبكتين و، رغم أنهما تمثلان عَلاقات مختلفة، فهما تتماثلان عند أخذ الهيكل
الشبكي لكليهما في الاعتبار فحسب. علماء الرياضيات لديهم رأي في ذلك: نقول إن الشبكتين
متماثلتان إذا أمكن تمثيلهما بنفس الصورة. وهذا يعني أن يوجد تناظر واحد إلى واحد بين
عقد كلتا الشبكتين؛ بحيث إن أي عُقدتين تتجاوران في الشكل الأول (بمعنى أنهما ترتبطان
بضلع واحد)، إذا — وفقط إذا — كانت العُقدتان المقابلتان لهما في الشكل الثاني هما
أيضًا متجاورتان. وبصفة عامة، قد يكون من الصعب معرفة ما إذا كانت الشبكتان متماثلتين
أم لا. على سبيل المثال، الصورتان في شكل ١٠-٩ كلتاهما تمثل . وفيما يلي التناظر المناسب بين العقد الذي يوضح ذلك:
وأترك للقارئ التحقق من أن أي عقدتين ستكونان متجاورتين في الشبكة الأولى إذا — وفقط إذا — كانت نظيرتاهما متجاورتين في الشبكة الثانية.
شكل ١٠-٩
يمكنك تخيُّل صعوبات التعامل مع الشبكات المُعقدة جدًّا. ومع ذلك فمن السهل أحيانًا
اكتشاف أن شبكتين غير متماثلتين: ما عليك إلا أن تعثر على اختلاف أساسي بين الشبكتين.
فمثلًا إذا كانت الشبكتان لا تحتويان على نفس العدد من العُقد أو نفس العدد من الأضلاع،
فإنهما قطعًا غير متماثلتين. وقد يكون الاختلاف طفيفًا بدرجة أكبر. فيمكن أن نجد عُقدة
لها الدرجة متصلة بعُقدة لها الدرجة ، في حين أن ذلك غير موجود في الشبكة الأخرى؛ فإذا كانت هذه هي الحالة
فلن تكون الشبكتان متماثلتين. على سبيل المثال، أوجد اختلافًا أساسيًّا بين الشبكتين
الموضحتين في شكل ١٠-١٠. كلتا الشبكتين تحتويان على عقدتين لهما
الدرجة ، ولكن في الشبكة الثانية هاتان العقدتان متجاورتان، وهي ليست الحالة
في الشبكة الأولى، ولهذا السبب فمن غير الممكن تسمية العقد في الشبكتين و بطريقة تحترم التجاور. وعلى الرغم من ذلك، إذا كان لديك مثال لا يظهر
فيه هذا الاختلاف في الهيكل الشبكي، فإن مسألة تحديد ما إذا كانت الشبكتان متماثلتين
أم
لا قد تصبح مسألة عويصة ومتعبة للغاية.
شكل ١٠-١٠
يمكننا الآن توضيح ما نعنيه بالاستواء. فالشبكة تكون مستويةً إذا أمكن تمثيلها بواسطة
شبكة لا تتقاطع أضلاعها، ومن ثَم فهي على مستوًى واحد. فشبكة
عدم معرفة الضيوف بعضهم ببعض هي شبكة مستوية لأنها
يمكن تمثيلها بشكل خماسي. بعبارة أخرى، كونُك رسمت صورةً مبدئيةً للشبكة وكانت هذه
الصورة تحتوي على عدة أضلاع متقاطعة؛ لا يعني بالضرورة أن الشبكة غير مستوية. على سبيل
المثال، الشبكة يمكن بطبيعة الحال رسمها كما في اليسار في شكل ١٠-١١، ولكن مع ذلك، يمكن بسهولة رؤيتها على أنها مستوية كما تبين صورتها البديلة الموجودة
في اليمين.
شكل ١٠-١١
هناك صيغة خاصة تنطبق على الشبكات المستوية ويمكن استخدامها لتوضيح أن الشبكة ليست
مستوية إذا كانت تحتوي على عدد كبير جدًّا من الأضلاع: وتؤدي هذه الصيغة بشكل خاص إلى
تفسير لماذا تكون و غير مستويتين.
ثمة عددان يرافقان أي شبكة: العدد ، وهو عدد العُقد والعدد ، وهو عدد الأضلاع؛ ولكن بالنسبة للشبكات المستوية، يمكننا إرفاق عدد
ثالث بها وهو ، وهو عدد أوجه الشكل المستوي، حيث الوجه هو المنطقة المحاطة بالأضلاع
ولا تحتوي على أي منطقة أصغر محاطة بالأضلاع. ومن المناسب أن نعد السطح الخارجي للشبكة
المستوية على أنه وجه آخر، مع أن هذا يختلف قليلًا عما سوف ننفذه. بالنسبة للنسخة
المستوية من الشبكة السابقة، فنجد أن و و. ويعد هو وجهها الخارجي. من الواضح أنه، على الرغم من أن هذه الشبكة
مرسومة، فإن العددين و سيظلان على حالهما، ولكن هذا ليس واضحًا جدًّا فيما يتعلق بالعدد . ومع ذلك، فهو صحيح، لأنه في أي شبكة مستوية متصلة ترتبط الأعداد
الثلاثة بعضها ببعض من خلال معادلة بسيطة للغاية:
(10-1)
في نموذج الشبكة نرى أن هذه المعادلة متحققة: . والسبب في استمرار هذه العلاقة في أي شبكة مستوية متصلة يمكن فهمه
بتخيُّل أن ترسم الشبكة ضلعًا تلو الآخر، مع إضافة أي عقد جديدة عند الضرورة، وملاحظة
أن المجموعين على جانبي المعادلة دائمًا ما سيزيدان أو سيقلان معًا. عندما نرسم أول
ضلع، سيكون لدينا شبكة مستوية حيث إن و و. (وجه واحد فقط غير محدود خارج الشبكة) ومن ثم تتحقق المعادلة. وكلما
أضفنا المزيد من الأضلاع، ستوجد لدينا حالتان لفحصهما. نظرًا لأن الصورة النهائية
مترابطة، فيمكن أن يتم تجميعها ضلعًا تلو الآخر دون الحاجة لرسم ضلع آخر غير مرتبط بأي
عُقدة من العقد المرسومة من الأساس، على الرغم من أننا قد نحتاج لتقديم عُقدة واحدة
جديدة عند رسم ضلع جديد. توجد حالتان:
-
(١)
يتم رسم ضلع مما يتطلب تقديم عُقدة جديدة لا تقع على ضلع موجود بالفعل، كما في شكل ١٠-١٢. في هذه الحالة يزيد كل من و بمقدار لكل ضلع يتم إضافته؛ ومن ثم تظل المعادلة ) 10-1 ( موزونة: في الشبكة الأصلية تأخذ المعادلة ) 10-1 ( الشكل وتغيرت إلى للشبكة على اليمين التي تكونت بإضافة ضلعين جديدين من النوع السابق وصفه.
شكل ١٠-١٢ -
(٢)
يتم رسم ضلع لا يتطلب أي عُقد جديدة (شكل ١٠-١٣). وهذا سيؤدي إلى زيادة و بمقدار ؛ لأن الضلع الجديد سوف يَقسم الوجه الموجود (ربما يكون الوجه الخارجي) إلى اثنين. وهذا سوف يؤدي إلى إضافة لكل طرَف من طرفَي المعادلة.
في المثال المبين في شكل ١٠-١٣ أُضيف ضلعان من هذا
النوع؛ واحد منهما قَسم وجهًا داخليًّا إلى وجهين، بينما قسم الآخر الوجه الخارجي إلى
اثنين. ومن ثم تحولت الصيغة ) 10-1 ( من إلى ، لكنها ما زالت موزونة.
شكل ١٠-١٣
هذا يحقق ما يسمى صيغة متعدد السطوح للشبكات المستوية. يمكننا الآن استغلال هذه الصلة
بين و و لتحديد بعض الخواص الاستثنائية التي تتمتع بها الشبكات
المستوية.
لنفترض أن لدينا شبكة مستوية بسيطة متصلة، أي تشتمل على مكون به عدد من الوجوه. لنسمِّ عدد الأضلاع التي تحيط بوجه باسم «عدد الوجه»
الخاص بهذا الوجه ونرمز لهذه المتتابعة من الأعداد ﺑ . إذا جمعنا كل أعداد الوجه فإننا سنجمع كل ضلع مرتين على الأكثر، لأن
كل ضلع يقع على حدود وجهين على الأكثر. (الضلع يمكن أن يكون على حدود وجه واحد فقط، كما
يتضح من واحد من الأضلاع في شكل ١٠-١٣.) ومن ثم فإن مجموع أعداد
الوجه لا يزيد على ضعف ، أي العدد الإجمالي لأضلاع الشبكة:
والآن لأي شبكة مستوية بسيطة تحتوي على ثلاثة أضلاع على الأقل، سيكون
كل وجه محدودًا على الأقل بثلاثة أضلاع؛ لأننا كان من الممكن أن نجد وجهًا محدودًا
بضلعين فقط إذا سمحنا بالأضلاع المتعددة، أما الوجه الذي يحيط به ضلع واحد، فهو الوجه
المحاط بحلْقة، وكلاهما سمتان محظورتان في الشبكات البسيطة. بعبارة أخرى، كل «عدد وجه»
يكون على الأقل ، بحيث يكون:
بجمع الحقيقتين السابقتين نحصل على:
بجمع هذه الصيغة مع صيغة متعدد السطوح رقم
) 10-1 ( نحصل على:
بعبارة أخرى، بضرب الطرفين في ، نجد أنه في أي شبكة مستوية بسيطة متصلة تتكون من أكثر من عُقدتين:
وهذا ينفي كون الشبكة تدخل في نطاق الشبكات المستوية لأنها تحتوي على عدد كبير من الأضلاع:
بالنسبة للشبكة نجد أن و؛ ومن ثم فإن أكبر من .
ومع ذلك، فإن الشبكة هربت لحظيًّا من هذا الشرك، حيث إن و ومن ثم فإن القاعدة متَّبعة في . ولكنها، مع ذلك، سوف تستسلم للحجة التالية المشابهة لما قرأناه
حالًا. نظرًا لأن أضلاع دائمًا ما تربط بين مجموعتين من ثلاث عُقد (انظر شكل ١٠-٩)؛ ومن ثم فإن أي دائرةٍ في الشبكة يجب أن يكون طولها عددًا
زوجيًّا: على الأخص لا توجد مثلثات؛ ومن ثم فإنه في أي تمثيل مستوٍ للشبكة ، إذا أمكن وجود مثل هذا التمثيل، فإن كل وجه لا بدَّ أن يحيط به
أربعة أضلاع على الأقل. وهذا يعطينا جملة أقوى من ذي قبل: وهي ؛ أي إن . وبجمع هذه الجملة مع صيغة متعدد السطوح رقم
) 10-1 ( يتضح أنه في أي تمثيل مستوٍ
للشبكة لا بدَّ أن يكون:
إلا أن الشبكة لا تستطيع تخطي هذه العقبة، لأن ، وهذا أكبر من .
تعتبر صيغة متعدد السطوح حقيقة أساسية جدًّا من حقائق الرياضيات. وقد سمحت لنا بإثبات
أنه لا يمكن رسم ولا دون أن يتقاطع ضلعان على الأقل. والسبب في أنها سميت بهذا الاسم هو
أنها تنطبق على متعدد السطوح، أي على الأشكال المصمتة المحاطة بأسطح مستوية متعددة
الأضلاع، شريطة أن تكون محدبة، أي إن الأوجه المضلعة تلتقي عند زوايا أقل من الزاوية
المستقيمة، مثل متعدد الأسطح المنتظم الذي شاهدناه في الفصل السابق. فمثلًا في المجسم
ذي الاثني عشر سطحًا يوجد ركنًا ، و ضلعًا ، و وجهًا ؛ ومن ثم تنطبق عليه الصيغة . ويمكنك التحقق من أن المجسمات الأربعة المنتظمة الأخرى تنطبق عليها
هذه الصيغة أيضًا.
إذا وافقنا على صيغة متعدد السطوح، فإن من السهل بما يكفي توضيح أنه من الممكن
الإجابة عن سؤال من نوعية السؤال الذي طُرح عند ختام الفصل السابق: هل من الممكن أن
يكون هناك مجسم منتظم آخر يحتوي على خمسة مثلثات متساوية الأضلاع تلتقي عند كل ركن،
ولكنه يحتوي على عدد من الأضلاع والأوجه، مختلف عن المجسم ذي العشرين وجهًا؟ الإجابة
بالتأكيد لا، لأن صيغة متعدد السطوح لن تنطبق عليه. لنفترض أن لدينا مثل هذا المجسم
المنتظم حيث عدد أركانه وعدد أضلاعه وعدد وجوهه . عند عدِّ كل الأضلاع عند كل ركن سنجد ، ولأن هذا يعد كل ضلع مرتين نجد أن . بالمثل عند عد الأضلاع بمعرفة الوجوه سنجد أنه بما أن كل وجه له
ثلاثة أضلاع وكل ضلع يقع على وجهين، فإن . عند ضرب صيغة متعدد السطوح في سنحصل على:
مما سبق نستنتج أن يجب أن تساوي ؛ ومن ثم فإن و ولا توجد قيم أخرى ممكنة.
(٣) الحفلات والجماعات الأكبر
نعود الآن إلى نوع المسائل الذي قدمناه لأول مرة
في الفصل السادس. ما مدى الكبر الذي يجب أن تكون عليه الحفلة حتى نتأكد من وجود مجموعة
من أربعة أصدقاء مشتركين أو أربعة أشخاص لا يعرف أحدهم الآخر؟ بالرجوع إلى لغة الشبكات،
سيكون السؤال هو: كم عدد العقد الذي يجب وجوده في شبكة بسيطة حتى نتأكد أن أو تحتوي على نسخة من ؟ وقد ثبت أن هذا العدد هو في الحقيقة. ولن أستطيع إثبات هذا هنا. ولكن ما يمكنني إثباته، على
أية حال، هو أن العدد موجود وسوف أقدم حجة لإثبات أنه ليس أكثر من . هذا قد يبدو غير مثير للإعجاب، لكن تذكر أنه ليس من الواضح أن العدد
لا بدَّ أن يوجد من الأساس. وستجد الحُجة المقدمة مهمة للغاية وهي الأساس لبرهان نظرية
رامزي المطبقة على مجموعات أكثر عمومية من تلك التي نفحصها؛ كما أن لها تفسيرات مفيدة
في الحالات التي تنطوي على مجموعات غير منتهية. بشكل خاص يمكن تعميم الحُجة التي أقدمها
هنا لتثبت أن أعداد رامزي موجودة دائمًا، بمعنى أنه: «لأي عدد مُعطًى يوجد عدد بحيث إن الشبكة البسيطة التي تحتوي على عدد من العقد أو الشبكة المكملة لها تحتوي على نسخة من داخلها.» في الفصل السادس، في السؤال الثامن رأينا أنه إذا كانت فإن وهي الحالة الأولى الجديرة بالاهتمام. سوف أثبت الآن أنه إذا كانت فإن قيمة لن تكون أكبر من .
من الأسهل اعتبار شبكة والمكملة لها متراكبتين، مما يُكوِّن نسخة من شبكة كاملة. لوِّن
الأضلاع بالأبيض أو الأسود تبعًا لكون الضلع موجودًا في أم في المكملة لها. ما سوف أثبته هو أنه بفرض أن الشبكة تحتوي على عُقدة، فإنها يجب أن تحتوي على نسخة وحيدة اللون من ، بمعنى أنه توجد مجموعة من أربع عُقد بحيث تكون الأضلاع الموصلة بين
هذه العُقد كلها باللون الأبيض أو أنها كلها باللون الأسود.
لنفترض إذن أن شبكتنا هذه (أو الحفل إذا شئت) تحتوي على الأقل على:
إذا كنت تتذكر صيغة المتسلسلة الهندسية من أول مسألة في الفصل الأول،
فسوف ترى أن هذا العدد هو . (العدد ليس مهمًّا فعلًا فيما يأتي: فقد جرى اختياره، كما سترى،
للتأكد من أن لدينا عددًا كبيرًا كافيًا من العُقد لتنفيذ الإجراء التالي.) قم بالتركيز
على إحدى العُقد — ولتكن العقدة — واستمر كما يلي (انظر شكل ١٠-١٤). من كل الأضلاع
الخارجة من (يوجد على الأقل منها طبعًا، لأننا نستخدم الشبكة
الكاملة)، سيكون نصفها على الأقل من لون واحد، وليكن . ( إما أن يكون أبيض أو أسود.) افحص جميع العُقد المتصلة بالعُقدة بضلع ملوَّن باللون ، وارمز إلى هذه المجموعة من العقد بالرمز . هناك ما لا يقل عن:
من هذه العقد. فلتختر منها واحدة ولتطلق عليها .
شكل ١٠-١٤
على الأقل نصف الأضلاع الخارجة من ومؤدية إلى عُقد أخرى في كلها من لون واحد، ولنسمِّ هذا اللون (وقد يكون هو نفسه أو يكون مختلفًا عنه). ولتكن هي مجموعة هذه العُقد. جدير بالذكر أن محتواة بالكامل في وهي نفسها تحتوي على الأقل على:
عنصرًا. اختر عنصرًا جديدًا من .
نقوم بهذه العملية خمس مرات، فنحصل على العُقد و و… و وزمرة من المجموعات:
كل مجموعة منها محتواة في التي تسبقها كما في شكل ١٠-١٤. العدد المبدئي للعُقد جرى اختياره ليضمن القيام بهذه العملية
على الأقل مرات، والمجموعات و و ستحتوي على الأقل على عددٍ من العناصر و و على الترتيب. كيف يساعد كل ذلك؟ نحن الآن بحاجة إلى ملحوظة دقيقة
للإجابة عن السؤال. وتحتوي الفقرة التالية على الفكرة الرئيسية، لكنها تتطلب بعض
التفكير.
افحص قائمة العُقد و و و و. انظر إلى أي عنصر في هذه القائمة، وليكن مثلًا. كل الأضلاع الخارجة من إلى عناصر المجموعة لها نفس اللون. والآن و و جميعها في ؛ ومن ثم فإن كل الأضلاع الخارجة من إلى عناصر القائمة التي تتلو لها نفس اللون. هذه الحجة تنطبق على إلى ، فكل واحدة من هذه العقد يقترن بها لون معين ، هو نفسه لون الأضلاع التي تخرج منها إلى جميع عناصر القائمة التالية
لها. والآن لا يوجد سوى لونين متاحين الأبيض والأسود، وعلى ذلك فعلى الأقل ثلاثة من و… و تقترن بنفس اللون (وليكن الأبيض مثلًا). اختر هذه المجموعة المكونة
من ثلاثة عناصر بالإضافة إلى : والآن كل ضلع بين هذه العقد الأربعة يجب أن يكون أبيض اللون؛ ومن ثم
نكون قد أوجدنا نسختنا أحادية اللون من ، أو إذا شئت مجموعتنا المكونة من أربعة أصدقاء مشتركين.
(٤) الآلات واللغات
ينطوي موضوعنا الأخير على النظر إلى الشبكات من منظور مختلف تمامًا: ننظر إليها على
أنها آلات. المكون الرئيسي للأوتوميتون (الآلات ذاتية التشغيل) هو عبارة عن شبكة يطلق
على العقد المكونة لها اسم «أوضاع». ومن بين هذه العُقد يوجد «الوضع المبدئي» وعدد من
«أوضاع القبول». (قد يوجد أكثر من وضع قبول، والوضع المبدئي نفسه يمكن أن يكون وضع
قبول.) وتكون الآلة ذاتية التشغيل أو الأوتوميتون في أي وقت في أحد الأوضاع، ويمكن تفعيلها من خلال «مُدخل» ما، يرمز
له بحرف من مجموعة حروف تعرف ﺑ «الأبجدية»؛ وهذا الحرف يرسل الأوتوميتون من وضع إلى
آخر. وبعد أن تؤثر سلسلة من الحروف (تسمى كلمة) على الأوتوميتون ، فسوف تكون الأوتوميتون إما في وضع قبول أو لا، حيث تأخذ سلسلة
الحروف المكونة ﻟ الأوتوميتون عبر سلسلة من الأوضاع. نقول إن الكلمة مقبولة من الأوتوميتون، أو تم التعرف عليها من الأوتوميتون، إذا ما
جعلت الأوتوميتون في وضع قبول. أما إذا لم تفعل، فإنها تكون مرفوضة، ونقول إن هذه
الكلمة ليست جزءًا من اللغة التي تتعرف عليها الأوتوميتون.
إذا شئت الانغماس في التشبيه بمصطلحات بشرية، يمكنك التفكير في أوضاع على أنها أمزجة، بحيث تكون أوضاع القَبول ممثلة للمزاج الجيد
للأوتوميتون، أما الأوضاع الأخرى فهي بمثابة مزاجها السيئ. فهي تستيقظ في مزاجها
المبدئي (الذي قد يكون جيدًا أو سيئًا، بناءً على شخصية الأوتوميتون الفردية) وتؤثر
عليها المدخلات التي تتعرض لها إما بجعلها في مزاج جيد أو سيئ. فإذا انتهى بها الأمر
في
مزاج جيد، فعندئذٍ قد قبلت الكلمة، ولكن إذا جعلتها الكلمة في مزاج سيئ، فإنها ترفضها.
على سبيل المثال، لنأخذ أبجدية بسيطة . ستكون هذه الأبجدية كافية دائمًا لأغراضنا، بل إن الحرفين يكفيان
لتوضيح معظم النظريات. في الأشكال ١٠-١٥ إلى ١٠-١٧
يطلق على الوضع المبدئي وأوضاع القبول مظللة. وتشير الأسهم على الأضلاع إلى كيفية تغيير
الحرف للأوتوميتون من وضع إلى آخر.
الأوتوميتون الموضحة في شكل ١٠-١٥ تتعرف على الكلمة شريطة أن
تحتويَ على حرف واحد على الأقل. فالكلمة المكونة من حروف فقط لا تنقل الأوتوميتون من وضعها المبدئي أبدًا. عند رؤية
الأوتوميتون للحرف فإنها تكون سعيدة وتظل في مزاجها الجيد (وضع القبول) أيًّا كان ما
تراه بعد ذلك.
شكل ١٠-١٥
الآلة التالية ليس من السهل إسعادها (شكل ١٠-١٦). فهي ستتعرف على
الكلمة فقط إذا تكونت من سلسلة من الحروف حتى الكلمة الفارغة (سلسلة من عدد صفر من ). على سبيل المثال، الكلمة ستنقل الآلة من الوضع المبدئي (وهو أيضًا وضع القبول الوحيد) للوضع ثم تعود مرة أخرى إلى الوضع المبدئي أربع مرات. وبما أن السلسلة السابقة تجعل الآلة تنتهي عند وضع
القبول، إذن فهي تتعرف على هذه الكلمة. ومع ذلك، بمجرد أن تكتشف أنها لا تحتوي على
سلسلة من الحروف فإنها تنتقل إلى وضع «التجاهل» ، الذي لا تتزحزح منه أبدًا. هذا سوف يحدث إذا بدأت الكلمة بالحرف ، أو إذا كانت الكلمة بها حرفان متتاليان متطابقان. أيٌّ من هذين
الحدثين كافٍ للإساءة للآلة لأنها ستكتشف أن الكلمة المُدخلة لها ليست في لغتها، وبعد
ذلك ستفقد الاهتمام كلية بكل ما يُدخل.
شكل ١٠-١٦
كمثال ثالث، أوجد اللغة المقبولة للأوتوميتون الصغيرة الموضحة في شكل ١٠-١٧. هذه الآلة تقبل الكلمة إذا — وفقط إذا — احتوت على المعامل ، على سبيل المثال، الكلمة تُقبل بينما لا تُقبل. في الحقيقة هذه أصغر أوتوميتون يمكن تصميمها لقبول هذه
اللغة الخاصة.
تعد نظرية الأوتوميتون أو الآلات ذاتية التشغيل من النظريات الهائلة ولها نظرية جبرية
خاصة بها، وهي تشكل جزءًا من موضوع يُعرف باسم «النظرية الجبرية لأشباه المجموعات».
وهناك العديد من التطبيقات في نظريات علوم الكمبيوتر وهذه النظرية نفسها شديدة الروعة.
فمثلًا لأي لغة معترف بها يوجد دائمًا أوتوميتون وحيدة وهي الصغرى التي تتعرف على اللغة . وتعتبر فئة اللغات المعترف بها نفسها قادرة على عدد من الخصائص
المتميزة، بعضها يقود إلى الفئة التي تظهر بشكل طبيعي في أماكن غير متوقعة.
شكل ١٠-١٧
بالنسبة لمن يرغب من القراء في التجريب، يمكنك أن تحاول رسم أوتوميتون تتعرف على
اللغات التالية: (١) الكلمات التي تحتوي على كعامل؛ (٢) الكلمات التي تحتوي على كلا الحرفين و؛ (٣) الكلمات التي تنتهي بالحرف . ويمكنك أن تختار ما تشاء، ولكن يجب أن تنتبه إلى أن الكثير من
اللغات البسيطة الموصوفة لا يتم التعرف عليها. على سبيل المثال، اللغة المكونة من كل
الكلمات التي تقرأ من اليمين ومن اليسار (مثل كلمة
radar وminim)،
ليست لغة لأي أوتوميتون: إذا كانت تتعرف على جميع الكلمات التي تُقرأ من اليمين ومن اليسار، فإنه يمكن
إثبات أنها من الضروري أن تتعرف على بعض الكلمات الأخرى التي لا تُقرأ من اليمين ومن
اليسار.
سوف أختم هذا ببرهان لمثل هذه اللغة غير المعترف بها وتسمح لنا باستخدام مبدأ برج
الحمام الذي قدمناه في السؤال رقم (٧) من الفصل السادس. المثال هو اللغة المكونة من كل الكلمات على الصورة ، أي جميع الكلمات و و و… (موجز القول أن مثل هذه الأوتوميتون لا يمكن الاعتداد بها، أو على
الأقل أنها تكون مقيدةً بعدد الأشياء التي يمكنها وضعها في أزواج.)
لنفترض أن هي الأوتوميتون التي تتعرف على جميع الكلمات في اللغة السابقة . وهذا ممكن جدًّا، ولكني سوف أبين أن ستكون مجبرة على التعرف على كلمات ليست من هذا النوع؛ ومن ثم فإن
اللغة المقترنة بالأوتوميتون ليست هي ولكنها مجموعات أكبر من الكلمات.
لكل عدد الكلمة سوف تأخذ من وضعها المبدئي إلى وضع آخر سوف نطلق عليه . بما أن مقبولة من قبل ، فإن الكلمة تأخذ من الوضع إلى وضع قبول آخر يطلق عليه . الآن بما أن لديها عدد محدود من الأوضاع ولكن هناك عددًا لا نهائيًّا من الأعداد ، ينتج عن ذلك أنه لا بدَّ من وجود عددين مختلفين، و مثلًا، بحيث يكون الوضعان و متطابقين بالرغم من اختلاف و.
في ضوء ذلك، انظر إلى الكلمة غير الموجودة في اللغة لأن . هذه الكلمة، رغم ذلك، يتم التعرف عليها بواسطة الأوتوميتون لأن تأخذ من الوضع المبدئي إلى ، ثم تأخذ من الوضع إلى وضع القبول المساوي له كما سبق.
