1- حدد أي البيانات الثنائية الفرع التامة هي بيانات تامة.
2- اكتب الاحتمالات الممكنة جميعها لمصفوفات التجاور، و مصفوفات الوقوع للمسارات التي لها ثلاثة رؤوس. و اكتب مصفوفة تجازر لمسار له ستة رؤوس، و لحلقة لها ستة رؤوس
3- باستخدام القوالب المستطيلة التي تكون مدخلاتها جميعها متساوية، اكتب مصفوفة التجاور ل Kmn.
4- أثبت أو انقض ما يأتي : إذا كانت درجة كل رأس في بيان بسيط G تساوي 2، فإن G يكون حلقة.
5- أثبت أن البيان الذي له أكثر من ستة رؤوس ذات درجة فردية، لا يمكن أن يتفكك إلى ثلاثة مسارات
6- أثبت أو انقض ما يأتي : يجب أن تكون متممة البيان البسيط غير المترابط بيانا مترابطا.
7- حدد ما إذا كان بيان بيترسون ثنائي الفرع، وجد حجم أكبر مجموعة مستقلة لهذا البيان.
8- ليكن G البيان الذي تكون مجموعة رؤوسه هي المرتبات من الدرجة k و إحداثياتها مأخوذة من المجموعة [0.1]، بحيث إن x يجاور y عندما يختلفان في موقع واحد بالضبط. حدد ما إذا كان G بيانا ثنائي الفرع.
9- أثبت أن إزالة الزوايا المربعة المائلة من لوحة الفاحص التي حجمها 8 في 8 تترك لوحة جزئية، لا يمكن تجزئتها إلى مستطيلات من الحجم 2X1 و 1X2. و باستخدام التعليل نفسه، جد عبارة عامة حول البيانات الثنائية الفرع جميعها.
10- خذ العائلات الأربع للبيانات الآتية في الحسبان : A = [مسارات]، B = [حلقات]، C = [بيانات تامة] D = [بيانات ثنائية الفرع]. لكل زوج من هذه العائلات، حدد صفوف التشاكلات جميعها للبيانات التي تنتمي إلى عائلتين.
11- حدد عدد صفوف التشاكل للبيانات البسيطة التي لها سبعة رؤوس، بحيث تكون درجة كل رأس 4.
12- في كل صف أدناه، حدد أقل عدد ممكن n بحيث توجد بيانات غير متشاكلة لها n من الرؤوس، و لها القائمة نفسها من درجات الرؤوس : أ) البيانات جميعها. ب) البيانات التي لا تحوي عرى ج) البيانات البسيطة. (مساعدة : بما أن كل صف يحوي الصف الذي يليه، فإن الإجابات تشكل ثلاثية غير متناقصة. للفرع (ج)، استخدم قائمة صفوف التشاكلات في المثال 31.1.1)
13- أثبت أنه لا توجد لبيان بيترسون حلقة طولها 7.
14- ليكن G بيانا خصره 4، بحيث تكون درجة كل رأس من رؤوسه k. أثبت أنه يوجد ل g على الأقل 2k رأسا، و حدد مثل هذه البيانات جميعها التي لها 2k رأسا بالضبط.
15- ليكن G بيانا خصره 5، أثبت أنه إذا كانت درجة كل رأس في G تساوي k على الأقل، فإن ل G على الأقل k2+1 رأسا. و عندما k = 2 و k = 3، جد بيانا واحدا له k2 + 1 رأسا بالضبط.
16- أثبت أن كل مجموعة من سنة أشخاص تحوي (على الأقل) ثلاثة أشخاص متعارفين تماما أو ثلاثة أشخاص غرباء تماما.
17- حدد أي ثنائي العصب يتفكك إلى بيانين جزئيين متشاكلين ؟
18- فكك بيان بيترسون إلى ثلاثة بيانات جزئية مترابطة بحيث تكون متشاكلة زوجا زوجا، و كذلك فككه إلى نسخ من P4.
19- أثبت أن Kn يتفكك إلى ثلاثة بيانات جزئية متشاكلة زوجا زوجا، إذا وفقط إذا كان n+1 لا يقبل القسمة على 3. (مساعدة : للحالة حيث n تقبل القسمة على 3، قسم الرؤوس إلى ثلاث مجموعات متساوية الحجم).
20- أثبت أنه إذا كان Kn يتفكك إلى مثلثات، فإن n – 1 أو n – 3 تقبل القسمة على 6
21- ليكن G بيانا بحيث تكون درجة كل رأس فيه 3. أثبت أن G لا يتفكك إلى مسارات لكل منها خمسة رؤوس على الأقل.
22- ليكن G بيانا بسيطا، بحيث تكون درجة كل رأس فيه تساوي 3. أثبت أن G يتفكك إلى مخالب إذا و فقط إذا كان G ثنائي الفرع.
23- تحقق من أن مجموعات التشاكلات الذاتية g تملك الخصائص الآتية : a) تركيب تشاكلين ذاتيين هو تشاكل ذاتي. b) التبديل المحايد تشاكل ذاتي. c) معكوس التشاكل الذاتي أيضا تشاكل ذاتي. d) تركيب التشاكلات الذاتية يحقق الخاصية التجميعية. (تعليق : لذلك فإن مجموعة التشاكلات الذاتية تحقق خصائص الزمرة).
24- 1. التشاكلات الذاتية لبيان بيرستون، لنأخذ بيان بيترسون كما عرف بخاصية الانفصال للمجموعات الثنائية من [5، 4، 3، 2، 1]. أثبت أن كل تشاكل ذاتي يرسل الحلقة ذات الرؤوس 45، 23، 51، 34، 12 إلى الحلقة ذات الرؤوس ab, cd, ea, bc, de يحدد بتبديل للمجموعة [5، 4، 3، 2، 1] و الذي يأخذ 5، 4، 3، 2، 1 إلى a, b, c, d, e على الترتيب. (تعليق : هذا يؤدي إلى أنه يوجد 120 تشاكلا ذاتيا).
25- أثبت أن يوجد للبيان الثنائي الفرع تجزئة ثنائية فريدة (ما عدا تبديل مجموعتي التجزئة) إذا و فقط إذا كان مترابطا.
26- حدد ما إذا كان K4 يحوي التالي (أعط مثالا أو أثبت عدم الوجود) : a) ممرا ليس مسربا. b) مسربا غير مغلق و ليس مسارا. c) مسربا مغلقا و لكنه ليس حلقة.
27- ليكن G البيان الذي مجموعة رؤوسه [15،...،1]، بحيث يكون i و j متجاورين إذا وفقط إذا كان أكبر عامل مشترك لهما يتجاوز العدد 1. احسب عدد مركبات G، و حدد أكبر طول لمسار في G.
28- ليكن v رأسا في البيان البسيط المترابط G. أثبت أنه يوجد ل v جار في كل مركبة ل G-v، و استنتج أنه لا يوجد بيان له رأس قطع من الدرجة 1.
29- أثبت أنه يوجد للبيان الثنائي الفرع تجزئة ثنائية فريدة (ما عدا تبديل مجموعتي التجزئة) إذا وفقط إذا كان مترابطا.
30- حدد قيم m و n بحيث يكون Km,n أويلريا.
31- ما أقل عدد ممكن من المسارب نحتاج إليه لتفكيك بيان بيترسون ؟ هل يوجد تفكيك لهذه المسارب باستخدام مسارات فقط ؟
32- أثبت أو انقض : a) يمتلك كل بيان أويلري ثنائي الفرع عدد زوجيا من الأضلاع. b) يمتلك كل بيان أويلري بسيط عدد رؤوسه زوجي عدد زوجيا من الأضلاع.
33- أثبت أو انقض : إذا كان G بيانا أويلريا يشترك فيه الضلعان e, f برأس، فتوجد في G حلقة أويلرية يظهر فيها الضلعان e, f برأس، فتوجد في G حلقة أويلرية يظهر فيها الضلعان e, f بصورة متتابعة.
34- حول الإثبات المعطى في المفردة 1.2.32 إلى طريقة لإيجاد حلقة أويلرية في البيان الزوجي المترابط.
35- براهين بديلة لإثبات أن كل ممر من u إلى v يحوي مسارا من u إلى v (البديهية 5.2.1) : a) (استقرار عادي) إذا أعطيت أن كل ممر طوله 1-I يحوي مسارا من رأسه الأول إلى رأسه الأخير، فأثبت أن كل ممر طوله I يحقق هذا أيضا. b) (مبدأ القيم القصوى) إذا أعطيت الممر W من u إلى v، فخذ أصغر ممر من u إلى v محتوى في W.
36- أثبت أو انقض العبارات الآتية حول البيانات البسيطة : (تعليق : "مختلفة" لا تعني "منفصلة"). a) اتحاد مجموعات الأضلاع لممرات مختلفة من u إلى v يجب أن يحوي حلقة. b) اتحاد مجموعات الأضلاع لمسارات مختلفة من u إلى v يجب أن يحوي حلقة.
37- ليكن W ممرا مغلقا طوله 1 على الأقل و لا يحوي حلقة. أثبت أن بعض أضلاع W تتكرر مباشرة (مرة واحدة في كل اتجاه). ليكن ᵨ ضلعا يظهر عدد فرديا من المرات في الممر المغلق W. أثبت أن W يحتوي على أضلاع لحلقة ما خلال ᵨ.
38- ليكن G هو البيان الذي تتكون فيه مجموعة الرؤوس من المرتبات من الدرجة k التي مدخلاتها من المجموعة [1،0]، بحيث يكون x مجاورا ل y إذا كان كل من x و y يختلفان بالضبط في موقعين فقط. حدد عدد المركبات ل G.
39- ليكن G بيانا ذاتي التتام. أثبت أن ل G رأس قطع إذا وفقط إذا كان ل G رأس درجته 1. (Akiyama-Harary [1981])
40- أثبت أن البيان يكون مترابطا إذا و فقط إذا وجد لكل تجزئة لرؤوسه إلى مجموعتين غير خاليتين ضلع نقاطه الطرفية في كلتا المجموعتين
41- لكل عبارة أدناه، حدد ما إذا كانت العبارة صحيحة لكل بيان بسيط مترابط غير تام G. كل رأس في G ينتمي إلى بيان جزئي محدث متشاكل مع P3.
42- لكل عبارة أدناه، حدد ما إذا كانت العبارة صحيحة لكل بيان بسيط مترابط غير تام G. كل ضلع في G ينتمي إلى بيان جزئي محدث متشاكل مع P3.
43- ليكن G بيانا بسيطا ليس فيه رأس معزول، و بيس فيه بيان جزئي محدث بضلعين فقط، أثبت أن G بيان تام.
44- استخدم الاستقراء العادي على عدد الأضلاع أو الرؤوس لإثبات أن غياب الحلقات الفردية يكون شرطا كافيا ليكون البيان ثنائي الفرع.
45- أثبت أن البيان G يكون ثنائي الفرع إذا و فقط إذا أوجد لكل بيان جزئي H من G مجموعة مستقلة تتكون على الأقل من نصف V(H).
46- ليكن G بيانا بسيطا لا يحوي P4 أو C3 كبيان جزئي محدث. أثبت أن G هو عصبة ثنائية (بيان ثنائي الفرع تام).
47- ليكن G بيانا بسيطا رؤوسه v1,…, vn، و لتكن Ak ترمز إلى القوة k المصفوفة التجاور ل G تحت عملية ضرب المصفوفات. أثبت أن المدخلة I, j في Ak هي عدد المرات من vi إلى vj التي طولها K في Ġ. و أثبت أن G ثنائي الفرع إذا و فقط إذا تحقق أنه لكل عدد صحيح فردي r قريب جدا من n، فإن مدخلات القطر جميعها تكون أصفارا في Ar. (تذكير : الممر هو قائمة مرتبة من الرؤوس و الأضلاع).
48- العبارة الآتية غير صحيحة. أضف فرضية لتصحيحها، و أثبت العبارة المصححة. "كل مسرب أعظمي في بيان زوجي هو حلقة أويلرية".
49- استخدم الاستقراء العادي على k أو على عدد الأضلاع (واحدا بعد الآخر) ؛ لإثبات أن البيان المترابط على 2k من الرؤوس الفردية بتفكك إلى k مسربا إذا كان k>0. هل هذه النتيجة تبقى صحيحة دون فرضية خاصية الترابط ؟
50- خوارزمية توكر. (Tuckers algorithm) افترض أن G بينا زوجي مترابط. عند كل رأس، اعمل تجزئة للأضلاع المرتبطة بهذا الرأس إلى أزواج (كل ضلع يظهر في زوج لكل نقطة طرفية فيه)، ابدأ مع ضلع ᵨ لتشكل مسربا (Trail) بمغادرة كل رأس على الضلع الذي يشكل زوجا مع الضلع المستخدم لدخول هذا الضلع، منتهيا بالضلع الذي يشكل زوجا مع ᵨ، و هذا يحلل G إلى مسارب مغلقة، ما دام يوجد أكثر من مسرب في هذا التحليل، جد مسربين لهما رأس مشترك، ثم ضمهما أحدهما إلى الآخر لتحصل على مسرب واحد أطول بتغيير المزاوجة (Pairing) عند رأس مشترك. و أثبت أن هذه الخطوات تعمل و تعطي حلقة أويلرية كمسربها النهائي (Tucke [1976]).
51- استخدم مفهوم الدرجة القصوى (extremality) لإثبات أن علاقة الربط هي علاقة تعد (مساعدة : إذا أعطيت ممرين p من u إلى v، و Q من v إلى w، فخذ في الحسبان أول رأس من P في Q).
52- أثبت أن كل بيان على n من الرؤوس، و عدد أضلاعه يساوي n على الأقل يجب أن يحوي حلقة طولها زوجي. (مساعدة : خذ في الحسبان أكبر مسار) (P.Kwok).
53- أثبت أن كل بيان على n من الرؤوس، و عدد أضلاعه يساوي n على الأقل يجب أن يحوي حلقة.
54- افترض أن G بيان خال من العرى، درجة كل رأس من رؤوسه على الأقل 3. أثبت أنه يوجد في G حلقة طولها زوجي. (مساعدة : حذ في الحسبان أكبر مسار) (P.Kwok).
55- افترض أن P و Q مساران في بيان مترابط G، بحيث إن طوليهما أكبر ما يمكن، أثبت أنه يوجد رأس مشترك بينهما.
56- افترض أن G بيان بسيط مترابط لا نستطيع أن نستحدث منه P4 و لا C4. أثبت أنه يوجد لg رأس يجاور باقي رؤوس G (مساعدة : افترض رأسا له أكبر درجة). (wolk [1965]).
57- استخدم استقراء على k لتثبيت أن كل بيان بسيط له عدد زوجي من الأضلاع بتفكك إلى مسارات طول كل منها 2. هل تبقى النتيجة صحيحة إذا حذف شرط الترابط ؟
58- تشمل مجموعة تسعة طلاب، إذا أرسل كل طالب ثلاث بطاقات معايدة لثلاثة من زملائه في الصف، بين إمكانية حصول كل منهم على بطاقات من الأشخاص أنفسهم الذين أرسل لهم بطاقاته.
59- أثبت أو انقض العبارة الآتية : في البيان G، إذا كان كل من u و v هما الرأسين الفريدين اللذين درجتهما فردية، فإن G يحوي مسارا من u إلى v.
60- تشمل مجموعة تسعة طلاب، إذا أرسل كل طالب ثلاث بطاقات معايدة لثلاثة من زملائه في الصف، بين إمكانية حصول كل منهم على بطاقات من الأشخاص أنفسهم الذين أرسل لهم بطاقاته.
61- إذا كان لديك البيانان G و H، فحدد عدد مركبات البيان G + H و أكبر درجاته بدلالة الأعداد الخاصة لكل من G و H.
62- حدد أكبر عدد ممكن من الأضلاع لبيان جزئي ثنائي الفرع لكل من Pn، Cn، و Kn.
63- في اتحاد للعبة معينة، قسمت الفرق إلى مجموعتين تضم كل منهما 13 فريقا. بين إمكانية ترتيب مباريات لهذه الفرق بحيث يلعب كل فريق تسع مباريات ضمن مجموعته، و أربع مباريات ضمن المجموعة الثانية.
64- افترض أن ,m,n 1ثلاثة أعداد صحيحة غير سالبة، بحيث إن 1 + m = n، جد الشروط الضرورية و اللازمة التي تحققها 1,m,n، بحيث يوجد بيان بسيط مترابط له n من الرؤوس، و بحيث يكون 1 منها رؤوسا زوجية و m رؤوسا فردية.
65- أثبت أنه لا يوجد ضلع قطع للبيان الزوجي. و ابن بيانا بسيطا منتظما بيان بسيط منتظم من الدرجة 2k+1 له ضلع قطع لكل k≥1.
66- أثبت أن كل بيان بسيط له رأسان على الأقل يمتلك رأسين لهما الدرجة نفسها. هل النتيجة صحيحة للبيانات الخالية من العرى ؟
67- لكل k≥3، حدد أصغر عدد n بحيث : a) يوجد بيان بسيط منتظم من الدرجة k على n من الرؤوس. b) توجد بيانات بسيطة منتظمة من الدرجة k غير متشاكلة على n من الرؤوس.
68- أثبت أنه لا يوجد ضلع قاطع (فاصل) لكل بيان ثنائي الفرع منتظم من الدرجة k لكل k≥2.
69- احسب عدد الحلقات التي طولها n في Kn، و عدد الحلقات التي طولها 2n في Kn,n
70- احسب عدد الحلقات السداسية Km,n.
71- أثبت أن K2,3 غير محتوى في أي مكعب زائدي Qk.
72- أثبت أن كل حلقة طولها 2r في مكعب زائدي تكون في مكعب جزئي بعده على الأكثر r. هل يمكن لحلقة طولها 2r أن تكون محتواة في مكعب جزئي بعده أقل من r ؟
73- احسب عدد الحلقات السداسية في Q3. أثبت أن كل حلقة سداسية في Qk تقع في مكعب جزئي واحد فقط ثلاثي البعد، استخدام هذا الحساب عدد الحلقات السداسية في Qk لكل k≥3
74- افترض أن V مجموعة ثنائية للترتيبات التي عدد عناصرها (binary k-tuples)k ، عرف بيانا بسيطا Qk رؤوسه المجموعة V، بحيث إن u ↔ v إذا و فقط إذا اتقف كل من u و v في إحداثي واحد فقط. أثبت أن Qk يشاكل المكعب الزائدي Qk إذا و فقط إذا كان k زوجيا (D.G.Hoffman).
75- في التشاكلات الذاتية للمكعب الزائدي Qk : a) أثبت أن كل نسخة من Qj في Qk هي بيان جزئي تولده مجموعة بها 2j من الرؤوس حددت قيمها على مجموعة بها k-j من الإحداثيات. (مساعدة : أثبت أن كل نسخة من Qj يجب أن تحوي رأسين يختلفان في j من الإحداثيات). b) استخدم فرع a لحساب عدد التشاكلات الذاتية للبيان Qk.
76- أثبت أن كل ضلع في بيان بيترسون ينتمي إلى أربع حلقات خماسية فقط، و استخدم ذلك لإثبات أن بيان بيترسون يحوي 12 حلقة خماسية بالضبط. (مساعدة : لإثبات الجزء الأول وسع كل ضلع للحصول على نسخة من p4، و استخدم القضية 38.1.1).
77- افترض أن G بيان بسيط على n من الرؤوس يخلو من طائرة ورقية (k4-e)، بحيث يوجد لكل زوج من الرؤوس غير المتجاورة جاران مشتركان فقط، أثبت أن G يكون منتظما (Calvin).
78- افترض أنه تم تشكيل البيان H من البيان المنتظم خالي العرى G بحذف أحد رؤوس G، حيث n(G) ≥ 3، صف (علل) كيفية الحصول على G من H.
79- افترض أن G بيان له ثلاثة رؤوس على الأقل، أثبت أن G مترابط إذا و فقط إذا وجد بيانان جزئيان مترابطان على الأقل من البيانات المحصلة من g يحذف أحد رؤوسها (مساعدة : استخدم القضية 29.2.1).
80- 23. افترض أن G بيان بسيط على n من الرؤوس، حيث n≥2، و حدد أكبر عدد ممكن من الأضلاع في G تحت كل شرط من الشروط الآتية : a) يوجد ل G مجموعة مستقلة من الحجم a. b) يوجد ل G بالضبط K مركبة. c)G غير مترابط.
81- أثبت أو انقض : إذا كان G بيانا بسيطا على n من الرؤوس، بحيث إن أكبر درجة فيه [n / 2]، و أقل درجة 1-[n / 2]، فإنه يكون مترابطا.
82- جد أكبر عدد من الأضلاع لبيان جزئي ثنائي الفرع من بينا بيترسون.
83- أثبت أو انقض : عندما نطبق الخوارزمية الموجودة في النظرية 1. 3. 19. على بيان ثنائي الفرع، فإننا نحصل على بيان جزئي ثنائي الفرع له أكبر عدد من الأضلاع (البيان كله).
84- استخدم الاستقراء على n(G) لإثبات أن يوجد لكل بيان غير تافه (nontrivial) خال من العرى بيان جزئي ثنائي الفرع H عدد أضلاعه يزيد على e (G) /2.
85- لكل n≥3، حدد أقل عدد ممكن من الأضلاع لبيان مترابط على n من الرؤوس، بحيث ينتمي كل ضلع منها إلى مثلث (Erdӧs [1988]).
86- يشارك فريقان في لعبة البريدج (نوع من لعب الورق). كل فريق مؤلف من لاعبين. افترض أن لدينا ناديا يمنع اللاعبين الأربعة من اللعب إذا صدف أن تشارك أي اثنين منهما في لعبة سابقة تلك الليلة، افترض وصول خمسة عشر لاعبا إلى النادي في تلك الليلة، إلا أن أحدهم قرر أن يدرس نظرية البيانات، أما الأربعة عشر شخصا الباقون، فلعبوا بحيث لعب كل منهم أربع مرت. بعد ذلك، تسمح لهم قواعد اللعبة بلعب ستة أدوار إضافية (12 مشاركة). أثبت أنه إذا وافق الآن دارس نظرية البيانات على اللعب، فإنه يمكن لعب لعبة أخرى على الأقل. (آخذ بتصرف من كتاب (Bondy-muety [1976] p111
87- افترض أن n عدد صحيح، و أن d تتكون من قائمة من الأعداد الصحيحة غير السالبة ذات مجموع زوجي، بحيث إن أكبر عدد منها أقل من n، و يختلف عن أصغر عدد بمقدار واحد على الكثر. أثبت أن d قابلة للرسم (geraphic) ؛ أي أنها متحققة بيانيا (بيانية) (مساعدة : استخدام نظرية هافل و حكيمي).
88- تعميم نظرية هافل و حكيمي . افترض أن لديك قائمة (مجموعة) غير متزايدة من الأعداد الصحيحة غير السالبة. و افترض أيضا أنه يمكن تحصيل ď بحذف dk، و بطرح 1 من ال k عنصرا القصوى المتبقية في القائمة (المجموعة). أثبت أن d تكون بيانية إذا و فقط إذا كانت ď بيانية. (مساعدة : تتبع خطوات إثبات نظرية 31.3.1 (wang-kleitman [1973]).
89- افترض أن d قائمة (مجموعة) من الأعداد الصحيحة تتألف من k نسخة من a و n – k نسخة من b، حيث a≥b≥0، جد الشروط اللازمة حتى تكون d بيانية .
90- توسيع (تمديد) بيانات منتظمة ثلاثية. (انظر المثال 26.3.1) افترض أن n = 4k حيث k≥2، جد بيانا بسيطا مترابطا ثلاثيا له n من الرؤوس لا يحوي ضلع فصل (قطع) و لكن لا يمكن تحصيله من بيان ثلاثي بسيط عن طريق التمديد لهذا البيان. (مساعدة : لا يوجد في هذا البيان أي ضلع يمكن أن بطبق عليه العلمية العكسية للحصول على بيان بسيط أصغر).
91- بناء بيانات بسيطة منتظمة ثلاثية : a) أثبت أنه يمكن عمل مفتاح ثنائي من خلال مجموعة من عمليات التوسعة و المحو (العملية العكسية للتوسعة). هذه العلميات معرفة في المثال 26.3.1. (تنويه : عملية المحو التي تولد ضلعا مكررا غير مسموحة). b) استخدم فرع a أعلاه لإثبات أن كل بيان بسيط منتظم ثلاثي يمكن الحصول عليه من K4 بمجموعة من عمليات التمديد (التوسعة) و المحو. (Batageli [1984]).
92- جد علاقة واقعية لا توجد حلقات لبيانها الموجه، وجد علاقة أخرى ذات حلقات إلا أنها غير تماثلية.
93- ثبت أن كل ممر من u إلى v في بيان موجه يحوي مسارا من ع إلى v.
94- أثبت أن كل ممر مغلق فردي الطول في بيان موجه يحتوي على ضلع لحلقة فردية (مساعدة : تتبع البديهية 15.2.1)
95- افترض أن G بيان موجه، فيه الدرجة الخارجة لكل رأس تساوي الدرجة الداخلة لذلك الرأس، أثبت أنه يمكن تخليل (تفكيك) G إلى حلقات.
96- أثبت العبارة الآتية أو انقضها : إذا كان D توجيها لبيان بسيط له عشرة رؤوس، فإنه لا يمكن أن تكوم الدرجات الخارجة لرؤوس D مختلفة.
97- أثبت أنه يوجد دوري له n من الرؤوس، بحيث إن الدرجة الداخلة تساوي الدرجة الخارجة لكل رأس إذا و فقط إذا كان n عدد فرديا.
98- أثبت n≥1 العبارة الآتية أو انقضها : يوجد في كل بيان موجه بسيط رأسان لهما الدرجة الخارجة نفسها أو الدرجة الداخلة نفسها.
99- أثبت أن البيان الموجه يكون مترابطا بقوة إذا و فقط إذا تحقق أنه لكل تجزئة لمجموعة رؤوسه إلى مجموعتين غير خاليتين T و S يوجد ضلع من أضلاعه يربط بين S و T.
100- أثبت أنه في كل بيان موجه، توجد مركبة قوية (مترابطة بقوة) ليس لها أضلاع داخلة (لا يدخلها أضلاع) كما توجد مركبة قوية ليس لها أضلاع خارجة (لا يخرج منها أضلاع).
101- للبيان الموجه D، عرف علاقة R على (V(D على الصورة الآتية : (x, y) إذا اوجد مسار من x إلى y، و مسار آخر من y ، و مسار آخر من y إلى x في Ḋ، فأثبت أن R علاقة تكافؤ، و أن صفوف التكافؤ هي مجموعات رؤوس المركبات القوية للبيان الموجه D.
102- أثبت أن الحلقة الفردية (الموجهة) تمثل بيانا موجها ليس له نواة. جد مثالا لبيان موجه له حلقة فردية مستحدثة بوضفها بيانا جزئيا، و لكن له نواة.
103- أثبت أنه توجد نواة واجدة للبيان الموجه الذي ليس فيه حلقات.
104- استخدم البديهية (23.4.1) و الاستقراء على عدد الأضلاع لإثبات الخاصية المميزة للبيانات الموجهة الأويلرية (النظرية (24.4.1). (مساعدة : تتبع النظرية 26.2.1)
105- أثبت صحة الصفة المميزة للبيانات الموجهة الأويلرية (النظرية 24.4.1) باستخدام مفهوم المسارب القصوى (مساعدة : اتبع 32.2.1) و الإثبات للنظرية 26.2.1)
106- تعطي النظرية 24.4.1 الشروط الضرورية و الكافية لكي يكون للبيان الموجه (حلقة) أويلرية، حدد (مثبتا) الشروط الضرورية و الكافية لكي يكون للبيان الموجه مسرب أويلري. (التعريف 22.4.1)، (Good [1946]).
107- رتب 7 أصفار و 7 آحاد حلقيا، بحيث يكون 14 صفا المكون كل منها من أربعة حدود ثنائية متتابعة، هي كل ما يمكن تكوينه من صفوف رباعية (باستخدام هذين الرقمين) مختلفة عن 0101 و 1010.
108- متتالية (De Bruijin) ديبروجين لأي هجائية (al phapet) مهما كان طولها. افترض مجموعة حروف هجائية حجمها k. أثبت وجود ترتبية حلقية مؤلفة من KI من الحروف المختارة من A بحيث تكون ال kI صفا التي طول كل منها I في هذه المتتالية مختلفة بعضها عن بعض، أي أن يكون كل منها مختلفا عن الآخر
109- افترض أن S هجائية حجمها m. وصح كيف يمكن الحصول على ترتيبة حلقية مؤلفة من m4 – m حرفا من S بحيث إن الصفوف المؤلفة من أربعة أحرف من الحروف المتتابعة جميعها تكون مختلفة بعضها عن بعض، و تحتوي حرفين مختلفين على الأقل.
110- حدد أصغر عدد n بحيث توجد بيانات لدورين غير متشاكلين لكل منهما n من الرؤوس، و لهما قائمة الدرجات الخارجة نفسها.
111- 1. نقول : إن البيان الموجه فريد المسار إذا وجد على الأكثر مسار واحد (موجه) يربط بين أي رأسين x و y. افترض أن Tn دوري على n من الرؤوس، حيث إن الضلع الذي يربط vj-vi يكون موجها في اتجاه الرأس الذي دليله أكبر. ما أكبر عدد للأضلاع الموجودة في بيان جزئي فريد المسار من Tn ؟ كم بيانا جزئيا فريد المسار عدد أضلاعه أكبر ما يمكن موجودا في مثل هذا البيان ؟ (مساعدة : أثبت أن البيان الموجه لا يحوي أي مثلثات) ).Maurer-Rabinovitch-Trotter [1980]
112- 2. افترض أن G دوري، و افترض كذلك أن L0 هي قائمة بعناصر V(G) بترتيب معين. إذا كان y يتبع x مباشرة في L0، و لكن y → x، في G، فإن yx ضلع معكوس (عكسي). يمكننا تبديل x مع y في الترتيب عندما يكون yx ضلعا معكوسا (هذا يمكن أن يزيد عدد الأضلاع المعكوسة). افترض أن متتالية....، L1، L0 تنتج بسبب عمليات تبديل الأضلاع المعكوسة في الترتيب الحالي ضلعا واحدا في كل مرة و بالتتابع. أثبت أن هذا يعطي قائمة من الأضلاع خالية من الأضلاع المعكوسة دائما، وحدد عدد الخطوات اللازمة للانتهاء من هذه العملية (تعليق : في الحالة الخاصة، عندما تمثل الرؤوس بأعداد، و يشير كل ضلع في اتجاه العدد الأعلى، فإن النتيجة تشير إلى أن تبديل الأعداد المتجاورة بالتتابع و غير المرتبة دائما و بالنهاية يعطي تصنيفا للقائمة) (Locke [1995]).
