خلاصة الفصل

تمارين: مراجعة الفصل

1.

أيّ من الرسوم البيانية أدناه (إن وُجد) هي نفسها؟ وأيّها مختلفة؟ اشرح.

2.

أيّ من الرسوم البيانية في السؤال السابق يحتوي على مسالك أويلر (Euler trails) أو دوائر أويلر؟ وأيّ من هذه الرسوم البيانية مستوٍّ؟

3.

ارسم رسمًا بيانيًّا له دائرة أويلر (Euler circuit) ولكنّه ليس مستويًّا.

4.

ارسم رسمًا بيانيًّا لا يملك مسلك أويلر (Euler trail) وليس مستويًّا أيضًا.

5.

تأمّل الرسم البيانيّ $G = (V, E)$ حيث $V = \{a,b,c,d,e,f,g\}$ و$E = \{ab, ac, af, bg, cd, ce\}$ (هنا نستعمل اختصارًا للحوافّ: فـ $ab$ تعني في الحقيقة $\{a,b\}\text{,}$ مثلًا).

1. هل الرسم البيانيّ $G$ متناظرٌ مع $G' = (V', E')$ حيث $V' = \{t, u, v, w, x, y, z\}$ و$E' = \{tz, uv, uy, uz, vw, vx\}\text{?}$ وإن كان كذلك، فاذكر التناظر. وإن لم يكن كذلك، فاشرح كيف عرفت ذلك.
2. ابحث عن رسمٍ بيانيّ $G''$ فيه 7 رؤوس و6 حوافّ وليس متناظرًا مع $G\text{,}$ أو اشرح لماذا هذا غير ممكن.
3. اكتب تتابع الدرجات (degree sequence) لـ $G\text{.}$ أي اكتب درجات كل الرؤوس مرتّبةً تنازليًّا.
4. ابحث عن رسمٍ بيانيّ متّصل $G'''$ له تتابع الدرجات نفسه الذي لـ $G$ وليس متناظرًا مع $G\text{,}$ أو اشرح لماذا هذا غير ممكن.
5. ما نوع الرسم البيانيّ $G\text{?}$ هل $G$ كامل؟ ثنائيّ الأجزاء؟ شجرة؟ دورة؟ مسار؟ عجلة (wheel)؟
6. هل $G$ مستوٍّ؟
7. ما العدد اللوني (chromatic number) لـ $G\text{?}$ اشرح.
8. هل يملك $G$ مسلك أويلر أو دائرة أويلر؟ اشرح.

6.

إذا كان رسمٌ بيانيّ فيه 10 رؤوس و10 حوافّ ويحتوي على دائرة أويلر، فهل يجب أن يكون مستويًّا؟ وكم وجهًا سيكون له؟

7.

نفترض أنّ $G$ رسمٌ بيانيّ فيه $n$ رأسًا، لكلٍّ منها درجة 5.

1. لأيّ قيمٍ من $n$ يكون لهذا معنًى؟
2. لأيّ قيمٍ من $n$ يملك الرسم البيانيّ مسلك أويلر؟
3. ما أصغر قيمةٍ لـ $n$ يمكن أن يكون عندها الرسم البيانيّ مستويًّا؟ (مربِك)

8.

في حفلةٍ مدرسيّة، تتبادل 6 بناتٍ و4 أولادٍ الرقص (كأزواج) بعضهم مع بعض.

1. كم عدد الأزواج الذين يرقصون إذا رقصت كل بنتٍ مع كلّ ولدٍ؟
2. كم عدد الأزواج الذين يرقصون إذا رقص الجميع مع الجميع الآخرين (بغضّ النظر عن الجنس)؟
3. اشرح ما الرسوم البيانية التي يمكن استعمالها لتمثيل هذه الحالات.

9.

ضمن مجموعةٍ من $n$ أشخاص، هل يمكن أن يكون الجميع أصدقاءَ مع عددٍ فرديّ من أشخاص المجموعة؟ وإن كان ذلك ممكنًا، فماذا يمكنك أن تقول عن $n\text{?}$

10.

لقد تحدّاك صديقك إلى إنشاء متعدّد وجوهٍ محدّب (convex polyhedron) يحتوي 9 مثلثات و6 خماسيات.

1. هل يمكن بناء متعدّد وجوهٍ كهذا باستعمال هذه الأشكال فقط؟ اشرح.
2. قرّرتَ أيضًا أن تضمّ مضلّعًا سباعيًّا واحدًا (مضلّعًا ذا سبعة أضلاع). فكم عدد الرؤوس التي يحتويها متعدّد الوجوه المحدّب الجديد؟
3. بافتراض نجاحك في بناء متعدّد الوجوه الجديد ذي الستّة عشر وجهًا، هل يمكن أن يكون كل رأسٍ محلّ التقاء العدد نفسه من الأوجه؟ وهل يمكن أن يلتقي كل رأسٍ إمّا بثلاثة أو بأربعة أوجه؟ وإن كان ذلك ممكنًا، فكم عدد رؤوس كل نوع؟

11.

هل يوجد متعدّد وجوهٍ محدّب يحتاج إلى 5 ألوانٍ من أجل تلوين رؤوس المتعدّد تلوينًا سليمًا؟ اشرح.

12.

كم عدد الحوافّ التي يملكها الرسم البيانيّ $K_{n,n}$? ولأيّ قيمٍ من $n$ يحتوي الرسم البيانيّ على دائرة أويلر؟ ولأيّ قيمٍ من $n$ يكون الرسم البيانيّ مستويًّا؟

13.

للرسم البيانيّ $G$ ستّة رؤوسٍ بدرجات $1, 2, 2, 3, 3, 5\text{.}$ فكم عدد حوافّ $G$? ولو كان $G$ مستويًّا، فكم عدد أوجهه؟ وهل يملك $G$ مسلك أويلر؟

14.

ما أصغر عددٍ من الألوان اللازم لتلوين رؤوس $K_{7}\text{.}$ تلوينًا سليمًا؟ وهل يمكنك أن تقرّر، انطلاقًا من إجابتك، ما إذا كان $K_7$ مستويًّا؟

15.

ما أصغر عددٍ من الألوان اللازم لتلوين رؤوس $K_{3,4}\text{?}$ تلوينًا سليمًا؟ وهل يمكنك أن تقرّر، انطلاقًا من إجابتك، ما إذا كان $K_{3,4}$ مستويًّا؟

16.

اثبت أنّ $K_{3,4}$ ليس مستويًّا. وافعل ذلك باستعمال صيغة أويلر (Euler’s formula)، لا مجرّدًا بالاحتكام إلى الحقيقة القائلة إنّ $K_{3,3}$ ليس مستويًّا.

17.

اثنا عشريّ الوجوه (dodecahedron) متعدّدُ وجوهٍ منتظمٌ محدّب مكوَّنٌ من 12 خماسيًّا منتظمًا.

1. نفترض أنّك تلوّن كل خماسيّ بأحد ثلاثة ألوان. اثبت أنّه يجب أن يوجد خماسيّان متجاوران ملوَّنان باللون نفسه.
2. وماذا لو استعملت أربعة ألوان؟
3. وماذا لو، بدلًا من اثنا عشريّ الوجوه، لوَنْتَ أوجه مكعّب؟

18.

قرّر ما إذا كانت العبارات التالية صادقة أم خاطئة. واثبت إجاباتك.

1. إذا كان رسمان بيانيان $G_1$ و$G_2$ لهما العدد اللوني نفسه، فإنّهما متناظران.
2. إذا كان رسمان بيانيان $G_1$ و$G_2$ لهما عددُ الرؤوس وعددُ الحوافّ نفسه، وكان لهما العدد اللوني نفسه، فإنّهما متناظران.
3. إذا كان رسمان بيانيان متناظرَين، فإنّهما لهما العدد اللوني نفسه.

19.

إذا كان رسمٌ بيانيّ مستوٍّ $G$ فيه $7$ رؤوسٍ يقسم المستوى إلى 8 مناطق، فكم عدد الحوافّ التي يجب أن يملكها $G$؟

20.

تأمّل الرسم البيانيّ أدناه:

1. هل يملك الرسم البيانيّ مسلك أويلر أو دائرة أويلر؟ اشرح.
2. هل الرسم البيانيّ مستوٍّ؟ اشرح.
3. هل الرسم البيانيّ ثنائيّ الأجزاء؟ كامل؟ ثنائيّ الأجزاء كامل؟
4. ما العدد اللوني للرسم البيانيّ؟

21.

لكلّ جزءٍ أدناه، قل ما إذا كانت العبارة صادقة أم خاطئة. واشرح لماذا العباراتُ الصادقة صادقة، وقدّم أمثلةً مضادّةً للعبارات الخاطئة.

1. كل رسمٍ بيانيّ ثنائيّ الأجزاء مستوٍّ.
2. العدد اللوني لكل رسمٍ بيانيّ ثنائيّ الأجزاء هو 2.
3. كل رسمٍ بيانيّ ثنائيّ الأجزاء يملك مسلك أويلر.
4. كل رأسٍ في رسمٍ بيانيّ ثنائيّ الأجزاء له درجةٌ زوجية.
5. الرسم البيانيّ ثنائيّ الأجزاء إذا وفقط إذا كان مجموع درجات كل رؤوسه زوجيًّا.

22.

تأمّل العبارة: «إذا كان الرسم البيانيّ مستويًّا، فإنّه يملك مسلك أويلر.»

1. اكتب عكس العبارة.
2. اكتب عكس المقدم للعبارة.
3. اكتب نفي العبارة.
4. هل يمكن أن يكون عكس المقدم خاطئًا؟ وإن كان خاطئًا، فماذا يكون ذلك يخبرك؟
5. هل العبارة الأصلية صادقة أم خاطئة؟ اثبت إجابتك.
6. هل عكس العبارة صادقٌ أم خاطئ؟ اثبت إجابتك.

23.

لتكن $G$ رسمًا بيانيًّا متّصلًا فيه $v$ رأسًا و$e$ ضلعًا. استعمل الاستدلال الرياضي (mathematical induction) لإثبات أنّه إذا كان $G$ يحتوي على دورةٍ واحدةٍ بالضبط (من بين حوافّه ورؤوسه الأخرى)، فإنّ $v = e\text{.}$

ملاحظة. هذا يطلب منك إثبات حالةٍ خاصةٍ من صيغة أويلر (Euler’s formula) للرسوم البيانية المستوية، فلا تستعمل تلك الصيغة في برهانك.

تلميح. قد ترغب في تقديم البرهان على قسمين. أوّلًا اثبت بالاستدلال أنّ الدورة $C_n$ تحقّق $v=e\text{.}$ ثمّ تأمّل ما يحدث إذا كان الرسم البيانيّ أكثر من مجرّد الدورة.