مفاهيم أساسية
1-1 ما البيان؟
كيف نستطيع من أسلاك لشبكة من الهواتف بأقل تكلفة ممكنة، بحيث يمكن الوصول لأي هاتف من أي هاتف آخر؟ ما أسرع مسلك يربط العاصمة الوطنية ببقية عواصم الولايات الأخرى؟ كيف نستطيع ملء 11 من شواغر الوظائف بـ 11 من الأشخاص المؤهلين؟ ما أكبر معدل تدفق من المصدر لغمر شبكة من الأنابيب؟ كم تحتاج شريحة الحاسوب من حزم الأسلاك: بحيث لا تتقاطع هذه الأسلاك معا في الحزمة نفسها؟ كيف نستطيع أن نجدول الموسم الرياضي في أقل عدد ممكن من الأسابيع؟ ما الترتيب المناسب للمدن بحيث يستطيع مندوب المبيعات زيارتها في أقصر وقت ممكن؟ هل يمكن تلوين المناطق المختلفة في أي خريطة باستعمال أربعة ألوان على أن تكون ألوان المناطق المتجاورة مختلفة؟ تتضمن نظرية البيان هذه المسائل، وغيرها الكثير من المسائل العملية الأخرى، وفي هذا الكتاب، طورنا نظرية البيان وطبقناها على مثل هذه المسائل، ومنذ البداية، فإننا نفترض الإلمام بالخلفية الرياضية الموجودة في الملحق A، حيث إن هذا الملحق يناقش المفاهيم الأساسية، ولغة الرياضيات المستخدمة.
التعريف
إن المسألة التي غالبا ما يقال إنها ولدت نظرية البيان سوف تقترح تعريفنا الأساسي للبيان
1.1.1. مثال مسألة جسور كونجز برج (The Königsberg Bridge Problem). تقع مدينة كونجز برج على نهر بريجل (Pregel) في بروسيا، وتتكون هذه المدينة من جزيرة نيفوف (Kneiphopf)، ومساحات على ضفتي النهر. وقد وصلت هذه المناطق بسبعة جسور، كما هو على اليسار أدناه، وتساءل مواطنو المدينة عما إذا كان يمكنهم مغادرة منازلهم، والسير على كل جسر من الجسور السبعة مرة واحدة فقط، ثم العودة إلى منازلهم، وقد اختزلت المسألة على تتبع الشكل الأيمن، حيث تمثل النقاط الكثيفة الكتل اليابسة، أما المنحنيات فتمثل الجسور.
النموذج الذي عن اليمين يسهل تعليل عدم وجود مثل هذا الطريق، حيث نحتاج في كل مرة ندخل اليابسة ونخرج منها إلى استخدام جسرين ينتهيان بهذه اليابسة، وكذلك نستطيع أن نقرن الجسر الأول بالجسر الأخير حيث بدأنا وانتهينا لذلك، فإن وجود مثل هذا المسار المتعرج، يتطلب أن يكون عدد زوجي من الجسور على كل كتلة يابسة، وهذا الشرط الضروري غير متحقق في مدينة كونجز برج.
إن مسألة جسور كونجز برج تصبح أكثر متعة عندما نثبت في الدرس 2.1 أيا من الأشكال لها مسارات مستعرضة، وفي غضون ذلك، فإن هذه المسألة تقترح نموذجا عاما لمناقشة مثل هذه القضايا.
2.1.1. تعريف البيان (G graph) : ثلاثية تتكون من مجموعة رؤوس (vertex set) V (G) ، ومجموعة أضلاع (edge set) E(G)، وعلاقة ترافق كل ضلع مع رأسين ليس بالضرورة أن يكونا مختلفين يسميان نقاطا طرفية (endpoints).
نرسم البيان على ورقة بوضع كل رأس على نقطة، وتمثل كل ضلع بمنحنى يربط بين نقاطه الطرفية.
3.1.1. مثال في البيان في المثال 1.1.1 مجموعة الرؤوس هي X,Z,Y،W ومجموعة الأضلاع هي: (e1,e2,e3,e4,e5,e6,e7) ويمكن قراءة تعيين النقاط الطرفية للأضلاع من الصورة.
لاحظ أن الضلعين e1,e2 ، و لهما النقاط الطرفية نفسها وكذلك e3 و e4 وإذا كان هنالك جسر فوق مدخل، فإن نهايتيه سوف تكونان في الكتلة اليابسة نفسها، وترسمه بوصفه منحنى يبدأ بالنقطة نفسها وينتهي بها، وتوجد لدينا مفردات ملائمة لمثل هذه الأنواع من الأضلاع في البيانات.
4.1.1. تعريف نعرف الأنشوطة (loop) على أنها ضلع، نقاطه الطرفية متساوية. وتعرف الأضلاع المكررة (multiple edges) على أنها أضلاع لها الزوج نفسه من النقاط الطرفية.
ونعرف البيان البسيط (Simple graph) على أنه بيان لا عُرى ولا أضلاعًا مكررة، وتحدد البيان البسيط بمجموعة رؤوسه ومجموعة أضلاعه، وذلك بافتراض مجموعة الأضلاع بوصفها مجموعة من الأزواج غير المرتبة من الرؤوس، وكتابة e = uv للدلالة على الضلع و الذي تكون نقاطه الطرفية u و v وعندما تكون كل من u و v نقاطا طرفية لضلع ما، فإنها تدعى متجاورة ( adjacent) وتكونان جيرانا (neighbors) ونكتب v↔u بدلا من ""u"" متجاور مع ""v"" .
البسيطة. في هذه الحالة، يحدد الضلع بنقاطه الطرفية. لذا، تستطيع أن نسمي الضلع بنقاطه الطرفية، كما في التعريف 4.1.1. وهكذا، وفي البيان البسيط، فإننا ننظر إلى الضلع بوصفه زوج من الرؤوس غير المرتبة، نستطيع أن تهمل العلاقة التي ترافق النقاط الطرفية مع الأضلاع صوريا. ويركز هذا الكتاب على البيانات البسيطة.
5.1.1. مثال عن اليسار أدناه، تجد رسمين لبيان بسيط، حيث مجموعة الرؤوس هي (u,v,x,w,y) ومجموعة الأضلاع هي: (uv, uw, vx, vw, xw,xy ) .
ظهرت المفردتان رأس"" و ""ضلع"" من الهندسة الفراغية، أو هندسة المجسمات، حيث إن للمكعب رؤوسا وأضلاعا، وهي تشكل مجموعة كل من الرؤوس والأضلاع لبيان ما ، وقد رسم المكعب عن اليمين أدناه، وحذفت أسماء الرؤوس والأضلاع.
يكون البيان محددًا (Finite) إذا كانت مجموعة كل من رؤوسه وأضلاعه منتهيتين. وعليه سنتبني الاصطلاح الآتي: كل بيان يذكر في هذا الكتاب هو بيان منته، إلا إذا ذكر خلاف ذلك بصورة صريحة.
6.1.1. * ملاحظة . البيان الخالي (null graph) هو البيان الذي تكون مجموعة كل من الرؤوس والأضلاع فيه خاليتين، لاحظ أن تمديد المثبتات أو تعميمها لتنطبق على البيان الخالي يقود إلى إرباك لا داعي له، لذلك ستهمله. وفي العبارات والتمارين كلها سوف نأخذ في الحسبان البيانات التي لها مجموعة غير خالية من الرؤوس فقط.
البيانات بوصفها نماذج
تظهر البيانات في أوضاع كثيرة، وتوحي التطبيقات لنا بأفكار ومصطلحات مفيدة حول بناء البيانات
7.1.1. مثال علاقات المعارف الشخصية والبيانات الجزئية. هل كل مجموعة مكونة من ستة أشخاص تحوي ثلاثة أشخاص بعضهم على معرفة شخصية مسبقة ببعض، أو ثلاثة أشخاص غرباء غير متعارفين؟ بما أن علاقة المعرفة الشخصية متماثلة، فإننا ننمذجها باستعمال بيان بسيط، حيث يمثل كل رأس شخصا ، وكل ضلع يمثل شخصين يعرف أحدهما الآخر، بالإضافة إلى أن علاقة عدم المعرفة الشخصية على مجموعة الرؤوس نفسها تعطي بيانا آخر، أضلاعه متممة"" مجموعة الأضلاع الأصلية. وسنعطي مصطلحات لهذه المفاهيم.
تعريف نقول: إن البيان G ثنائي الفرع (bipartite) إذا كانت مجموعة رؤوسه (G) اتحادا المجموعتين منفصلتين قد تكون إحداهما خالية مستقلتين تسميان مجموعات تجزئة للبيان G أو مجموعات مجزأة للبيان (G).
11.1.1. مثال الجدولة وتلوين البيانات (Scheduling and graph coloring). افترض أننا نريد أن نجدول اجتماعات لجان مجلس الشيوخ بصورة دورية في كل أسبوع، حيث لا نستطيع أن نجدول لجنتين في الوقت نفسه إذا كان فيهما عضو مشترك. فكم دورة زمنية مختلفة نحتاج إليها ؟
نضع رأسًا لكل لجنة، بحيث يكون الرأسان متجاورين عندما يكون هنالك عضو مشترك في اللجنتين المقابلتين لهذين الرأسين، ونضع عناوين للفترات الزمنية) للرؤوس، بحيث يكون للنهايات الطرفية للأضلاع عناوين مختلفة. وفي البيان أدناه، نستطيع أن نستعمل عنوانا واحدًا لكل مجموعة من المجموعات الثلاث المستقلة ذوات الرؤوس المجمعة بعضها بالقرب من بعض، ويجب أن يعطى الأعضاء في العصبة عناوين مختلفة، لذلك وفي هذا المثال يكون أقل عدد ممكن من الفترات الزمنية هو ثلاث.
وبما أننا مهتمون بتجزئة الرؤوس فقط، وأن العناوين لا تحمل قيما عددية، فإنه من المناسب أن نسميها ألوانا (Colors).
.12.1.1. تعريف تعرف العدد اللوني Chromatic number للبيان ، يرمز إليه بالرمز (G) على أنه أقل عدد ممكن من الألوان نحتاج إليه لتلوين الرؤوس، بحيث تكون ألوان الرؤوس المتجاورة مختلفة. ويسمى البيان G (متعدد الفروع مجزأ) من الدرجة (k-partite) إذا كان بالإمكان كتابة (G) على صورة اتحاد من المجموعات المستقلة (ربما بعضها خال)
هذا يعمم فكرة البيانات الثنائية الفرع، وهي مجزأة من الدرجة 2 يجب أن تشكل. إن الرؤوس التي أعطيت اللون نفسه مجموعة مستقلة. لذلك، فإن (G) X هو أقل عدد ممكن من المجموعات المستقلة نحتاج إليه لتجزئة (G) X ، ويكون البيان متعدد الفروع ( مجزأ ) من الدرجة ) إذا وفقط إذا كان عدده اللوني يساوي على الأكثر، وقد استخدمنا المصطلح مجموعة مجزأة عندما نتحدث عن مجموعة في تجزئة المجموعة معينة إلى مجموعات مستقلة.
سندرس العدد اللوني وتلوين البيانات في الفصل 5. لاحظ أن المسألة الأكثر شهرة في نظرية البيان هي تلوين الخرائط"".
13.1.1. مثال الخرائط والتلوين (Maps and coloring) . بكلام غير دقيق، الخريطة هي تجزئة للمستوى إلى مناطق مترابطة، فهل بالإمكان تلوين المناطق في أي خريطة باستخدام أربعة ألوان على الأكثر، بحيث يكون للمناطق المتجاورة ألوان مختلفة؟
لربط تلوين الخرائط بتلوين البيانات، نضع رأسًا يمثل كل منطقة، وضلعا لتمثيل المناطق التي تتشارك بالحدود، ونتساءل في مسألة الخريطة عما إذا كان العدد اللوني للبيان الناتج يساوي 4 على الأكثر لاحظ أنه يمكن رسم بعض البيانات في المستوى دون أن تتقاطع أضلاعها مثل هذه البيانات تسمى بيانات مستوية (planar) والبيان الذي يسبق التعريف 12.1.1 هو بيان سوي لاحظ كذلك وجود تقاطعات في هذا الرسم، ولكن هنالك رسما آخر ليس فيه تقاطعات سندرس البيانات المستوية في الفصل السادس.
14.1.1. مثال المسالك في شبكات الطرق (Routes in road networks) . نستطيع أن تنمذج شبكة الطرق باستخدام بيان أضلاعه التي تقابل قطع الطرق بين التقاطعات، وتستطيع أيضًا أن نعين أوزانا للأضلاع لقياس المسافة أو زمن الرحلة، وفي هذا السياق، لاحظ أن الأضلاع تمثل الروابط الفيزيائية ( الطبيعية) . فكيف نستطيع أن نجد أقصر مسلك من x إلى 5 سنبين كيفية حساب هذا في الفصل الثاني.
إذا كانت الرؤوس في البيان تمثل منزلنا والأماكن الأخرى المراد زيارتها ، فلربما نريد أن نتبع مسلكا نزور من خلاله الرؤوس جميعها مرة واحدة بالضبط ، كزيارة كل شخص دون المكوث عنده. وسنأخذ في الحسبان وجود مثل هذا المسلك في الفصل السابع.
لاحظ أننا نحتاج إلى مصطلحات لوصف هذين النوعين من المسالك في البيانات.
15.1.1. تعريف المسار (path) هو بيان بسيط يمكن ترتيب رؤوسه، بحيث يكون الرأسان متجاورين إذا وفقط إذا كانا متتاليين في القائمة. أما الحلقة (cycle) ، فهي بيان يتساوى فيه عدد كل من الرؤوس والأضلاع، ومن الممكن وضع رؤوسه حول دائرة بحيث يكون الرأسان متجاورين إذا وفقط إذا ظهرا متتالين على الدائرة.
لاحظ أن الشكل أعلاه يظهر مسارا وحلقة، كما هو موضح من جدولة الرؤوس بحسب الترتيب: x,b,a,z,y فضلا عن أن إهمال ضلع واحد من الحلقة ينتج مسارا. وفي دراسة المسالك في شبكات الطرق. نفكر في المسارات والحلقات المحتواة في البيان. كذلك نأمل في الوصول إلى كل رأس في الشبكة من أي رأس آخر والتعريف الآتي يجعل هذه المفاهيم دقيقة.
المصفوفات والتشاكل
كيف تحدد بيانا ما؟ نستطيع وضع الرؤوس والأضلاع في قائمة ( مع النقاط الطرفية) ، ولكن هناك تمثيلات مفيدة أخرى، يضاف إلى ذلك أن قولنا إن البيان عديم أشواط أو خال منها (loopless) يعني أن الأضلاع المكررة مسموحة، ولكن أشواطا غير مسموحة.
17.1.1. تعريف:ليكن G بيانا عديم أشواط، بحيث إن مجموعة رؤوسه هي: VG= V1.....Vn ومجموعة أضلاعه هي: EG= E1...EN تعرف مصفوفة التجاور (adjacency matrix) للبيان G ، وتكتب (G) A على أنها هي المصفوفة من الحجم n×n. حيث تكون المدخلة ai,j هي عدد الأضلاع في G التي نقاطها الطرفية vi,vj . أما مصفوفة الوقوع (incidence matrix) mg فتعرفها على أنها المصفوفة من الحجم n×m بحيث تكون المدخلة هي mi,j إذا كانت نقطة طرفية للضلع ej وبخلاف ذلك تكون 0
إذا كان الرأس v نقطة طرفية للضلع e ، فإنّ v و e تقع إحداهما على الأخرى (incident)، ونعرف درجة (degree) الرأس v في البيان عديم العرى على أنها عدد الأضلاع الواقعة على هذا الرأس. تعتمد الطريقة المناسبة لتعريف مصفوفة كل من التجاور والوقوع، أو درجات الرؤوس للبيان الذي يحوي عرى على التطبيق؛ لاحظ أن الدرسين 2.1 و 3.1 يناقشان ذلك.
19.1.1. مثال. للبيان G أدناه الخالي من العرى، نجد مصفوفة كل من التجاور والوقوع الناتجتين عن ترتيب الرؤوس x،z,y,w وترتيب الأضلاع : a و b و c و d و e ، حيث إن درجة الرأس y هي 4 ، وذلك من النظر إلى البيان، أو من جمع الصف لـ y في أي من المصفوفتين.
إن إيجاد مصفوفة التجاور لبيان ما يعطي ضمنيا تسمية للرؤوس بحسب ترتيب الصفوف؛ فالرأس i يقابل الصف والعمود i إذ تخزين بيان في الحاسوب يتطلب تسمية الرؤوس.
ومع ذلك، نريد أن ندرس الخصائص ( مثل خاصية الترابط) التي لا تعتمد على هذه الأسماء. حدسيا، إن الخصائص البنيوية لـ G و H ستكون هي نفسها إذا استطعنا إعادة تسمية الرؤوس في G باستخدام الرؤوس في H. وهكذا، فإن G سوف يصبح .H. ونجعل التعريف مضبوطا للبيانات البسيطة ، لاحظ أن إعادة التسمية هي دالة من V)G) إلى (H) ، بحيث يحدّد كل عنصر في (H) لعنصر واحد في (G) . لذلك نقرنهما في صورة أزواج، وتكون مثل هذه الدالة مقابلة واحدًا لواحد (one-to-one correspondence) ، أو تناظرا (bijection) ( انظر الملحق (A) . وعندما نقول : نقلب إعادة التسمية G إلى H ، فإنّ هذا يماثل قولنا إن تناظر الرؤوس يحافظ على علاقة التجاور.
تعريف. صف التشاكل (Isomorphism class) للبيان، هو صف تكافؤ للبيانات تحت علاقة التشاكل، وتتشاكل المسارات على n من الرؤوس زوجا زوجًا ؛ لذا فإن مجموعة المسارات على n من الرؤوس تشكل صف تشاكل.
ملاحظة : البيانات غير الموسومة وصفوف التشاكل. عند مناقشة البيان G، يكون لدينا مجموعة ثابتة من الرؤوس، لكن تعليقاتنا البنيوية تُطبّق أيضًا على كل بيان متشاكل مع G، وتكون استنتاجاتنا مستقلة عن أسماء (أوسمة ) الرؤوس. وهكذا ، نستخدم التعبير غير الرسمي "" البيانات غير الموسومة، ليعني صف التشاكل للبيانات. عندما نرسم بيانًا ، فإن رؤوسه تسمى بمواقعها الفيزيائية، حتى لو لم نعطها أسماء أخرى. لذا فإنّ رسم البيان يكون عضوا في صفه التشاكلي، وندعوه بيانا فقط، وعندما نعيد رسم بيان لإظهار بعض أوجهه البنيوية فإننا نختار أنسب عضو في صف التشاكل، ونبقى نناقش "" البيان غير الموسوم نفسه.
حينما نناقش بنية البيانات، فمن المناسب أن نستعمل أسماء ورموزًا لصفوف التشاكلات المهمة، وحيث يجب أن تكون هنالك مرونة في الرجوع إلى صف التشاكل أو لأي عنصر يمثله.
تعريف. يرمز إلى المسار ( غير الموسوم) أو الحلقة على n من الرؤوس بالرمزين Pn و Cn، على الترتيب والحلقة n-1 هي حلقة على n من الرؤوس. ونعرف البيان التام (complete graph) على أنه بيان بسيط، رؤوسه متجاورة زوجا زوجًا ؛ ويرمز إلى البيان التام (غير الموسوم) على n من الرؤوس بالرمز Kn ، أما البيان الثنائي الفرع التام (complete bipartite graph) أو الثنائي العصبة (biclique) فيعرّف على أنه بيان ثنائي الفرع بسيط، بحيث يكون أي رأسين فيه متجاورين إذا وفقط إذا كانا في مجموعات مجزأة ( جزئية ) مختلفة. وعندما يكون حجم المجموعتين r و s، فإننا نستخدم الرمز Krs للعصبة الثنائية (غير الموسومة)
* ملاحظة : عرفنا البيان التام بوصفه بيانًا رؤوسه متجاورة زوجا زوجًا، أما العصبة فهي مجموعة الرؤوس المتجاورة زوجًا زوجًا في البيان. حيث يستعمل الكثير من المؤلفين المصطلحين بصورة متبادلة، ولكن الاختلاف يسمح لنا بمناقشة العصب باستخدام لغة المجموعات المستقلة نفسها.
في إطار ثنائي الفرع، نستخدم ببساطة ""عصبة لنختصر البيان الثنائي الفرع التام. إن الاسم البديل ثنائي العصبة، هو تذكير بأن البيان الثنائي الفرع التام لا يكون بيانا تاما بوجه عام
التفكيك والبيانات الخاصة
تعريف. يكون البيان ذاتي التتام (self - complementary) إذا كان متشاكلاً مع متممته. ويعرف تفكيك (decomposition) البيان على أنه قائمة من البيانات الجزئية، بحيث يظهر كل ضلع مرة واحدة بالضبط في إحدى البيانات الجزئية في القائمة.
يكون البيان H على n رأسًا ذاتي التتام إذا وفقط إذا وجد لـ K تفكيك يتكون من نسختين من H.
تعريف بيان بيترسون (Petersen graph) هو البيان البسيط الذي تكون رؤوسه مجموعات جزئية ثنائية العناصر من مجموعة خماسية العناصر، في حين تكون أضلاعه أزواج المجموعات الجزئية الثنائية العناصر المنفصلة.رسمنا في الأعلى بيان بيترسون بثلاث طرق، إذ إنّ هذا البيان مفيد جدًّا في كثير من الأحيان لدرجة أنه خُصِّصَ كتاب بأكمله له ([1993] Holton-Sheehan)، وعلاوة على أن خصائصه تستنبط من علاقة التجاور التي استخدمت بوصفها تعريفا له.
مثال : تركيب ( بنية) بيان بيترسون باستخدامنا [5] = {5 ،4 ،3 ،2 ،1) بصفتها مجموعة خماسية العناصر، نكتب الزوج في صورة ab ، أو ba ، وبما أن 12 و 34 منفصلان، لهذا تكون هذه الرؤوس متجاورة عند تشكيل البيان، أما 12 و 23 فليسا كذلك. لاحظ أنه لكل مجموعة ثنائية ab، هنالك ثلاث طرق لاختيار مجموعة ثنائية العناصر من العناصر الثلاثة المتبقية في [5] . لذلك فإن درجة كل رأس 3 يتكون بيان بيترسون من حلقتين منفصلتين على 5 رؤوس إضافة إلى أضلاع لربط الرؤوس في هاتين الحلقتين. ومن تعريف خاصية الانفصال، نجد أن 12 ، 34 ، 51 ، 23 ، 45 على الترتيب، هي رؤوس لحلقة على 5 رؤوس، وبطريقة مشابهة تضبط بقية الرؤوس 13 ، 52 ، 41 ، 35 ، 24. لاحظ أيضًا أن 13 يكون متجاورا مع 45 في حين يكون 52 متجاورًا مع 34 ، وهكذا دواليك ، كما هو مبين على اليسار في الأعلى.
نستخدم هذا الاسم حتى عندما لا نعين عناوين الرؤوس؛ وفي الأساس، نستخدم بيان بيترسون بوصفه اسما لصف تشاكل. ولنبين أن البيانات في الأعلى متشاكلة معا زوجا زوجًا، فيكفي أن نسمي الرؤوس في كل بيان باستخدام مجموعات فرعية ثنائية العناصر من [5] ، وحيث تكون علاقة التجاور في كل حالة هي خاصية الانفصال .
قضية : إذا كان هنالك رأسان غير متجاورين في بيان بيترسون فإنه يوجد لهما بالضبط جار مشترك واحد فقط.
الإثبات: الرؤوس غير المتجاورة مجموعات ثنائية تتشارك في عنصر واحد؛ وحجم اتحادهما . يساوي 3 إضافة إلى أن الرأس المجاور لهما هو مجموعة ثنائية منفصلة عن كليهما، وبما أننا نختار المجموعات الثنائية من { 5 ،4 ،3 ،2 ،1 ، فتوجد مجموعة ثنائية واحدة بالضبط منفصلة عن S.
تعريف: نُعرّف الخصر (girth) للبيان الذي يمتلك حلقة على أنه طول أقصر حلقة في هذا البيان، أما البيان الذي ليس فيه حلقات فيكون خصره لا نهائيا.
نتيجة:خصر بيان بيترسون يساوي 5.
الاثبات: هذا البيان بسيط. ولذلك، ليس له حلقة على رأس واحد ولا حلقة على رأسين، لاحظ أن الحلقة على ثلاثة رؤوس تتطلب ثلاثة أزواج من المجموعات الثنائية المنفصلة زوجًا زوجا، وهذا لا يمكن حدوثه بين 5 عناصر ، لاحظ أن الحلقة على أربعة رؤوس في غياب حلقة على ثلاثة رؤوس تتطلب رؤوسا غير متجاورة مع رأسين جارين مشتركين، وهذا ما تمنعه القضية 38.1.1. وفي النهاية، نجد أن الرؤوس 12 ، 34 ، 51 ، 23 ، 45 تعطينا حلقة خماسية، وبذلك يكون الخصر 5.
إن بيان بيترسون متماثل بشدة؛ حيث إنّ كلّ تبديلة من( 5 ،4 ،3 ،2 ،1) تولد تبديلة على المجموعات الجزئية الثنائية، وتحافظ على علاقة خاصية الانفصال. وعليه، فيوجد على الأقل 5 = 120 تشاكلا من بيان بيترسون إلى نفسه، ويؤكد التمرين 43 أنه لا يوجد غيرها.
تعريف: التشاكل الذاتي (Automorphism) للبيان G ، هو تشاكل من G إلى G. يكون البيان G متعدي الرؤوس (Vertex-transitive ) إذا وجد لكل زوج (G) V , تشاكل ذاتي يرسل u إلى v . لاحظ أن التشاكلات الذاتية لـ G هي التباديل لـ (G) V التي يمكن تطبيقها على كل من صفوف (G) A وأعمدتها دون أن تغيّر (G) A .
في البيان متعدي الرؤوس، نستطيع أن نثبت عبارة ما حول كل رأس بإثبات تلك العبارة لرأس واحد ؛ لأن هذه الخاصية تضمن أن البيان "" يشبه بعضه بعضا عند كل رأس.
