مقدمة في نظرية الرسم البياني

Correct answers From 5

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])‎.
113- أثبت أن البيان يكون شجرة إذا وفقط إذا خلا من العرى، و كان له شجرة مولودة واحدة فقط.
114- استخدم نظرية مصفوفة الشجرة لإثبات صيغة كيلي.
115- عين أعدادا صحيحة بوصفها أوزانا لأضلاع Kn. أثبت أن الوزن الكلي على كل حلقة يكون زوجيا إذا وفقط إذا كان الوزن الكلي زوجيا على كل مثلث.
116- أثبت العبارة الآتية أو انقضها : مل شجرة لها مواءمة مكتملة واحدة على الأكثر.
117- حدد الحجم الأصغر لمواءمة أعظمية في الحلقة Cn.
118- لتكن S مجموعة الرؤوس المشبعة بالمواءمة M في البيان G. أثبت أن بعض المواءمات العظمى أيضا تشبع S. و هل هذه العبارة يجب أن تكون صحيحة لكل مواءمة كبرى ؟
119- لتكن Tشجرة على n من الرؤوس، و ليكن k الحج الأكبر لمجموعة مستقلة في T. حدد (T)‎’a بدلالة n و k.
120- يخطط أعضاء ناد لقضاء عطلتهم الصيفية، حيث يتوافر لديهم الرحلات tn،....،t1، ولكن سعة الرحلة ti هي ni. و كل شخص يرغب في بعض هذه الرحلات سيسافر على الأكثر في واحدة منها. بدلالة أي الأشخاص يرغب بأي الرحلات، اشتق الشرط الضروري و الكافي لملء الرحلات جميعها (بسعتها)‎ من الأشخاص الذين يرغبون فيها.
121- مصفوفة التباديل (permutation matrix)‎ P : هي مصفوفة، مدخلاتها 1.0 فقط و تحوي في كل صف و عمود العدد 1 بالضبط مرة واحدة. أثبت أن أي مصفوفة مربعة مدخلاتها أعداد صحيحة غير سالبة يمكن كتابتها في صورة حاصل جمع k من مصفوفات التباديل، إذا كانت مجاميع الفوف جميعها و مجاميع الأعمدة جميعها كذلك تساوي k.
122- تتكون مجموعة من أوراق اللعب من mn بطاقة مع m و n نقشا عليها، بحيث يكون هنالك بطاقة واحدة لكل قيمة في كل تفش. وزعت البطاقات إلى صفيف n في m : a)‎ أثبت أن هنالك مجموعة تتكون من m بطاقة، بواقع بطاقة واحدة في كل عمود، ذات قيم مختلفة. b)‎ استخدم فرع (a)‎ لبرهنة أنه بمتتالية من تبديلات البطاقات التي لها القيمة نفسها، يمكن إعادة ترتيب البطاقات بحيث يتكون كل عمود من n بطاقة من النقوش المختلفة. (Enchev [1997])‎.
123- استخدم نظرية كونج و إيجرفاري لإثبات أن كل بيان ثنائي الفرع G له مواءمة حجمه e(G)‎/∆(G)‎ على الأقل. استخدم هذا لتستنتج أنه توجد لكل بيان جزئي منKn,n عدد أضلاعه أكثر من n(1-k)‎مواءمة حجمها k على الأقل.
124- حدد اكبر عدد من الأضلاع في البيان الثنائي الفرع البسيط الذي لا يحوي مواءمة عدد أضلاعها k و لا يحوي نجما عدد أضلاعه I (Isaak)‎.
125- استخدم نظرية كونج و إيجرفاري لإثبات نظرية هال.
126- ليكن G بينانا ثنائي الفرع. أثبت أن a (G)‎ = n(G)‎/2 إذا و فقط إذا وجدت ل G مواءمة مكتملة .
127- أعط توصيفا مميزا للبيانات التي عدد سيطرتها 1.
128- أوجد أصغر شجرة لا يتساوي فيها عدد كل من السيطرة و الغطاء الرأسي.
129- حدد عدد السيطرة لبيان بيترسون، و حدد الحجم الأصغر لمجموعة مسيطرة كلية في بيان بيترسون كذلك.
130- في المكعب الزائد Q4، حدد الأحجام الصغرى لكل من : مجموعة مسيطرة، و مجموعة كسيطرة مستقلة، و مجموعة مسيطرة مترابطة، و مجموعة مسيطرة كلية.
131- أوجد طريقة لوضع خمسة أزواج من الملكات غير المهاجمة زوجا زوجا على لوح شطرنج 8 في 8 بحيث تهاجم هذه الملكات المربعات الأخرى جميعها.
132- في البيان المترابط G الذي درجته n، أثبت أن الحجم الأصغر لمجموعة مسيطرة مترابطة هو n ناقص أكبر عدد للأوراق في سجرة مولدة
133- باستعمال أوزان غير سالبة للأضلاع، أنشئ بيانا موزونا على أربعة رؤوس بحيث لا تكون المواءمة ذات الوزن الأكبر مواءمة ذات حجم أكبر.
134- بين كيفية استعمال الخوارزمية النهجارية لفحص إمكانية وجود مواءمة كاملة في البيان الثنائي
135- أعط مثالا على مسألة المواءمة المستقرة يتكون من رجلين و امرأتين، بحيث يكون هناك أكثر من مواءمة مستقرة.
136- مسألة سائق الحافلة. افترض أن هناك n سائقا و n مسلكا صباحيا يقضي فيها السائق أوقاتا Xn،....X1، و n مسلكا مسائيا يقضي فيها أوقاتا yn،....y1. و يدفع للسائق أجر إضافي عندما يتجاوز المسلكين الصباحي و المسائي زمنا كليا t. و الهدف هو تعيين شوطين ؛ صباحي و مسائي لكل سائق من أجل تخفيض قيمة الأجور الإضافية الكلية إلى الحد الأدنى. عبر عن هذه بوصفها مسألة مواءمة موزونة، و برهن أن إعطاء أطول مسلك صباحي رقمه i و أقصر مسلك مسائي رقمه i للسائق نفسه لكل i يعطي حلا مثاليا. (مساعدة : لا تستخدم الخوارزمية الهنجارية ؛ خذ التركيب الخاص للمصفوفة)‎. (R.B. Potts)‎
137- افترض أن لديك n رجلا و n امرأة. و قد خصص كل منهم n –i نقطة إلى الشخص i في قائمة أولوياته، و ليكن الوزن لزوج من الأشخاص هو مجموع النقاط المخصصة من ذلك الزوج من الأشخاص أنشئ مثالا لا تكون فيه أي مواءمة وزن كبرى مواءمة مستقرة.
138- أثبت أنه إذا وضع رجل x في زوج مع امرأة a في مواءمة مستقرة، فإن a لم ترفض x في خوارزمية مقترحات جيل و شابلي. استنتج أنه من بين المواءمات المستقرة جميعها، فإن كل رجل يكون أكثر سعادة في المواءمة الناتجة عن هذه الخوارزمية. (مساعدة : خذ في الحسبان الحدوث الأول لمثل هذا الرفض)‎.
139- في مسألة رفقاء الغرف المستقرة، كل شخص من 2n شخصا له ترتيب أولويات على ال (2n-1)‎ شخصا الآخرين. و المواءمة المستقرة هي مواءمة كاملة لا يوجد فيها زوج غير متوائم يفضل فيه كل منهما شخصا آخر على رفقاء غرفهم الحاليين. أثبت أنه لا توجد مواءمة مستقرة عندما تكون الأولويات على النحو الآتي أدناه. (Gale-Shapley [1962])‎ a : b˃ c˃ d b : c˃ a ˃ d c : a ˃ b ˃ d d : a ˃ b ˃ c
140- في مسألة رفقاء الغرف المستقرة، افترض أن كل شخص يصرح بالقسم العلوي من قائمة الأولويات بوصفه جزءا "مقبول". عرف بيان المقبولية على أنه البيان الذي تكون رؤوسه الناس و أضلاعه هي الأزواج من الناس الذين افترضوا أن كلا منهما مقبول للآخر. أثبت أن المجموعات العالية المنزلة في المقبولية G كلها تؤدي إلى مواءمة مستقرة إذا و فقط إذا كان G ثنائي الفرع.
141- في خوارزمية المقترحات حيث يقترح الرجل، أثبت أنه لا يوجد رجل مرفوض دائما من النساء جميعهن. (مساعدة : ماذا يحدث بعد أن يرفض X من النساء جميعهن ما عدا امرأة واحدة)‎.
142- ليكن G بيانا منتظما من الدرجة 3 و له صلعا قطع على الأكثر. أثبت أن G يملك معاملا من الدرجة 1. ([1891] Petersen)‎
143- ليكن G بيانا ثنائي الفرع منتظما نت الدرجة k. أثبت أنه يمكن تفكيكه إلى معاملات من الدرجة r و فقط إذا كانت r تقسم k.
144- ليكن G و H بيانين. حدد عدد المركبات و الدرجة العظمى لH G ˅ بدلالة متغيرات G و H.
145- أثبت أن الشجرة T تملك مواءمة كاملة إذا و فقط إذا كان o(T-v)‎ = 1 لكل (Chungphaisan)‎ vϵV(T)‎ .
146- ليكن G بيانا زوجيا منتظما من الدرجة k (درجته زوجية)‎ بحيث يبقى مترابطا بعد حذف أي (K-2 ضلعا. أثبت أن G يملك معاملا من الدرجة 1.
147- أثبت أن البيان البسيط المنتظم من الدرجة 3 يملك معاملا من الدرجة 1 إذا و فقط إذا كان يتفكك إلى نسخ من P4.
148- 6. ليكن G بيانا مترابطا خاليا من المخالب ذا درجة زوجية : a)‎ لتكن T شجرة مولدة للبيان G بالبحث الأفقي أولا (الخوارزمية 8.3.2)‎. و ليكن x و y رأسين لهما والد مشترك في T غير الجذر. أثبت أن x و y يجب أن يكونا متجاورين. b)‎ استخدم فرع (a)‎ لتثبت أن G يملك معاملا من الدرجة 1. ( تعليق : دون الاستعانة بفرع (a)‎ يمكن إثبات النتيجة الأقوى، و هي أن الضلع الأخير في المسار الأطول ينتمي إلى معامل من الدرجة 1 .(Las Vergnas [1975], Sumner [1974a])‎
149- لتكن M مواءمة في البيان g، و ليكن U رأسا غير مشبع للمواءمة M. أثبت أنه إذا كان G لا يملك مسارا موسعا للمواءمة M يبدأ عند u، فإن u غير مشبع في مواءمة كبرى ما في G.
150- أعط مثالا ناقضا للعبارة الآتية، و أضف فرضيات لتصحيحها، ثم أثبت صحة العبارة المصححة : إذا كان e ضلعا فاصلا (cut-edge)‎ ل G، فإن أحد طرفيه على الأقب يكون رأسا فاصلا ل G.
151- أثبت أو انقض كلا من العبارة الآتية : إذا كان مقياس ترابط بيان معين يساوي 4، فإن هذا البيان يكون مترابطا من الدرجة 2.
152- أثبت أو انقض كلا من العبارة الآتية : إذا كان البيان مترابطا من الدرجة 3، فإن مقياس ترابطه يساوي 3.
153- أثبت أو انقض كلا من العبارة الآتية : إذا كانت درجة ترابط بيان تساوي k، فإن درجة ترابطه الضلعية تساوي k.
154- أثبت أو انقض كلا من العبارة الآتية : إذا كان البيان مترابطا ضلعيا من الدرجة K، فإنه يكون مترابطا من الدرجة k.
155- افترض أن G بيان له أكثر من k من الرؤوس، و بحيث إن G ليس بيانا تام. أثبت أنه إذا لم يكن G مترابطا من الدرجة k، فإن هناك مجموعة فاصلة حجمها k-1 لهذا البيان.
156- أثبت أن البيان G مترابط من الدرجة k إذا و فقط إذا كان Kr G ˅ (التعريف 6.3.3)‎ مترابطا من الدرجة k + r.
157- جد صيغة تعطي عدد الأشجار المولدة لبيان مترابط بدلالة الأشجار المولدة لقوالبه.
158- جد أصغر بيان بسيط منتظم من الدرجة الثالثة بحيث يكون مقدار ترابطه يساوي 1، و أثبت ذلك.
159- افترض أن k,n أعداد صحيحة موجبة، بحيث n عدد زوجي، و k عدد فردي، و n>k>1. افترض أن G هو البيان البسيط المنتظم من الدرجة k المشكل بوضع n من الرؤوس على دائرة، و بجعل كل رأس يجاور (يرتبط بضلع)‎ الرأس المضاد له على الدائرة بالإضافة إلى مجاورته لأقرب (k-1)‎/2 رأسا في كلا الاتجاهين على الدائرة، أثبت أن k(G)‎ = k (Harary [1962a])‎.
160- ليكن G بيانا مترابطا، بحيث توجد لكل ضلع e حلقتان هما : C1 و C2 تحتويان على e، و بحيث إن e الضلع الوحيد المشترك بينهما. أثبت أن G مترابط ضلعيا من الدرجة 3، استخدم هذه النتيجة لإثبات أن بيان بيترسون مترابط ضلعيا من الدرجة الثالثة.
161- استخدم القضية 12.1.4 و النظرية 11.1.4 لإثبات أن بيان بيترسون مترابط من الدرجة 3.
162- أثبت أن حذف قاطعة ضلعية حجمها 3 من بيان بيترسون يعزل رأسا.
163- افترض أن G بيان زوجي الرتبة مترابط من الدرجة r، بحيث إن K1,r+1 بيان جزئي من G. أثبت أن ل G معامل 1. (1-facter)‎ (Summer [1976b])‎
164- افترض أن F مجموعة جزئية من الأضلاع في بيان G. أثبت أن F قاطعة ضلعية إذا و فقط إذا كانت تحوي عدد زوجيا من أضلاع كل حلقة في G. فعلى سبيل المثال، عندما G = Cn، فإن كل مجموعة زوجية من الأضلاع تشكل قاطعة ضلعية، و لا توجد أي مجموعة فردية تمثل قاطعة ضلعية (مساعدة : لإثبات الشرط الكافي ؛ علينا أن نثبت أنه يمكن وضع مركبات F في مجموعتين، بحيث إن لكل ضلع في F نقطة طرفية في كل من المجموعتين)‎.
165- إذا كان H بيانا جزئيا مولدا لبيان مترابط G، فأثبت أن H يمثل شجرة مولدة للبيان G إذا و فقط إذا كان H* = G-E(H)‎ لا يحوي أي رابطة من G، و إضافة أي ضلع ل H بحدث بيانا جزئيا من G يحوي رابطة من G.
166- افترض أن G بيان بسيط، رؤوسه ؛ [11،......،2،1] حيث i ↔ j إذا و فقط إذا كان i و j عامل مشترك أكبر من 1. حدد قوالب G.
167- أثبت أن درجة كل رأس من رؤوس بيان تكون زوجية إذا و فقط إذا كان كل قالب فيه أويلريا.
168- افترض أن G بيان مترابط، أثبت أنه مترابط ضلعيا من الدرجة k إذا و فقط إذا كان كل قالب فيه مترابطا ضلعيا من الدرجة k.
169- افترض أن H و ’H بيانان جزئيان من البيان G، بحيث إنهما كبيران مترابطان من الدرجة k. أثبت أنهما يشتركان في k-1 رأسا على الأكثر. (Harary-Kodama. [1964])‎
170- أثبت أن الخوارزمية 23.1.4 تحسب بدقة عدد قوالب أي بيان.
171- طور خوارزمية لحساب المركبات القوية لبيان موجه، و أثبت أن خوارزميتك تعمل. (مساعدة : اعمل نموذجا لهذه الخوارزمية متعمدا على الخوارزمية 23.1.4)‎.
172- استخدم النتائج الموجودة في هذا الدرس لإثبات أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا وفقط إذا أمكن الحصول على G من C3 بعمل مجموعة من عمليات إضافة الأضلاع و قسمتهما.
173- أثبت أنه إذا كان G مترابطا ضلعيا من الدرجة 2، و إذا حصلنا على ’G من G بقسمة أحد أضلاع G، فإن ’G مترابط ضلعيا من الدرجة 2. استخدم هذا الإثبات أنه إذا كان للبيان تحليل مقبضي مغلق، فإن البيان يكون مترابطا ضلعيا من الدرجة 2 (تعليق : هذا إثبات بديل للكفاية في النظرية 10.2.4)‎.
174- افترض أن G بيان موجه حيث [12] تمثل مجموعة رؤوسه، و حيث إن i → j إذا و فقط إذا كانت i تقسم j. جد (12 و 1)‎ k و (12, 1)‎’k.
175- أثبت العبارة الآتية أو انقضها : إذا كان P مسارا من u إلى v في بيان G مترابط من الدرجة 2. فإنه يوجد مسار Q من ع إلى v بحيث إن Q منفصل داخليا عن P.
176- افترض أن G بيان بسيط، و اجعل H(G)‎ تمثل البيان الذي رؤوسه V(G)‎ بحيث إن uv ϵ E(H)‎ إذا و فقط إذا ظهر كل من u و v في الحلقة نفسها التي في G. أعط توصيفا للبيانات G بحيث يكون H بيانا تاما.
177- استخدم النتائج الموجودة في هذا الدرس لإثبات أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا و فقط إذا أمكن الحصول على G من C3 بعمل مجموعة من عمليات إضافة الأضلاع و قسمتهما.
178- أثبت أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا و فقط إذا تحقق ما يأتي : لكل ثلاثية مرتبة (x, y, z)‎ من الرؤوس المختلفة، يوجد مسار من x إلى z يمر من خلال y (chein [1968])‎.
179- افترض أن G بيان له أربعة رؤوس على الأقل. أثبت أن G يكون مترابطا من الدرجة 2 إذا و فقط إذا تحقق ما يأتي : لكل زوج X وy حيث X و Y مجموعتان جزئيتان من رؤوس G و بحيث إن ǀXǀ , ǀYǀ ≥2، يوجد مساران منفصلان تمام هما : P1 و P2 في G بحيث يوجد لكل منهما نقطة طرفية في X، و نقطة طرفية أخرى في Y، دورن وجود رؤوس داخلية لأي منهما لا في X و لا في Y.
180- نعرف التحليل المقبضي الجشع لبيان مترابط من الدرجة 2 على أنه تحليل مقبضي يبدأ بأطول حلقة، ثم يكرر إضافة أطول مقبض ممكن. استخدم تحليلا مقبضيا جشعا لإثبات أن كل بيان G مترابط من الدرجة 2 خال من المخالب يحوي [n (G)‎/3] نسخة من P3، بحيث إن هذه النسخ منفصلة زوجا زوجا. (kaneko-kelmans-Nishimura [2000])‎.
181- افترض أن G بيان مترابط له ثلاثة رؤوس على الأقل، أثبت أن العبارات الآتية متكافئة (يمكن استخدام نظرية منجر)‎ : a)‎ G مترابط ضلعيا من الدرجة 2. b)‎ كل ضلع في G يظهر في حلقة. c)‎ يوجد في G مسرب مغلق لا يكرر أضلاعا (closed trail)‎، و يحوي أي ضلعين محددين. d)‎ يوجد في G مسرب مغلق لا يكرر أضلاعا، و يحوي أي رأسين محددين.
182- استخدم نظرية منجر لإثبات أنه إذا كان G بيانا منتظما من الدرجة 3، فإن k(G)‎ = k׳(G)‎ (النظرية 11.1.4)‎.
183- افترض أن G بيان مترابط ضلعيا من الدرجة 2، عرف علاقة R على E(G)‎ على الصورة الآتية : (e, ƒ)‎ ϵ R إذا كان e = ƒ، أو إذا كان G-e-ƒ غير مترابط (lovàsz [1979, p277])‎ : a)‎أثبت أن (e, ƒ)‎ ϵ R إذا و فقط إذا اتمنى كل من e, ƒ إلى الحلقة نفسها. b)‎ أثبت أن R علاقة تكافؤ على E(G)‎. c)‎ لكل صف تكافؤ F، أثبت أن F محتوى في حلقة. d)‎ لكل صف تكافؤ F، أثبت عدم وجود قاطعة ضلعية ل G-F.
184- افترض أن v رأس في بيان G المترابط من الدرجة 2، أثبت أنه يوجد ل u جوار ر، بحيث إن G – u –v مترابط (Chartrand-Lesniak [1986, p51])‎.
185- افترض أن G بيان مترابط من الدرجة 2. أقبت أنه إذا كانت كل من T1 و T2 شجرتين مولدتين للبيان G فيمكن تحويل T1 و T2 بإجراء عدة عمليات يتم من خلالها إزالة ورقة (leaf)‎ و إعادة تثبيتها باستخدام ضلع آخر للبيان G.
186- جد أصغر بيان مقدار ترابطه 3، بحيث يكون له رأسان غير متجاورين و منفصلان معا بواسطة أربعة مسارات منفصلة داخليا زوجا زوجا.
187- افترض عدم وجود رؤوس معزولة للبيان G. أثبت أنه إذا خلا هذا البيان من الحلقات الزوجية، فإن كل قالب فيه يكون إما ضلعا أ, حلقة فردية.
188- العضوية في الحلقات المشتركة : a)‎ أثبت أن ضلعين مختلفين ينتميان إلى القالب نفسه في بيان G إذا و فقط إذا كانا ينتميان إلى الحلقة نفسها. b)‎ افترض أن e, ƒ, g ϵ E(G)‎، و افترض أيضا وجود حلقة في G تمر خلال e و g، و حلقة أخرى تمر خلال f و g. أثبت أنه توجد حلقة في G تمر في e و g. (تعليق : لاحظ أن هذه المسألة تضمن أن علاقة "المساواة أو الانتماء إلى الحلقة" نفسها هي علاقة تكافؤ على أضلاع البيانات التي ليس لها أضلاع فاصلة أو قاطعة، و أن صفوف التكافؤ لهذه العلاقة هي مجموعات أضلاع قوالب البيان)‎.
189- أثبت أن المكعب الزائدي مترابط من الدرجة Qk بإيجاد k من المسارات x,y المنفصلة داخليا زوجا زوجا و ذلك لكل زوج رؤوس x.y ϵ V(Qk)‎.
190- افترض أن G بيان مترابط ضلعيا من الدرجة 2k بحيث إن له على الأكثر رأسين درجتهما فردية، أثبت أنه يوجد لهذا البيان توجيه مترابط ضلعيا من الدرجة k. (Nash-Williams [1960])‎.
191- افترض أن G بينا مترابط من الدرجة k، و افترض أيضا أن S و T مجموعتان جزئيتان غير متقاطعتين من V(G)‎ حجم كل منهما يساوي k على الأقل، أثبت أنه يوجد للبيان G, k من المسارات T,S المنفصلة (غير المتقاطعة)‎ زوجا زوجا.
192- أثبت لتطبيق عملية التمديد الموجود في المثال 1.3.26 على أن البيان المترابط من الدرجة 3 يعطينا بيانا مترابطا من الدرجة 3. ثم احصل على بيان بيترسون بإجراء تمديد (توسيع)‎ على K4. (تعليق : لقد أثبت Tutte [1966] أن البيان المنتظم من الدرجة 3 بكون مترابطا من الدرجة 3 إذا و فقط إذا أمكن الحصول عليه من K4 بإجراء عدد من عمليات التوسع (التمدد)‎)‎
193- افترض أن G بيان بسيط مترابط من الدرجة k : a)‎ افترض أن C و D حلقتان في G طولهما أكبر ما يمكن، إذا كانت k =2 أو k = 3، فأثبت أن C و D تشتركان في k من الرؤوس على الأقل، (مساعدة : إذا لم تشتركا فاحصل على حلقة أطول)‎. b)‎ لكل k ≥2، جد بيانا مترابطا من الدرجة k له حلقات مختلفة ، طولها أكبر ما يمكن و تشترك في k من الرؤوس فقط (مساعدة : اعتبر k2,4 عندما k =2)‎.
194- أثبت أنه إذا كان G مترابطا من الدرجة 2، فإن G-xy يكون مترابطا من الدرجة 2 إذا و فقط إذا وقع كل من x و y على حلقة G-xy. ثم استنتج أن البيان المترابط من الدرجة 2 يكون مترابطا من الدرجة 2 بحده الأدنى إذا و فقط إذا كانت كل حلقة بيانا جزئيا مستحدثا (induced subgraph)‎
195- أثبت أن كل مصفوفة حجمها 2x2 يمكن تدويها تدويرا منسجما.
196- افترض أن N شبكة لأضلاعها سعات معينة، و لنقاط لاتصال قيود محافظة بالإضافة إلى حدود دنيا ƒ(e)‎ ≥ L(e)‎. إذا كان التدفق الملائم الابتدائي معطى فبين كيف يمكن تعديل خوارزمية فورد و فولكرسون لوضع العلامات من أجل البحث عن أكبر تدفق ملائم عبر هذه الشبكة.
197- افترض أن G بيان موجه فيه x, y ϵV (G)‎. و افترض أيضا أن السعات قد حددت على الرؤوس المختلفة عن x و y بدلا من تحديدها على الأضلاع، و افترض وجود حد ثابت للتدفق الكلي عبر كل رأس، و لا يوجد أي حصر على التدفق عبر الأضلاع، وضح كيف يمكن استخدام نظرية تدفق الشبكات العادية لتحديد أكبر قيمة لتدفق ملائم من x إلى y في البيان G الذي حددت سعات رؤوسه.
198- استخدم تدفق الشبكات لإثبات أن البيان G يكون مترابطا إذا و فقط إذا وجد لكل تجزئة ل V(G)‎ لمجموعتين غير خاليتين S و T ضلع له نقطة طرفية في S، و أخرى في T. (تعليق : يوجد إثبات مباشر لهذه المسألة في الفصل الأول. لذا، فهذا مثال على استخدام مطرقة ضخمة لقتل بعوضة أو ذبابة)‎.
199- افترض أنه يوجد k من الأقسام الأكاديمية في إحدى الجامعات الكبيرة. و افترض أيضا أننا نرغب في تعيين لجنة مهمة تختار أستاذا من كل قسم، علما بأن بعض الأساتذة معينين تعيينا مشتركا بين قسمين أو أكثر، و افترض كذلك أنه لا يمكن تعيين أي شخص ليكون ممثلا لأكثر من قسم، و افترض أيضا أن عدد الأساتذة المساعدين يساوي عدد الأساتذة المشاركين و يساوي عدد الأساتذة في هذه اللجنة (افرض أن k تقبل القسمة على 3)‎. بين كيف يمكن إيجاد مثل هذه اللجنة. (مساعدة : جد شبكة بحيث ترتبط وحدات التدفق بالأساتذة الذين تم اختيارهم لهذه اللجنة، و أن السعات تمثل القيود المختلفة، ثم و ضح كيفية استخدام هذه الشبكة لاختبار ما إذا وجدت مثل هذه اللجنة، و أوجدها إن وجدت)‎. (Hall [1956])‎.
200- استخدم نظرية Gale و Ryser (نظرية 18.3.4)‎ لتحديد ما إذا وجد بيان بسيط ثنائي الفرع تكون درجات رؤوس إحدى مجموعتي رؤوسه هي : (5.4.4.2.1)‎ و كذلك درجات رؤوس المجموعة الثانية من رؤوسه هي : (5.4.4.2.1)‎ أيضا.
201- أكمل تفاصيل إثبات النتيجة 21.3.4، و ذلك بإثبات الشروط الضرورية و الكافية لوجود دوران في شبكة لها حدود دنيا و عليا.
202- أثبت أن العدد اللوني لبيان يساوي أكبر عدد لوني لمركباته.
203- جد بيانا G بحيث إن G ليس بيانا تاما و لا حلقة فردية، و لكن يوجد ترتيب لرؤوس هذا البيان :
204- بحيث يستخدم التلوين الجشع لهذه الرؤوس بالنسبة إلى هذا الترتيب ∆(G)‎ + 1 لونا.
205- أثبت أن G □ H يتفكك إلى n(G)‎ نسخة من H و n(H)‎ نسخة من G.
206- أثبت أو انقض : يوجد لكل بيان G لوني من الدرجة k تلوين ب k من الألوان بحيث يحوي أحد صفوفه اللونية a(G)‎ رأسا.
207- استخدم النظرية 21.1.5 لإثبات وجود مسار مولد لكل دوري. ([1934]Redei )‎.
208- حدد عدد الألوان الازم لوضع علامات دالة على V(Kn)‎ بحيث إن كل صف لوني يولد بيانا جزئيا درجته القصوى أقل من k أو يساويها.
209- افترض أن G بيان تتقاطع حلقاته الفردية زوجا زوجا ؛ بمعنى أنه يوجد رأس مشترك بين أي حلقتين فرديتين في G. أثبت أن X(G)‎ ≤ 5.
210- افترض أن كل ضلع لبيان G يظهر في حلقة واحدة على الأكثر. أثبت أن كل قالب في G ضلعا، أو حلقةـ أو رأسا معزولا. استخدم هذا في الإثبات أن X(G)‎ ≤ 3.
211- افترض أن G بيان منتظم من الدرجة 20، له 360 رأسا، و قد تم تكوينه بالطريقة الآتية :
212- وضعت الرؤوس على دائرة بأبعاد متساوية بينهما. تكون الرؤوس المفصولة بدرجة أو بدرجتين غير متجاورة، أما الرؤوس المفصولة بثلاث، أو ربع، أو خمس، أو ست درجات فتكون متجاورة. لا توجد أي معلومات عن التجاورات الأخرى (ما عدا أن البيان منتظم من الدرجة 20)‎. أثبت أن X(G)‎ ≤ 19. (مساعدة : لون الرؤوس المتتابعة بترتيب معين حول الدائرة)‎. (Pritikin)‎.
213- افترض أن g هي بيان مسافة الفصل في المستوى في هذا البيان V(G)‎ = R2، و تكون النقطتان متجاورتين إذا و فقط أذا كانت المسافة التقليدية بينهما تساوي 1 (هذا بيان غير منته)‎. أثبت أن 4 ≤ X(G)‎ ≤ 7. (مساعدة : لبرهان الحد الأعلى، قدم تلوينا صريحا للمناطق آخذا بالحسبان حدود كل منطقة)‎. (هادوايجر، موزر-موزر)‎ ([1961]Hadwiger [1945, 1961], Moser-Moser )‎
214- افترض أن Sm،....، S1 مجموعات منتهية، و أن xSm...U = S1x. عرف بيانا G رؤوسه عناصر U، حيث u ↔ vإذا و فقط إذا اختلف u عن v في كل إحداثي، جد X(G)‎.
215- افترض أن لديك إشارة ضوئية بتم التحكم فيها عن طريق مفتاحين كهربائيين، بحيث إن كلا منهما يمكن أن يوضع ب n من المواقع، و لكل موقع من هذه المواقع للمفتاح يظهر أحد ال n لونا الممكنة، و عند تغيير موضع المفتاحين يتغير اللون. أثبت أن اللوم الذي يظهر يتحدد من خلال موقع أحد المفتاحين، ثم وضح ذلك بدلالة العدد اللوني لبيان معين. (Greenwell-Lovasz [1974])‎.
216- أثبت أن نظرية بروكس تكافئ العبارة الآتية : كل بيان منتظم من الدرجة k-1 و حرج من الدرجة Kk يكون بيانا تام أو حلقة فردية (مساعدة : لبرهنة نظرية بروكس من هذه العبارة، خذ في الحسبان بيانا جزئيا حرجا من الدرجة k للبيان المعطى G، حيث إن G لوني من الدرجة k)‎.
217- افترض أن G بيان بسيط له n من الرؤوس، و m من الأضلاع، و درجته القصوى تساوي 3 على الأكثر. افترض أنه لا يوجد ل G أي مركبة تشكل بيانا تاما على أربعة رؤوس. أثبت أن G يحوي بيانا جزئيا ثنائي الفرع عدد أضلاعه يساوي m-2/ 3 على الأقل. (مساعدة " طبق نظرية بروكس. و بعد ذلك، وضح كيف نحذف بعض الأضلاع لتحويل التلوين الثلاثي الفعلي ل G إلى تلوين ثنائي لبيان جزئي كبير من G)‎.
218- أثبت أنه يمكن تلوين بيان بيترسون بلونين، بحيث يتألف البيان الجزئي المستحدث من كل صف لوني من أضلاع و رؤوس معزولة.
219- أثبت أن البيان البسيط يكون بيانا تاما متعدد الفروع إذا و فقط إذا خلا هذا البيان من بيان جزئي مستحدث له ثلاثة رؤوس و ضلع واحد
220- افترض أن G بيان، بحيث إن x(G – x – y)‎ = x(G)‎ – 2 لكل زوج x و y من الرؤوس المختلفة. أثبت أن G بيان تام. (تعليق : لقد خمن لوفاز أن النتيجة كذلك تتحقق عندما نفرض هذا الشرط فقط على الرؤوس المتجاورة)‎.
221- أثبت أن البيان البسيط يكون بيانا تام متعدد الفروع إذا و فقط إذا خلا هذا البيان من بيان جزئي مستحدث له ثلاثة رؤوس و ضلع واحد.
222- حدد أصغر عدد الأضلاع لبيان مترابط له n من الرؤوس، و عدده اللوني يساوي k (مساعدة : خذ في الحسبان البيانات الجزئية الحرجة من الدرجة Ersov-Kozuhin [1962] k، انظر Bhasicer-Samad-West [1994] من أجل درجات الترابط الأعلى.
223- إذا كان لدينا تلوين أمثل لبيان لوني من الدرجة k (عدده اللوني يساوي k)‎، أثبت أنه يوجد لكل لون i رأس لونه i يجاور رؤوسا ملونة بال k-1 لونا الأخرى.
224- أثبت أنه إذا كان البيان G حرجا لونيا، فإن البيان ׳G المولد من G من خلال بناء مسيلسكس يكون أيضا حرجا لونيا.
225- من بين البيانات البسيطة على n من الرؤوس التي تخلو من عصبة من الدرجة r+1. أثبت أن بيان توران هو البيان الفريد الذي له أكبر عدد من الأضلاع. (مساعدة : تفحص برهان النظرية 9.2.5 بدقة و حذر أكثر)‎.
226- تحصل مدينة دائرية الهيئة قطرها أربعة أميال على 18 محطة تقوية للهواتف المحمولة، و تستطيع كل محطة أن تبث إلى بقية المحطات التي تبعد عنها مسافة أقل أو تساوي ثلاثة أميال. أثبت أن محطتين على الأقل تستطيعان أن تبثا إلى خمس محطات أخرى على الأقل بغض النظر عن كيفية توزيع هذه المحطات في المدينة.
227- افترض أن G بيان يخلو من المخالب (لا يستحدث منه K1,3)‎ : a)‎ أثبت أن البيان الجزئي المستحدث من اتحاد صفين لونيين في أي تلوين فعلي للبيانG يتكون من مسارات و حلقات زوجية. b)‎ أثبت أنه إذا وجد ل G تلوين فعلي يستخدم بالضبط k من الأولان، فإنه يوجد ل G تلوين فعلي من الدرجة k، حيث يختلف حجم الصفوف في هذا التلوين بمقدار 1 على الأكثر، (Niessen-Kind [2000])‎.
228- افترض أن G بيان حرج من الدرجة 4، و له مجموعة فاصلة s حجمها 4. أثبت أنه يوجد للبيان [S]G أربعة أضلاع على الأكثر، (Pritikin)‎.
229- أثبت أن كل بيان بسيط درجته الصغرى تساوي 3 على الأقل يجب أن يحوي تقسيما ل K4. (مساعدة : أثبت النتيجة الأقوى-كل بيان بسيط غير تافه له على الأكثر رأس واحد درجته أقل من 3 يحوي تقسيما ل K4. يوضح برهان النظرية 20.2.5 أن كل بيان مترابط من الدرجة 3 يحوي تقسيما ل Dirac [1952 a], (K4)‎.
230- افترض أن G بيان لوني من الدرجة k. و لاحظ أن البديهية 18.1.5، و الفرضية 8.1.2 تشير إلى أن G يحوي كل شجرة لها k من الرؤوس بوضفه بيانا جزئيا. قم بتقوية هذه النتيجة لبيان مماثل، وضع عليه علامات دالة : إذا كان ƒ تلوينا فعليا ب k من الألوان للبيان G، و كانت T شجرة رؤوسها : [w1, …, wk]، فتوجد دالة : V(T)‎→V(G)‎ ϕ تحافظ على التجاور بحيث إن Ƒ(ϕ)‎ (Wi)‎ )‎=i لكل i. Gyarfas-Szemeredi-Tuza [1980], Summer [1981])‎
231- افترض أن G بيان لوني من الدرجة k خضره يساوي على الأقل، أثبت أن G يحوي كل شجرة على k من الرؤوس بوصفه بيانا جزئيا مسحدثا، (سومنز، جيرفاس، سنرميردي-توزا)‎ .(Gyarfas-Szemerédi-Tuza [1980], Summer [1981])‎
232- استخدم التكرار اللوني للحصول على كثيرة الحدود اللونية لكل شجرة على n من الرؤوس.
233- أثبت أن مجموع معاملات X(G ;K)‎ يساوي صفرا، إلا إذا خلا G من الأضلاع (مساعدة : عندما تكون الدالة كثيرة حدود، فكيف يمكن الحصول على مجموع المعاملات ؟)‎.
234- لتكن P بيان بيترسون. من نظرية بروكس، نعلم أن هذا البيان ثلاثي اللون، لذلك، و باستخدام مبدأ طواقي الحمام، نجد في G مجموعة مستقلة S حجمها 4 : a)‎ أثبت أن P – S = 3K2. باستخدام فرع (a)‎ و التماثل، حدد عدد تجزئات رؤوس P إلى ثلاث مجموعات مستقلة. b)‎ بوجه عام، كيف يمكن الحصول على عدد التجزئات إلى أصغر عدد من المجموعات المستقلة من كثيرة الحدود اللونية للبيان G ؟
235- افترض أن العدد اللوني للبيان G يساوي k. أثبت أنه يوجد على الأكثر kn-k تجزئة لرؤوس G إلى k من المجموعات المستقلة، حيث إن البيان الفريد الذي يحقق المساواة هو Kk + (n-k)‎ K1 (عصبة من الدرجة k إضافة إلى n-k رأسا معزولا)‎. (مساعدة : استخدم الاستقراء على n، و خذ في الحسبان حذف رأس واحد)‎، (Tomescu [1971])‎.
236- استخدم مبدأ التضمين و الاستبعاد لبرهان النظرية 10.3.5 مباشرة.
237- افترض أن G هو البيان الذي نحصل عليه من K6 من طريق قسمة أحد الأضلاع، استخدم التكرار اللوني لحساب X(G ; k)‎ بوصفه حاصل ضرب لعوامل خطية (عوامل على الشكل k-ci)‎. أثبت أن G ليس بيانا و تريا. (Read [1975], Dmitriev [1980])‎)‎.
238- افترض أن G بيان وتري. استخدم ترتيب حذف مبسطي لبيان g لبرهنة العبارات الآتية : a)‎ يوجد ل G على الأكثر n من العصب العظمى، حيث تتحقق المساواة في الحالة التي لا يحوي فيها G أضلاعا. (Fulkerson-Gross [1965])‎. b)‎ إن كل عصبة عظمى في G لا تحوي رأسا مبسطيا للبيان تكون مجموعة فاصلة.
239- افترض أن e ضلع في حلقة C في بيان و تري. أثبت أن e تشكل مثلثا مع رأس ثالث من رؤوس C.
240- افترض أن Q عصبة عظمى في بيان و تري Gـ أثبت أنه إذا كان G – Q بيانا مترابطا، فإن Q تحوي رأسا مبسطيا (Voloshin-Gorgos [1982])‎
241- افترض أن G بيان فترة، أثبت أن G بيان و تري، و أن Ġ بيان مقارنة.
242- يسمى الضلع في البيان G الذي له توجيه لاحلقي بضلع تابع (غير مستقل)‎ إذا حصلنا على حلقة عندما نعكس اتجاهه : a)‎ أثبت أن كل توجيه لا حلقي لبيان مترابط على n من الرؤوس يحوي n – 1 ضلعا مستقلا. b)‎ أثبت أنه إذا كان X(G)‎ أٌقل من خصر G، فإنه يوجد للبيان G توجيه ليس له أضلاع تابعة. (مساعدة : استخدام التقنية الموجودة في برهنة النظرية 21.1.5)‎.
243- إن العدد a(G)‎ للتوجيهات اللاحلقية للبيان G يحقق العلاقة التكرارية a(G)‎ = a(G-e)‎ + a(G. e)‎ (النظرية 27.3.5 فضلا عن أنه من الواضح أن عدد الأشجار المولدة يحقق العلاقة التكرارية نفسها ؛ هل يكون عدد التوجيهات اللاحلقية لبيان G دائما يساوي عدد الأشجار المولدة ؟ و لماذا ؟
244- أثبت العبارة الآتية أو انقضها : يوجد رأس قطع للبيان السوي إذا و فقط إذا كان الممر المحيط بأي وجه حلقة.
245- أثبت أو انقض : a)‎ كل بيان جزئي لبيان سوي يكون سويا. b)‎ كل بيان جزئي لبيان غير سوي يكون غير سوي.
246- أثبت أن البيانات المشكلة بحذف ضلع واحد من K5 و K3,3 تكون بيانات سوية.
247- جد قيم r و s التي تجعل Kr,s سويا.
248- أثبت العبارة الآتية أو انقضها : يوجد رأس قطع للبيان السوي إذا و فقط إذا كان الممر المحيط بأي وجه حلقة.
249- يعرف البيان السوي الخارجي الأعظمي على أنه بيان سوي خارجي بسيط بحيث لا يكون بيانا جزئيا مولدا لبيان سوي خارجي بسيط أكبر. افترض أن G بيان سوي خارجي أعظمي له ثلاثة رؤوس على الأقل. أثبت أن G مترابط من الدرجة 2.
250- أثبت أنه يوجد رأس درجته تساوي 5 على الأكثر في كل بيان سوي بسيط.
251- استخدم النظرية 23.1.6 لتبرهن أن كل بيان بسيط سوي عدد رؤوسه أقل من 12 يحوي رأسا درجته تساوي 4 على الأكثر
252- أثبت العبارة الآتية أو انقضها : لا توجد بيان سوي ثنائي الفرع بسيط درجته الصغرى تساوي 4 على الأقل.
253- افترض أن G بيان سوي أعظمي. أثبت أن G* مترابط ضلعيا من الدرجة 2 و منتظم من الدرجة 3.
254- ابن (جد)‎ بيانا سويا منتظما من الدرجة 3 قطره 3 و له 12 رأسا. (تعليق : أثبت T.Barcume أن مثل هذا البيان ليس له أكثر من 12 رأسا)‎.
255- أثبت العبارة الآتية أو انقضها : إذا كان g بيانا مستويا مترابطا من الدرجة 2 درجته الصغرى 3، فإن البيان الثنوي G* يكون بيانا بسيطا.
256- أثبت بالاستقراء على عدد الأوجه أن البيان المستوي G يكون ثنائي الفرع إذا و فقط إذا كان طول كل وجه عدد زوجيا.
257- أثبت أن مجموعة من الأضلاع في بيان مستو مترابط G تشكل شجرة مولدة ل G إذا و فقط كانت الأضلاع الثنوية للأضلاع المتبقية في G تشكل شجرة مولدة ل G*.
258- البيان الثنوي الضعيف (WeaK dual)‎ للبيان G هو البيان الذي نحصل عليه من G* بحذف الرأس الموجود في الوجه G. أثبت أن البيان الثنوي الضعيف لبيان مستو خارجي عبارة عن غابة.
259- إثبات بديل لصيغة أويلر : a)‎ استخدم المنحنيات المضلعة (ليست صيغة أويلر)‎ للإثبات بالاستقراء على n(G)‎ أن كل طمر سوي لشجرة G يحوي وجهها واحد. b)‎ أثبت صيغة أويلر بالاستقراء على عدد الحلقات.
260- أثبت أن كل بيان مستو على n من الرؤوس يشاكل بيانه الثنوي يجب أن يحوي 2n-2 ضلعا. و لكل n≥4 جد بيانا مستويا بسيطا على n من الرؤوس يشاكل بيانه الثنوي.
261- لكل n≥2، جد أكبر عدد من الأضلاع في بيان خارجي بسيط له n من الرؤوس بإعطاء ثلاثة براهين كالآتي : a)‎ بالاستقراء على n. b)‎ باستخدام صيغة أويلر. c)‎ بإضافة رأس في الوجه غير المحدود، و استخدام النظرية 23.1.6.
262- أفترض أن G بيان مستو منتظم من الدرجة 3، و مترابط بحيث يقع كل رأس من رؤوسه في وجه واحد طوله يساوي 4، و كذلك في وجه واحد طوله 6، و في وجه طوله 8 أيضا : a)‎ حدد عدد الأوجه من كل طول بدلالة n(G)‎. b)‎ استخدم صيغة أويلر و فرع (a)‎ لتحديد عدد أوجه G.
263- أثبت أن متممة البيان السوي البسيط الذي له 11 رأسا على الأقل هي بيان غير سوي. ابن بيانا سويا بسيطا على ثمانية رؤوس بحيث يكون هذا البيان ذاتي التتام (Self Complementary)‎ أي أن متممته هي البيان نفسه.
264- افترض أن G بيان سوي أعظمي. أثبت أنه إذا كانت S مجموعة ثلاثية فاصلة للبيان G*، فإن G*-S يحوي مركبتين (chappell)‎.
265- ابن عائلة غير منتهية من البيانات السوية البسيطة التي درجتها الصغرى تساوي 5 بحيث يكون لكل منها 12 رأسا درجة كل منها تساوي 5 (مساعدة : عدل الثنعشري)‎.
266- أثبت أنه إذا كان G بيانا سويا بسيطا له أربعة رؤوس على الأقل، فيوجد فيه أربعة رؤوس على الأقل درجة كل منها أقل من 6 لكل قيمة من قيم n الزوجية حيث n ≥ 8، جد بيانا سويا بسيطا على n من الرؤوس له أربعة رؤوس بالضبط، درجة كل منها أقل من 6، (Grtinbaum – MotzKin [1963])‎.
267- افترض أن S مجموعة n من النقاط في المستوى بحيث تساوي المسافة بين x و y في المستوى 1 على الأقل لكل x,y ϵ S. أثبت أنه يوجد على الأكثر 3n – 6 زوجا v.u في S بحيث تساوي المسافة في المستوى بين u و بالضبط 1v.
268- إذا أعطيت أعدادا صحيحة k ≥ 2 و l ≥ 1 بحيث إن Kl عدد زوجي، فابن بيانا سويا له K وجها بالضبط، و طول كل وجه من هذه الوجوه يساوي l.
269- حدد أقل عدد من الأضلاع بمكن حذفه من بيان بيترسون للحصول على بيان جزئي سوي.
270- نظرية فاري. افترض أن R منطقة محاطة بمتعدد أضلاع بسيط له على الأكثر خمس حواف (يعني مضلع بسيط أن الأضلاع عبارة عن قطع مستقيمة لا تتقاطع)‎. أثبت أنه يوجد في R نقطة ترى R كلها، بمعنى أن القطعة المستقيمة من x إلى أي نقطة في R لا تقطع حدود R استخدم هذا لتبرهن استقرائيا أنه يوجد لكل بيان سوي طمر على شكل خطوط مستقيمة.
271- استخدم نظرية كوارتوسكي لتبرهن أن البيان G يكون سويا خارجيا إذا و فقط إذا خلا G من بيان جزئي يشكل تقسيما ل K4 أو ل K23 (مساعدة : لتطبيق نظرية كورارتوسكي ؛ جد تعديلا مناسبا ل G أن هذا أسهل كثيرا من تقليد إثبات نظرية كواراتوسكي)‎.
272- إذا كان هناك بيان مترابط من الدرجة 3، و له ستة رؤوس على الأقل، و يحوي تقسيما ل K5، فبرهن أن G يحوي تقسيما ل K3,3، (Wagner [1937])‎.
273- أفترض أن H بيان، درجته الكبرى تساوي 3 على الأكثر. أثبت أن بيانا G يحوي تقسيما ل H إذا و فقط إذا كان G يحوي بيانا جزئيا قابلا للتقليص إلى H
274- لقد أثبت و اجنر العام 1937 م أن الشرط الثاني ضروري و كاف ليكون البيان Gسويا، و هو : لا يمكن الحصول على K5 أو K3,3 من خلال إجراء عمليات الحذف و التقليص للأضلاع : a)‎ أثبت أن حذف الأضلاع و تقليصها يحافظ على السوية، و استنتج من ذلك أن شرط و اجنر ضروري. b)‎ استخدم نظرية كواراتوسكس لإثبات أن شرط واجنر كاف.
275- أثبت أن البيان G يكون سويا إذا و فقط إذا كان بيان تعارض كل حلقة C في G ثنائي الفرع (Tutte [1958])‎.
276- افترض أن x و y رأسان لبيان سوي G أثبت أن يوجد ل G طمر سوي فيه x و y على الوجه نفسه إلا إذا وجدت حلقة C في G – x – y، بحيث إن x و y ينتميان إلى شظايا C- متعارضة في G (مساعدة : استخدام نظرية كواراتوسكي. تعليق : لقد أثبت توت هذا النتيجة دون استخدام نظرية كواراتوسكي كما استخدمها لإثبات هذه النظرية)‎.
277- افترض أن G بيان مستو بسيط مترابط من الدرجة 3 يحوي حلقة C أثبت أن C لكون حدودا لوجه في G إذا و فقط إذا وجدت في G شظية –C واحدة بالضبط. (تعليق : لقد أثبت توت عام 1963 م هذه النتيجة للحصول على نتيجة ويتني (Whitneys [1933b])‎ و هي أنه يوجد-مبدئيل- طمر سوي واحد فقط للبيانات السوية المترابطة من الدرجة 3. انظر أيضا (Kelmans [1981a])‎.
278- افترض أن G بيان سوي خارجي له n من الرؤوس، و افترض أيضا أن P مجموعة فيها n نقطة في المستوى، بحيث إنه لا توجد ثلاثة منها على الخط نفسه إن النقاط القصوى ل P تحدث مضلعا محدبا يحوي باقي النقاط في داخله : a)‎ افترض أن P1 و p2 نقاط قصوى متتابعة في P، أثبت على وجود نقطة p ϵ P-[p1, p2] بحيث إن : 1)‎ لا توجد أي نقطة من P داخل P1P2P)‎ و 2)‎ يوحد خط 1 يمر في P و يفصل P1 عن P2، و يقطع P فقط عند P، و يوجد بالضبط 2-1 نقطة من نقاط P محتواة في جانب L الذي يحوي P2، b)‎ أثبت أنه يوجد ل G طمر على شكل خطوط مستقيمة بحيث ترسل رؤوسها إلى P كلها. (مساعدة : استخدم فرع (a)‎ لإثبات النتيجة الأثوى و هي أنه : إذا كان كل من v1 و v2
279- استخدم نظرية الألوان الأربعة لتبرهن أن كل بيان سوي خارجي يكون قابلا للتلوين بثلاثة ألوان.
280- هات نصا لخوارزمية كثيرة حدود زمنية بحيث تأخذ بيانا سويا كمدخل، و تنتج تلوينا فعليا لخمسة ألوان لهذا البيان.
281- يكون البيان G مضمحلا (متفسخا)‎ من الدرجة k (k-degenerate)‎ إذا وجد في كل بيان جزئي منه رأس درجته تساوي k على الأكثر، أثبت أن البيان المضمخل (المتفسخ)‎ من الدرجة k يكون قابلا للتلوين ب k + 1 لونا.
282- جد عدد التقاطع لكل من K2,2,2,2 و K4,4، و عدد التقاطع لبيان بيترسون كذلك.
283- استخدم نظرية الأولان الأربعة لتبرهن أن كل بيان سوي بتفكك إلى بيانين ثنائيي الفرع. (Hedetniemi [1969]. Mabry [1995])‎
284- دون استخدام نظرية الألوان الأربعة، أثبت أن كل بيان سوي له 12 رأسا على ألأكثر يكون قابلا للتلوين بأربعة ألوان. استخدم هذا لتبرهن أن كل بيان سوي له 32 رأسا على الأكثر يكون قابلا للتلوين بأربعة ألوان.
285- افترض أن H تشكل في تثليث سوي (التعريف 2.3.6)‎. و افترض كذلك أن ’H هو البيان الذي نحصل عليه من وضع درجات الرؤوس كعلامات دالة على جيران رؤوس الحلقة، و من ثم نحذف رؤوس الحلقة. أثبت إمكانية استرداد H من ’H.
286- جد تشكلا حجم حلقته يساوي 5 في تنثليث سوي، بحيث إن درجة كل رأس تساوي 5 على الأقل، و بحيث يوجد أكثر من رأس داخلي واحد.
287- أثبت أن كل تشكل سوي حجم حلقته يساوي 4 على الأكثر يكون مصغرا. (مساعدة : الحلقة عبارة عن حلقة فاصلة C. أثبت أنه إذا كانت التثليثات الأصغر قابلة للتلوين بأربعة ألوان، فإن للفلق C- من G أربعة ألوان تتوافق على C)‎، (BirKhoff [1913])‎.
288- نعرف صالة عرض (معرض)‎ الآثار (الفنون)‎ الذي له جدران على أنه مضلع إضافة إلى بعض الأوتار غير المتقاطعة التي تسمى "جدرانا" و التي تصل (تربط)‎ بين الرؤوس كل جدار داخلي يحتوي على فتحة صغيرة تسمى "مدخلا" إذا وضع الحارس على المدخل، فإنه لا يستطيع رؤية كل شيء داخل الغرفتين المتجاورتين، و لكن الحارس الذي لا يكون موجودا في المدخل، فإنه لا يستطيع أن يرى أبعد من الجدار. حدد أصغر عدد t من الحراس يلزم استخدامه لحراسة معرض فني له جدران بحيث تكون كل نقطة داخلية مرئية من قبل أحد الحراس . (Hutchinson [1995] .RStinalgen[1999])‎
289- أثبت أن البيان السوي الأعظمي يكون قابلا للتلوين بثلاثة ألوان إذا و فقط إذا كان هذا البيان أويلريا. (مساعدة : لإثبات الكفاية ؛ استخدم الاستقراء على n(G)‎ اختر زوجا مناسبا أو ثلاثة رؤوس متجاورة لاستبدالها بأضلاع)‎ (Heawood [1898])‎.
290- أثبت أنه يمكن تجزئة رؤوس بيان سوي خارجي بسيط إلى مجموعتين، بحيث يكون البيان الجزئي الذي تحدثه كل مجموعة عبارة عن اتحاد منفصل لمسارات (مساعدة : عرف تجزئة باستخدام نوعية المسافة (زوجية أم فردية)‎ بالنسبة إلى رأس مثبت)‎. (Mih6K-[1983] .AKiyama-Era-Geryacia-Watanabel 1989].Goddard [1991])‎
291- أثبت أن المكعب الرباعي Q4 بيان غير سوي. فكك Q4 إلى بيانين متشاكلين سويين لذا، فإن سمك Q4 يساوي 2.
292- فكك K9 إلى ثلاثة بيانات سوية متشاكلة زوجا زوجا.
293- أثبت أنه لا يوجد بيان جزئي سوي منK3,2,2 بحيث يكون لهذا البيان الجزئي 15 ضلعا، و استخدم هذا لتعطي إثباتا ثانيا لحقيقة أن v(K3,2,2)‎≥2.
294- ليكن Mn البيان الذي نحصل عليه من الحلقة Cn بإضافة أوتار تربط بين الرؤوس المتقابلة (إذا كان n عددا زوجيا)‎، و تربط بين الرؤوس شبه المتقابلة (إذا كان n عدد فرديا)‎. إن البيان M منتظم من الدرجة 3 إذا كان n زوجيا، و منتظم من الدرجة 4 إذا كان n عددا فرديا. جد v(Mn)‎، (Guy-Harary [1967] )‎.
295- لكل عدد صحيح موجب k، ابن (جد)‎ بيانا يمكن طمره على الطارة إلا أن رسمه في المستوى يحوي K تقاطعا على الأقل (مساعدة : يكفي إعطاء عائلة طارية (يمكن طمرها على الطارة)‎ واحدة بحيث تكون سهلة الوصف : استخدم القضية 13.3.6)‎.
296- جد (ابن)‎ طمرا على الطارة لبيان بسيط غير ثنائي الفرع منتظم من الدرجة 3 بحيث يكون طول كل وجه فيه عدد زوجيا.
297- نقول : إن طمر لبيان على سطح معين يكون منتظما إذا كان لوجوهه جميعها الطول نفسه جد طمرا منتطما على الطارة لكل من : K4,4، و K3,6، و K3,3.
298- أثبت صيغة أويلر للجنس :y إن عدد رؤوس أي طمر و أضلاعه و أوجهه لخلية ثنائية لبيان على سطح Sy يحقق العلاقة n-r+f=2-2y. استنتج من ذلك أنه يوجد (n-2+2y)‎3 ضلعا على الأكثر لبيان بسيط له n من الرؤوس، و قابل للطمر على Sy.
299- لكل عدد صحيح موجب k، استخدم صيغة أويلر لتبرهن أنه يوجد بيان سوي G، بحيث إن k≤Y(G □ K2)‎
300- أثبت أن بيان بيترسون لا يملك بيانا جزئيا فوق الممتلئ.
301- أعط تلوينا ضلعيا صريحا لإثبات أن Xʼ(Qk)‎ = ∆(Qk)‎.
302- حدد العدد اللوني الضلعي للبيان Cn □ K2.
303- احصل على متباينة ل Xʼ(G)‎ بدلالة e(G)‎ و aʼ(G)‎.
304- أثبت أن بيان بيترسون هو المتممة ل L(K5)‎.
305- حدد عدد المثلثات في البيان الخطي لبيان بيترسون.
306- ليكن G بيانا بسيطا يخلو من الرؤوس المعزولة. أثبت أنه إذا كان L(G)‎ مترابطا و منتظما، فإما أن يكون G منتظما، أ, أن يكون بيانا ثنائي الفرع بحيث تكون درجات الرؤوس في كل مجموعة مجزأة متساوية. (Ray-Chaudhuri [1967])‎
307- ليكن G بيانا بسيطا مترابطا ضلعيا من الدرجة k. أثبت أن L(G)‎ مترابط من الدرجة k، و مترابط ضلعيا من الدرجة 2k-2. (مساعدة : للقطع الضلعي الأصغر [S,Ṡ] في L(G)‎، صف ماذا يقابل القطع في G، و احسب عدد أضلاعه بدلالة الرؤوس في G)‎.
308- أعط تلوينا ضلعيا صريحا لتثبت أن Xʼ(Kr,s)‎ = ∆ (Kr,s)‎.
309- أثبت أنه يوجد لكل بيان ثنائي الفرع G بيان H ثنائي الفرع بسيط منتظم من الدرجة ∆(G)‎ يحوي G.
310- إثبات خوارزمي للنظرية 7.1.7 ليكن G بيانا ثنائي الفرع مع درجة كبرى تساوي k. و ليكن ƒ تلوينا ضلعيا فعليا من الدرجة k لبيان جزئي H من G. و ليكن uv ضلعا ليس في H. باستخدام مسار يتناوب مسار في لونين، أثبت أن ƒ يمكن أن يبدل، ثم يوسع إلى تلوين ضلعي فعلي من الدرجة k ل H+uv. استنتج أن∆(G)‎ Xʼ(G)‎ =.
311- استخدم نظرية بروكس في بيان ملائم لتثبت أنه إذا كان G بيانا بسيطا له ∆(G)‎ =3، فإنه قابل للتلوين الضلعي من الدرجة 4. (تعليق : النتيجة هي حالة خاصة من نظرية فايزنج ؛ لا تستخدم نظرية فايونج لإثبات هذا)‎.
312- ليكن G و H بيانين بسيطين غير تافهين. استخدم نظرية فايزنج لتثبت أن ∆(H)‎ Xʼ(H)‎ =. يؤدي إلى أن∆(G □ H)‎ Xʼ(G □ H)‎ =.
313- مخمنة فوق الممتلئ ← مخمنة التحليل إلى العوامل من الدرجة 1 (الملاحظة 12.1.7)‎ : a)‎ أثبت أنه في البيان المنتظم الذي درجته زوجية، يكون البيان الجزئي المحدث فوق ممتلئ إذا و فقط إذا كان البيان الجزئي المحدث من بقية الرؤوس فوق ممتلئ. b)‎ ليكن G بيانا بسيطا منتظما من الدرجة k درجته 2m، ويملك بيانا جزئيا فوق ممتلئ. أثبت أن k
314- إذا أعطيت تلوينا ضلعيا للبيان G، اجعل c(v)‎ يرمز إلى عدد الألونا المختلفة التي تظهر على الأضلاع الواقعة v. من بين التلوينات الضلعية جميعها التي درجتها k للبيان G، يكون تلوين ما هو الأمثل ()‎ إذا كان يعظم :∑vϵv(G)‎c(v)‎ a)‎ أثبت أنه إذا كان لم تكن أي مركبة ل G حلقة فردية، فإن g يملك تلوينا ضلعيا من الدرجة 2 حيث يظهر كلا اللونين عند كل رأس درجته 2 على الأقل. (مساعدة : استخدم الحلقات الأويلرية)‎. b)‎ ليكن ƒ تلوينا ضلعيا أمثل من الدرجة k، بحيث يظهر اللون a على الأقل مرتين عند الرأس uϵV(G)‎، أما اللون b فلا يظهر عند u. و ليكن H التي تحتوي u هي حلقة فردية. c)‎ ليكن G بيانا ثنائي الفرع. استنتج من الفرع (b)‎ أن G قابل للتلوين الضلعي من الدرجة ∆(G)‎ (تعليق : تقود هذه الأفكار لإثبات نظرية فايزنج.)‎ (Fournier [1973])‎
315- ل n≠8، أثبت أن L(Kn)‎ هو البيان البسيط المنتظم من الدرجة (2n-4)‎ الوحيد الذي رتبته (n2)‎ بحيث تملك الرؤوس غير المتجاورة أربعة جيران مشتركة، في حين تمتلك الرؤوس المتجاورة n-2 جارا مشتركا. (تعليق : عندما n = 8، فإن ثلاثة بيانات استثنائية تحقق الشروط)‎. .(Hoffman [1960]. Chang[1959])‎
316- أثبت أن كل مسار في ذي الاثني عشر وجها يقع في حلقة هاملتونية.
317- لأي القيم r يكون Kr,r هاملتونيا ؟
318- ل n˃1، أثبت أن Kn,n يملك (n-1)‎!n!/2 حلقة هاملتونية.
319- ليكن G بيانا ثنائي الفرع هاملتونيا، و اختر x,y ϵV(G)‎. أثبت أن G-x-y يملك مواءمة تامة إذا و فقط إذا كان من x و y على جهتين مختلفتين من التجزئة الثنائية ل G. طبق هذا لتثبيت أن حذف مربعي وحدة من لوحة الشطرنج (8 x 8)‎ يبقى على لوحة يمكن أن تجزأ إلى مستطيلات 1 في 2 إذا و فقط إذا تحقق أن المربعين المحذوفين يملكان لونين مختلفين.
320- يأكل فأر مكعب 3 x 3 x3 من الجبن بأكل المكعبات الجزئية 1 x 1 x 1 جميعها. إذا بدأ عند زاوية مكعب جزئي، و في كل مرة يتحرك إلى مكعب جزئي (تشارك بوجه مساحته 1)‎، هل يستطيع الفأر عمل هذا و الانتهاء بأكل المكعب الجزئي الذي في المركز ؟ هات طريقة لعمل ذلك، أو أثبت استحالة ذلك (تجاهل الجاذبية)‎.
321- أنشئ عائلة مكونة من عدد لا نهائي من البيانات غير الهاملتونية التي تحقق الشرط الضروري لقضية 3.2.7.
322- هاملتوني مقابل أويلري : a)‎ جد بيانا غير أويلري مترابطا من الدرجة 2 بحيث يكون بيانه الخطي هاملتونيا. b)‎ أثبت أن L(G)‎ يكون هاملتونيا. إذا و فقط إذا كان G يملك مسربا مغلقا يحتوي على نقطة طرفية واحدة على الأقل من كل ضلع. (Harary, Nash-Williams [1965])‎
323- ليكن G البيان المنتظم من الدرجة 3 الذي نحصل عليه من بيان بيترسون باستبدال مثلث بأحد الرؤوس، و من ثم مواءمة رؤوس المثلث مع جيران الرأس المحذوف. أثبت أن G ليس هاملتونيا. (تعليق : ما عدا هذا البيان و بيان بيترسون، فإن كل بيان منتظم من الدرجة k، و مترابط من الدرجة 2 و له 3k+3 رأسا على الأكثر يكون هاملتونيا)‎. (Hilbig [1986])‎
324- يكون البيان G قابلا للتلوين الضلعي من الدرجة k بصورة فريدة (uniquely)‎ إذا كانت التلوينات الضلعية الفعلية من الدرجة k للبيان G جميعها تحدث التجزئة للأضلاع نفسها. أثبت أن كل بيان منتظم من الدرجة 3 قابل للتلوين الضلعي من الدرجة 3 بصورة فريدة يكون هاملتونيا. (Greenwell-Kronk [1973])‎
325- ضع n نقطة حول دائرة. ليكن Gn هو البيان المنتظم من الدرجة 4 الذي نحصل عليه بضم كل نقطة إلى أقرب نقطتين إليها في كل اتجاه. إذا كان n≥5، فأثبت أن Gn هو اتحاد لحلقتين هاملتونيتين.
326- أثبت أن الجداء الديكارتي لبيانين هاملتونينا. استنج أن المكعب Qk ذا البعد k هامتلوني لكل k≥2.
327- ليكن G(k,t)‎ صف البيانات التي لها k فرعا و المترابطة بحيث تكون كل مجموعة مجزأة حجمها t، و كل بيان جزئي محدث من مجموعتين مجزأتين هو مواءمة حجمها t. ل k≥4 و t≥4ـ أنشئ بيانا في G(k,t)‎ بحيث يكون غير هاملتوني. (مساعدة : يوجد بيان في G(4,4)‎ مع مجموعة فيها 3 عناصر، و حذفها يخلف أربع مركبات ؛ عمم هذا المثال. تعليق :G(3,t)‎ = [C3t]، و أيضا كل بيان في G(k,3)‎ يكون هاملتونيا)‎ (Ayel [1982])‎
328- أثبت أن المتانة لبيان بيترسون هي 3/4.
329- ليكن t(G)‎ يرمز إلى المتانة ل G : a)‎ أثبت أن. t(G)‎ ≤k(G)‎/2 (Chvẚtal[1973])‎. b)‎ أثبت أن المساواة تتحقق في فرع (a( للبيانات التي تخلو من المخالب. (مساعدة : خذ في الحسبان مجموعة S حيث ǀSǀ=t(G)‎. c(G-S)‎ ( Mattews-Sumner[1984])‎.
330- ليكن G بيانا بسيطا و ليس غابة، و يملك خصرا يساوي 5 على الأقل. أثبت أن Ġ يكون هاملتونيا. (مساعدة : استخدام شرط أور (Ores condition)‎ (N. Graham)‎
331- احصل على تمهيدية 9.2.7 (الكفاية لشرط أور)‎ من النظرية 13.2.7 (الكفاية لشرط كفتال)‎. (Bondy [1978])‎
332- أثبت أو انقض : إذا كان G بيانا بسيطا له ثلاثة رؤوس على الأقل، و كان يملك a(G)‎ رأسا على الأقل درجاتها n(G)‎-1، فإنه يكون هاملتونيا.
333- ليكن G بيانا بسيطا ثنائي بالتجزئة الثنائية X,Y حيثn/2 >1 ǀXǀ = ǀYǀ =. و لتكن dn،....،d1 هي درجات الرؤوس فيه، حيث d1≤…≤ dn. ليكن Gʼ هو أصغر بيان حاو للبيان (supergraph)‎G بحيث Gʼ[Y] = Kn/2 : a)‎ أثبت أن G يكون هاملتونيا إذا و فقط إذا كان Gʼ هاملتونيا. وصف العلاقة بين متتاليتي الدرجات لكل من G و Gʼ. b)‎ افترض أن dk>k أو dn/2>n/2-k عندما k≤n/4. أثبت أن G يكون هاملتونيا. (مساعدة : افترض أن متتالية الدرجة ل Gʼ لا تحقق شرط كفتال لبعض قيم i
334- شرط ضروري لمترابط هاملتوني : (Moon [1965a])‎. a)‎ أثبت أن كل بيان مترابط هاملتوني على أربعة رؤوس على الأقل يملك [3n(G)‎/2 ضلعا على الأقل. b)‎ أثبت أن الحد في فرع (a)‎ هو أفضل ما يمكن بإثبات أن Cm □ K2 يكون مترابطا هاملتونيا إذا كان m فرديا.
335- أثبت أنه إذا كان G بيانا بسيطا بحيث متتالية درجاته هي dn≥...≥d1 و كان d1+d2، فإن G يملك مسار طوله على d1+d2+1، إلا إذا كان G هو الرابط n-( d1+1)‎ رأست معزولا مع بيان d1+1 من الرؤوس، أو كان G=pkd1V K1 لبعض قيم P ≥3 ([1967b]Ore )‎.
336- لقد خمن سكوت سميت أن إذا أخذنا أي أطول حلقتين في بيان مترابط من الدرجة k دائما فإنهما تملكان k رأسا مشتركا على الأقل. إن طريق الحل أدناه يصلح لقيم k الصغيرة : a)‎ افترض أن G بيان منتظم من الدرجة 4 على n من الرؤوس بحيث إن G هي إتحاد لحلقتين ( قد تظهر أضلاع متكررة)‎. ليكن Gʼ بيانا منتظما من الدرجة 4 على n+2 من الرؤوس، و بحيث نحصل عليه من G بتقسيم جزئي لضلعين، و إضافة ضلع مزدوج بين الرأسين الجديدين. بين أن Gʼ هو أيضا اتحاد لحلقتين مولدتين إذا كان n≤5. b)‎ استخدم فرع (a)‎ لتستنتج أن أي زوج من الحلقات الأطول في بيان مترابط من الدرجة k يتقاطع في k نقطة على الأقل إذا كان k≤6 (Burr, Smith)‎.
337- ليكن G بينا أويلري. و لتكن Vʼ هي مجموعة الحلقات الأويلرية في G، مع الأخذ في الحسبان أن حلقة و معكوسها هما الشيء نفسه. افترض أن Gʼ هو البيان على مجموعة الرؤوس Vʼ بحيث تكون حلقتان متجاورتين إذا و فقط إذا كانت إحداهما تظهر من الأخرى بعكس الترتيب الضلعي على حلقة جزئية مغلقة فعلية. أثبت أن Gʼ يكون هاملتونيا إذا كان ∆(G)‎ ≤ 4. (مساعدة : استخدم الاستقراء على الرؤوس التي درجتها 4، و هذا يثبت وجود حلقة هاملتونية لكل ضلع في Gʼ. (تعليق : يتحقق الاستنتاج أيضا دون تقييد على ∆(G)‎ (Zhang- Guo [1986] Xia [1982])‎
338- أثبت أن كل دوري يملك مسار هاملتونيا (مسار موجه مولد)‎. (مساعدة : استخدم التطرفية)‎. (Re'dei [1934])‎
339- أحصل على النظرية 8.2.7 (الكفاية لشرط ديراك في البيانات)‎ من النظرية 22.2.7 (الكفاية لشرط غويلا و هوري على البيانات الموجهة)‎. (مساعدة : حول بيانا بسيطا G إلى بيان موجه صارم باستبدال كل ضلع بزوج من الأضلاع الموجهة في اتجاهين متعاكسين)‎.
340- أثبت أن كل بيان هاملتوني منتظم من الدرجة 3 يملك تلوبن تايت.
341- اعرض بيانات بسيطة منتظمة من الدرجة 3 تكون : a)‎ سويةـو لكنها غير قابلة للتلوين الضلعي من الدرجة 3. b)‎ مترابطة من الدرجة 2، و لكنها غير قابلة للتلوين الضلعي من الدرجة 3. c)‎ سوية مع ترابط 2، و لكنها ليست هاملتونية.
342- أثبت أن كل بيان مستوي أعظمي غير K4 يكون قابلا للتلوين الوجهي من الدرجة 3.
343- دون استخدام نظرية الأولان الأربعة، أثبت أن كل بيان مستو هاملتوني يكون قابلا للتلوين الوجهي من الدرجة 4 (دون أي افتراض حول درجات الروؤس)‎.
344- ليكن G تثليثا مستويا : a)‎ أثبت أن الثنوي G* يملك معاملا من الدرجة 2. b)‎ استخدم فرع (a)‎ لتثبيت أن الرؤوس في G من الممكن أن تلوين بلونين بحيث يملك كل وجه رؤوس كلا اللونين. (مساعدة : استخدم الفكرة في الإثبات لنظرية (2.3.7)‎ Penaud [1975], Burstein [1974]
345- أثبت أن تلوينا فعليا من الدرجة 4 للبيان ذي العشرين وجها يستعمل كل لون 3 مرات بالضبط.
346- لقد أثبت ويتني [1931]أن كل تثليث سوي مترابط من الردجة 4 يكون هاملتونيا. استخدم هذا لتحخفف مسألة الألوات الأربعة إلى المسألة التي تثبت أن كل بيان سوي هاملتوني قابل للتولين من الدرجة 4.
347- جد بيانا سويا مترابطا من الدرجة 5. هل يوجد بيان سوي مترابط من الدرجة 6 ؟
348- ليكن G تثليثا مستويا. أثبت أنه يملك تجزئة رأسية إلى مجموعتين محدثا غابات إذا و فقط إذا كان G* هاملتونيا. (Stein [1970])‎
349- ليكن G بيانا منتظما من الدرجة 3. أثبت أنه إذا كان G اتحادا لحقلتين، فإنه يكون قابلا للتلوين الضلعي من الدرجة 3.
350- "سناركات الزهرة" ليكن Gk و Hkأنشئا في (المثال 13.3.7)‎ : a)‎ أثبت أن Gk قابل للتلوين الضلعي من الدرجة 3. b)‎ أثبت أن Hk غير قابل للتلوين الضلعي من الدرجة 3 عندما يكون k فرديا. (Isaacs [1975])‎
351- أثبت أن كل قطع ضلعي ل Kk □ Ct و الذي لا يعزل رأسا يملك 2k ضلعا على الأقل.
352- أثبت أن تطبيق عملية الجداء النقطي (التعريف 12.3.7)‎ على سناركين يعطي سناركا ثالثا. ([1975] Isaacs)‎.
353- أثبت أن كل بيان هو بيان التقاطع لعائلة من الأشجار الجزئية لبيان معين.
354- تسمى البيانات التي تخلو من P4 مرافقات البيانات ()‎ و التي ترمز إلى " تصغير المتممة" نقول : إن البيان هو تصغير متممة إذا أمكن تصغير هذا البيان إلى البيان الخالي عن طريق أخذ متممات المركبات (مركبات البيان)‎ بالتتابع : a)‎ أثبت أن البيان G يخلو من P4 إذا و فقط كان تصغير متممة. b)‎ استخدم الفرع (a)‎ و نظرية البيان الكامل لتبرهن أن كل بيان خال من P4 يكون كاملا. (Seinsche [1974])‎
355- تحديد العصب. افترض أن G = G1UG2، و أن G1∩G2 عصبة، و أن G1 و G2 بيانات كاملة. أثبت أن G يكون بيانا كاملا دون استخدام تمهيدية مجموعة قطع النجمة.
356- جد بيانا ناقصا G له مجموعة قطع النجمة C بحيث إن القلق C- للبيان G هو بيانات كاملة (تعليق : التحديد عند مجموعات قطع النجمة لا يحافظ على الكمال، ع الرغم من عدم وجود مجموعة قطع النجمة للبيانات الحرجة من الدرجة P)‎.
357- افترض أن G حاصل الضرب الكارتيزي لبيانات تامة. أثبت أن a(G)‎=ᶿ (G)‎، و برهن كذلك أن k2 □ k2 □k2 غير كامل.
358- أثبت أن C5 V K1 هو البيان الوحيد الحرج لونيا الذي درجته اللونية تساوي 4، و له ستة رؤوس.
359- أثبت أن G حلقة فردية إذا و فقط ‘ذا كان a(G)‎ = (n(G-1)‎ / 2 و a(G-u-v)‎ = a(G)‎ لكل u.v ϵ V(G)‎ (Melnikov-vizing [1971], Greenwell [1978])‎.
360- أصف اختبارا لخوارزمية أل MCS ؛ لتختبر ما إذا كان الترتيب الناتج ترتيب حذف مبسطي (Tarjan-Yannakakis [1984].
361- أثبت مباشرة (دون استخدام ترتيب الحذف الميسطي)‎ أن بيان التقاطع لعائلة أشجار حزئية من شجرة معينة لا يحوي حلقة غير وترية.
362- أثبت أنه يوجد لكل بيان وتري تمثيل تقاطع بأشجار جزئية لسجرة مضيفة درجتها الكبرى تساوي 3.
363- افترض أن Q عصبة عظمى في بيان وتري G، لكل x ϵV(G)‎، أثبت أنه يوجد ل Q رأسان، بحيث أن بعد كل منهما عن x يكون مختلفا عن بعد الآخر، (Voloshin [1982])‎.
364- بيانات تقاطع الأشجار الجزئية لبيان. يعرف التوجيه الأخوي (الودي)‎ لبيان على أنه توجيه للبيان، بحيث يكون كل زوج من الرؤوس التي لها تابع (خلف)‎ مشترك متجاورا : a)‎ (-)‎ أثبت أن البيان يكون بيانا وتريا إذا و فقط إذا وجد له توجيه أخوي غير حلقي. b)‎ (-)‎ احصل على بيان ليس له توجيه أخوي. c)‎ تعد عائلة من الأشجار في بيان معين قابلة للتجذير إذا أمكن تعيين جذور لهذه الأشجار بحيث بتقاطع زوج منها إذا انتمى أحد الجذرين على الأقل إلى كلتا الشجرتين الجزئيتين. أثبت أن للبيان G توجيها أخوي إذا و فقط إذا كان G بيان تقاطع لعائلة أشجار جزئية لبيان معين، و بحيث تكون هذه العائلة قابلة للتجذير.
365- أثبت أن البيان البسيط G يكون غابة إذا و فقط إذا وجد رأس مشترك لكل عائلة مسارات متقاطعة زوجا زوجا في G. (مساعدة : لإثبات الكفاية ؛ استخدم الاستقراء على عدد المسارات في العائلة)‎.
366- توصيف بيانات الانشقاق بمنع بعض البيانات الجزئية. نقول : إن البيان بيان انشقاق إذا أمكن تجزئة رؤوسه إلى عصبة و مجموعة مستقرة : a)‎ أثبت أنه إذا كان G بيان انشقاق فإن G و Ġ يكونان بيانين و تريين. لاحظ أنه إذا كان كل من G و Ġ بيانا وتريا، فلا يوجد للبيان G بيانات جزئية مستحدثة ضمن المجموعة {C4, 2K2, C5}. b)‎ أثبت أنه إذا كان G بيانا بسيطا بحيث لا يوجد له بيان جزئي مستحدث ضمن المجموعة {C4, 2K2, C5}، فإنه يكون بيان انشقاق. (مساعدة : من بين العصب ذات الحجم الأكبر، افترض أن Q أحد هذه العصب بحيث يكون عدد أضلاع G-Q أقل ما يمكن. أثبت أن G-Q تكون مجموعة مستقرة من خلال استخدام خيار Q، و شروط البيانات الجزئية الممنوعة)‎، (Hammer-Simeone [1981])‎.
367- حدد الأشجار التي تكون بيانات انشقاق، و ابن زوجا من بيانات الانشقاق غير المتشاكلة التي لها متتالية الدرجات نفسها.
368- تعرف الأشجار من نوع k على أنها البيانات التب تظهر من عصبة من الدرجة K بتكرار إضافة 0 أو أكثر من الرؤوس الجديدة التي تربط بالعصبة في البيان القديم. أثبت أن G يكون سجرة من نوع K إذا و فقط إذا حقق الخواص الثلاث الأتية : a)‎ إذا كان مترابطا. b)‎ إذا كانت له عصبة من الدرجة k،و لكن لا توجد له عصبة من الدرجة k+2. c)‎ إذا كان كل فاصل رؤوس أصغري له عصبة من الدرجة k.
369- خاصية هيلي لخطا الأعداد الحقيقية. افترض أن Ik,...،I1 فترات حقيقة متقاطعة زوجا زوجا . أثبت أنه توجد نقطة مشتركة بين Ik,...،I1
370- أثبت مباشرة أن الشجرة تكون بيان فترة إذا و فقط إذا كانت جرارة (شجرة تحوي مسارا يحوي الأقل رأسا لكل ضلع)‎.
371- افترض أن G بيان فترة. أثبت أن Ġ بيان مقارنة، و أن G بيان وتري. (مساعدة : جد ترتيب حذف مبسطي)‎.
372- أثبت أنه يوجد للبيان G تمثيل بفترات إذا و فقط إذا كان لمصفوفة وقع العصبة و الرؤوس ل G خاصية الواحدات المتتابعة.
373- أثبت أن البيان G بيان فترة إذا و فقط إذا أمكن ترتيب رؤوسه على الشكل vn، ...، v1، حيث إن vi↔vk تعطي vj↔vk عندما i
374- أثبت أن G بيان فترة وحدة (يمكن تمثيله بفترات لها الطول نفسه)‎ إذا و فقط إذا امتلك A(G)‎+1 خاصية الواحدات المتتابعة (Roberts [1968])‎.
375- أثبت أن G يكون بيان فترات فعلي (قابل للتمثيل بفترات بحيث لا توجد أي فترة تحوي فعليا فترة أخرى)‎ إذا و فقط إذا كان لمصفوفة الوقوع للعصب و الرؤوس له خاصية الواحدات المتتابعة لكل من الصفوف و الأعمدة، (Fishburn [1985])‎.
376- أثبت أن كل بيان خال من P4 يكون بيان مينيل.
377- أثبت أن كل وتري يكون تثليثا o-.
378- افترض أن C حلقة في بيان ليس له حلقة فردية مستحدثة. أثبت أن ل V(C)‎ ثلاثة رؤوس متجاورة زوجا زوجا بحيث إن المسارات جميعها التي تربط بين هذه الرؤوس في C لها طول فردي.
379- أثبت أن الشروط الآتية متكافئة : a)‎ يوجد لكل حلقة فردية طولها 5 على الأقل زوج من الأوتار المتفاطعة. b)‎ لكل زوج x, y ϵV(G)‎، تكون المسارات اللاوترية من x إلى y إما زوجية كلها أو فردية كلها. (مساعدة : ل A ←B، خذ في الحسبان زوجا P1 و P2 من المسارات من x إلى y لها نوعيات متضادة، بحيث يكون مجموع أطوالها أصغري)‎، (Burlet-Uhry [1984])‎.
380- أثبت أن كل بيان قابل للترتيب ترتيبا كاملا يكون كاملا بقوة (مساعدة : استخدم التمهيدية 25.1.8)‎ (Chva tal [1984])‎.
381- نعرف التجزئة التخالفية (المتخالفة)‎ للبيان G على أنها تجزئة ل V(G)‎ إلى مجموعتين غير خاليتين X و Y، بحيث إن كلا من G [X]، و [Y] Ġ غير مترابط. لقج خمن كفتال (Chvaʼtal [1985 b)‎ أنه لا توجد تجزئة تخالفية لأي بيان ناقص أصغري. أثبت أن هذا يعطي تمهيدية مجموعة قطع النجمة و أن ال SOGC تعطي هذه المخمنة.
382- نقول : يشكل الرأسان x و y زوجا زوجيا إذا كان لكل مسار لا وتري من x إلى y طول زوجي (بمعنى أن عدد أضلاع هذا المسار زوجي)‎. تعد التوائم (الرؤوس غير المتجاورة التي لها الجوار نفسه)‎ حالة خاصة : a)‎ افترض أن S1 و S2 مجموعتنا متقرتان كبريان في بيان قابل للتجزئة G. أثبت أن البيان الجزئي المولد من الفرق التماثلي ل S1 و S2 يكون مترابطا. (Bland-Huang-Trotter [1979])‎. b)‎ استخدم فرع (a)‎ لتبرهم أنه لا يوجد زوج زوجي لأي بيان حرج من الدرجة p. (تعليق : إذن، لا يوجد توائم لأي حرج من الدرجة p، و هذا يبرهن ثانية أن مضاعفة الرؤوس يحافظ على الكمال)‎، (Meyniel [1987], Bertschi-Reed [1988])‎
383- افترض أن G بيان قابل للتجزئة، و أن S1 و S2 مجموعتان مستقرتان في التلوين الأمثل ل G-x. استخدم فرع (a)‎ من المسألة السابقة لتبرهن أن البيان الجزئي الذي تولده {x} U S1 U S2 يكون ثنائي الترابط (مترابط من الدرجة 2)‎. (Buckingham-Golumbic [1983])‎
384- إن البيان K1,3+e. باستخدام الكمال لبيانات مينيل، أثبت أن البيانات الخالية K1,3+e تحقق ال SPGC .(Meyniel [1976])‎.
385- SPGC لبيان الدائرة. (Buckingham-Golumbic [1983])‎ a)‎ استخدم التمهيدية 28.1.8 لتبرهن أنه إذا كان x رأسا في بيان قابل للتجزئة G، فإن C-N [x] يكون مترابطا N(x)‎ = N[x] U {x} : b)‎ استخدم فرع a لتبرهن أن بيانات الدائرة القابلة للتجزئة تكون خالية من K1,3. c)‎ استنتج من فرع (b)‎ و النتيجة 53.1.8 أن ال SPGC تحقق لبيانات الدائرة.
386- أعط توصيفا مميزا للبيانات التي تشكل مجموعاتها المستقرة عائلة من المجموعات المستقلة لما ترويد على مجموعة الرؤوس.
387- أثبت أن المجموعات المستقرة لبينا لا تكون بالضرورة هي المجموعات المستقلة لماترويد، وذلك من خلال إيجاد بيانات موزونة الرؤوس ؛ حيث إن النسبة بين أكبر وزن لمجموعة مستقرة الوزن الذي تم إيجاده بجشع إلى مجموعة مستقرة تكون كبيرة اختياريا.
388- أثبت أن كل ما ترويد تجزئة يكون ما ترويد مستعرضا.
389- عدل الخوارزمية الجشعة لتحصل (مع إثبات)‎ على خوارزمية لإيجاد مجموعة مستقلة موزونة كبرى في ماترويد له أوزان حقيقية اختيارية (ليست بالضرورة غير سالبة)‎ على العناصر.
390- أعط توصيفا مميزا للبيانات التي تشكل مواءمتها عائلة من المجموعات المستقلة لماترويد على مجموعة الأضلاع.
391- حدد الماترويدات التي تكون متحققة بيانيا. و أعط توصيفا مميزا للبيانات التي ماترويدات حلقاتها ماترويدات تجزئة.
392- باستخدام الاعتماد الخطي فقط، أثبت أن الماترويدات المتجهة تحقق خاصية الحلقات المستحدثة ؛ إن إضافة عنصر واحد إلى مجموعة مستقلة من المتجهات يوجد مجموعة غير مستقلة واحدة على الأكثر
393- صف حلقات الماترويد المستعرض M بدلالة البيان الثنائي الفرع المناظر G، باستخدام خواص البيانات الثنائية الفرع فقط. و برهن أن M تحقق خاصية الحذف الضعيف.
394- أفترض أن M(G)‎ هي ماترويدات الحلقات ل G. و افترض كذلك أن k(X)‎ تساوي عدد مركبات البيان الجزئي المولد Gx الذي مجموعة أضلاعه هي X. و بذلك، فإن r(x)‎=n-k(x)‎. اجعل U و V و V، حيث U↔v عندما تتقاطع المركبات المرتبطة في u و v : a)‎ احسب عدد رؤوس مركبات H بدلالة الأعداد k(X)‎,k(Y)‎ و k(X∩Y)‎. أثبت أن k(XUY)‎ b)‎ استخدم فرع (a)‎ لبرهنة خاصية المقياسية الجزئية ل M(G)‎ دون استخدام أي خواص أخرى للماترويدات. ([1979]Aigner)‎.
395- استخدم نظرية كونج و إيجرفاري (König- Egervʼary)‎ لتبرهن-مباشرة-أن دالة الرتبة للماترويد المستعرض تكون مقياسية جزئية.
396- أفترض أن M نظام وراثي بأوزان غير سالبة على E، أثبت-مباشرة-أنه إذا كان M يحقق خاصية تبديل الأساس (B)‎، فإن الخوارزمية الجشعة تولد دائما أساسا موزونا أعظم.
397- بديهيات ماترويد بديلة. افترض أن M نظام وراثي، أثبت-مباشرة-أنه إذا كان M يحقق خاصية تبديل الأساس (B)‎، فإن الخوارزمية الجشعة تولد دائما أساسا موزونا أعظم.
398- بديهيات ماترويد بديلة. أفترض أن M نظام وراثي، أثبت تضمينات M الآتية مباشرة : a)‎ تتضمن (-)‎ المقياسية الجزئية (R)‎ الامتصاص الضعيف (A)‎. b)‎ يتضمن الامتصاص القوي (ʼA)‎ المقياسية الجزئية (R)‎ (دون استخدام الانتظام (الاتساق)‎)‎. (مساعدة : استخدام الاستقراء على X∆Y)‎. c)‎ يتضمن تبديل الأساس (B)‎ وحدانية الحلقات المستحدثة (J)‎. d)‎ تتضمن (-)‎ وحدانية الحلقات المستحدثة (J)‎ الحذف الضعيف (C)‎. e)‎ تتضمن وحدانية الحلقات المستحدثة (J)‎ التوسيع (J)‎. (مساعدة : استخدم J و الاستقراء على I1-I2 لتحصل على التوسيع)‎
399- لأي نظام وراثي، لأثبت أن خاصية الحذف الضعيف تتضمن خاصية الحذف القوي مستخدما الاستقراء على ǀC1 U C2ǀ، .(Lehman [1964])‎
400- أثبت أنه يوجد على الأقل 2r مجموعة مغلقة للماترويد الذي رتبته r (Lazarson [1957])‎.
401- أثبت أن الماترويد يكون بسيطا إذا و فقط إذا تحقق ما يأتي : 1)‎ لا يوجد أي عنصر يظهر في كل مستوى زائدي. 2)‎ من كل زوج من العناصر المختلفة، يوجد مستوى زائدي يحوي واحدا منها بالضبط. أثبت أن هذين الشرطين يكفيان لأن تكون عائلة من المجموعات جمعا من المستويات الزائدية لماترويد بسيط.
402- في ماترويد ما، أثبت أن مجموعة تكون تحت أساس إذا و فقط إذا كانت مستوى زائديا.
403- استخدم خاصية الحذف الضعيف في إعطاء توصيف مميز عندما تكون عائلة من المجموعات عائلة مستويات زائدة لماترويد ما.
404- أثبت أن المجموعات المغلقة لماترود ما هي المتممات لاتحادات مرافقات الحلقات.
405- افترض أن X مجموعة مغلقة في ماترويد M : a)‎ لتكن Y مجموعة مغلقة محتواة في X، بحيث إن r (Y)‎ = r (X)‎-1. أثبت أنه يوجد ل M مستوى زائدي H بحيث Y=X∩H. (مساعدة : إذا كان معطى لدينا مجموعة جزئية مستقلة كبرى Z من Y، فوسعها بواسطة eϵX، ثم وسعها لأساس B، و اجعل H=ƃ (B-e)‎. b)‎ أثبت أن X هو تقاطع r(M)‎-r(X)‎ من المستويات الزائدية المختلفة.
406- أثبت الخواص الآتية للمجموعات المغلقة لماترويد : a)‎ تقاطع أي مجموعتين مغلقتين يساوي مجموعة مغلقة. b)‎ يساوي مولد أي مجموعة تقاطع المجموعات المغلقة جميعها التي تحوي هذه المجموعة. (تعليق : لذا، فإن Ƃx هي المجموعة الوحيدة المغلقة الصغرى التي تحوي X)‎.
407- أثبت أن M.X لا تحوي عرى إذا و فقط إذا كانت Ẋ مغلقة.
408- الأساسات و مرافقات الحلقات في الماترويدات : a)‎ أثبت أنه عندما ينتمي e إلى أساس B في ماترويد M، لإغنه يوجد بالضبط مرافق حلقة واحدة في M منفصل عن B-e، و يحوي e. b)‎ استخدام فرع (a)‎ لتبرهن أنه إذا كانت C حلقة في ماترويد M، و كان كل من x و y عنصرين مختلفين من عناصر C، فإنه يوجد مرافق حلقة C*ϵC* بحيث إن C*∩C={X, Y}، (Minty [1966])‎. c)‎ فسر لماذا يكون فرع (b بديهيا و تافها لماترويدات الحلقات.
409- أثبت أن ثنوي الماترويد البسيط (لا يحوي عرى و لا عناصر متوازية)‎ يمكن أن يكون غير بسيط. و بين إمكانية أن تكون مجموعة معينة حلقة أو مرافق حلقة في ماترويد ما.
410- استخدم ثنوية الماترويدات لتبرهن صيغة أوبلر لبيانات المستوى المترابطة.
411- إن بيان أساسات الماترويد هو البيان الذي له رأس لكل أساس للماترويد، حيث تكون الأساسات متجاورة إذا كان حجم الغرف التماثلي لهذه الأساسات يساوي 2. أثبت على وجود حلقة مولدة لكل بيان أساسات ماترويد، و وضح النتيجة لكل من الماترويدات البيانية و الموحدة (مساعدة : استخدم التقليص و الحصر استقرائيا لإيجاد حلقة مولدة من خلال أي ضلع)‎، ([ 1986,p72], Kung [1972]Holzmann-Harary)‎
412- استخدم نظرية تقاطع الماترويدات لتبرهن أنه في كل توجيه لا حلقي ل G يمكن تغطية الرؤوس على الأكثر ب a(G)‎ من المسارات المنفصلة زوجا زوجا. (Chappell [1994])‎، (تعليق : هذه حالة خاصة من النظرية 33.4.8. للبيانات الموجهة اللاحلقية)‎.
413- أثبت أن حصر الماترويدات المستعرضة و اتحادها يكون ماترويدات مستعرضة، لكن التقليص، و الماترويدات الثنوية للماترويدات المستعرضة ليست بالضرورة ماترويدات مستعرضة.
414- أفترض أن G بيان موزون على n من الرؤوس، و افتض أيضا أن، E1…En-1، تجزئة ل E(G)‎ ل n-1 مجموعة. هل توجد خوارزمية على صورة كثيرة حدود بالنسبة إلى الزمن، لحساب عدد الأشجار المولدة التي لها وزن أصغر من بين الأشجار المولدة التي لها وزن أصغر من بين الأشجار التي لها ضلع واحد بالضبط في كل مجموعة جزئية Ei ؟
415- استخدم التوصيف المميز للبيانات التي لها k من الأسجار المولدة المنفصلة ضلعيا زوجا زوجا (النتيجة 59.2.8)‎ لتبرهن على وجود k سجرة مولدة منفصلة ضلعيا زوجا زوجا لكل بيان مترابط ضلعيا من الدرجة 2k، و كل k جد بيانا مترابطا ضلعيا من الدرجة 2k بحيث لا يوجد له k+1 من الأشجار المولدة المنفصلة ضلعيا زوجا زوجا. (]Nash-Williams [1961])‎.
416- افترض أن S مجموعة من نسع نقاط في المستوى (لا يوجد منها ثلاث نقاط على استقامة واحدة)‎. أثبت أن S تحوي رؤوس مضلع خماسي محدب. أعط مثالا على ثماني نقاط لا تتحقق فيها هذه النتيجة.
417- 1. افترض أن لديك قرصين متحدين في المركز، و أن لكل منهما 20 قطاعا دائريا من الحجم نفسه. تم طلاء عشرة قطاعات و لكل قرص بالون الأحمر، و عشرة قطاعات أخرى باللون الأزرق ضمن ترتيب معين. أثبت أنه يمكن محاذاة القرصين أو صفهما بطريقة معينة بحيث إن لعشرة من قطاعات القرص الداخلي على الأقل اللون نفسه لقطاعات القرص الخارجي المرتبطة بها.
418- لكل n ϵ N، اجعل S هي المجموعة المؤلفة من n+1 عنصرا في {1,…,2n}. أثبت أنه يوجد في S عنصران بحيث يقسم أحدهما الآخر، و يوجد كذلك عنصران آخران، القاسم المشترك الأعظم لهما يساوي 1. أثبت أن هاتين النتيجتين هما أفضل ما يكمن من خلال إيجاد مجموعة جزئية حجمها n لا تتحقق عليها هذه النتائج.
419- استخدم مبدا طواقي الحمام و المجاميع الجزئية لتبرهن كلا من العبارتين الآتيتين : a)‎ تحوي كل مجموعة مؤلفة من n من الأعداد الصحيحة مجموعة جزئية غير خالية مجموعها يقبل القسمة على n( أعط مثالا على مجموعة مؤلفة من n-1 من الأعداد الصحيحة لا تحقق فيها هذه الخاصية)‎. b)‎ لتكن x ϵ R، أثبت أن عنصرا واحدا على الأقل من المجموعة {x, 2x, …,(n-1)‎x} يختلف عن عدد صحيح بمقدار 1/n على الأكثر.
420- يوجد في ناد خاص 90 غرفة و 10 عضو. زود الأعضاء بمفاتيح لهذه الغرف بحيث يكون ل 90 منهم مقدرة لدخول الغرف، بمعنى أنه تم تزويد كل شخص من هؤلاء ال 90 بمفتاح لغرفة مختلفة. (أفترض عدم اشتراكهم بالمفاتيح)‎. أثبت أنه يلزمنا 990 مفتاحا، و أن العدد 990 كاف.
421- أفترض أن T شجرة. استخدم التقنية الموجودة في النظرية 2.3.8 لترهن أن مركز t يتألف من رأس واحد، أو من رأسين متجاورين (هذا يبرهن النظرية 13.1.2 مرة أخرى)‎، (Jordan [1869], Graham-Entringer- Szeʼkey [1994])‎.
422- أثبت أن كل مجموعة مؤلفة من 2m+1 من نقاط شبكية صحيحة (شبكية أعداد صحيحة)‎ في Rm تحوي زوجا من النقاط بحيث يكون مركزه المتوسط (متجه الوسط)‎ أيضا نقطة شبكية صحيحة.
423- أثبت أنه يوجد لكل تلوين ثنائي لنقاط شبكية صحيحة في Rm جمع فيه n من النقاط التي لها اللون نفسه بحيث يكون مركزها المتوسط (متجه الوسط)‎ نقطة صحيحة لها أيضا اللون نفسه (مساعدة : لا حاجة إلى نظرية رامزي بسبب وجود إثبات قصير باستخدام مبدأ طواقي الحمام فقط)‎، (Boʼna [1990])‎.
424- أفترض أن S جمع مؤلف من n+1 عدد صحيحا مجموعه يساوي .k ل K≤2n+1، أثبت أنه يوجد ل S مجموعة جزئية، حاصل جمع عناصرها يساوي i لكل i ϵ [K]. لكل n، أعط مثالا لجمع بحيث تفشل هذه النتيجة عندما k=2n+2.
425- لكل عدد زوجي n، جد ترتيبا ل E(Kn)‎، بحيث يساوي أكبر طول لمسرب متزايد n-1. (تعليق : هذا يبرهن أن النظرية 4.3.8 هي أفضل ما يمكن عندما يكون n عدد زوجيا، إضافة ما يمكن عندما يكون n عدد فرديا يساوي 9 على الأقل. إلا أن البناء يكون أصعب كثيرا)‎، (Graham- Kleitman [1973])‎.
426- أفترض أن S مجموعة مؤلفة من R(m,m ; 3)‎ من نقاط المستوى بحيث لا يوجد منها ثلاث نقاط على استقامة واحدة، أثبت أن S تحوي m نقطة بحيث تشكل هذه النقاط مضلعا (Tarsi)‎ عدد أضلاعه m.
427- تذكر ان البينا الموجه يكون بسيططا إذا لم يشترك أي ضلعين من أضلاعه بالزوج المرتب نفسه من النقاط الطرفية. يعرف الدوري الرتيب على أنه دوري يكون فيه توجيه الأضلاع متوافقا دائما مع رتبة الدلائل على الرؤوس، أو أنه بكون غير متوافق دائما مع هذه الرتبة. و يكون للبيان الموجه خالي العرى التام نسخة واحدة من كل زوج مرتب من الرؤوس المختلفة بوصفها ضلعا. إذا أعطيت m، فبرهن أنه إذا كانت N كبيرة جدا، فإن لكل بيان موجه بسيط خالي العرى رؤوسه [N] مجموعة مستقلة من الرتبة m، أو له دوري رتيب رتبته m، أو له بيان موجه خالي العرى تام رتبته m
428- جد قيمة عدد رامزي R(K1,m,K1,m)‎. (مساعدة : يعتمد الجواب على ما إذا كانت m و n زوجية أو فردية)‎.
429- أفترض أن T شجرة على m من الرؤوس، إذا علمت أن m-1 يقسم n-، فجد عدد رامزي R(t, k1,n)‎. (Burr [1974])‎.
430- أثبت أن R(c4,c4)‎ = 6. (تعليق : يوجد العديد من البراهين)‎.
431- أثبت أن R(2K3, 2K3)‎. (مساعدة : اختزال المسألة لحالة الشكل الفراشي الذي فيه مثلثات من اللونين بالإضافة إلى حلقة خماسية أحادية اللون، ثم استخدم التماثل)‎.
432- أثبت أن R(mK2, mK2)‎=3m-1.
433- يعرف تضاعف رامزي للبيان G على أنه أصغر عدد من النسخ أحادية اللون من G في تليون ثنائي لأضلاع عصبة على R(G,G)‎ من الرؤوس. أثبت أن تضاعف رامزي ل K3 يساوي 2.
434- أثبت أنه يوجد لكل نقطة في منطقة مثلثية تعبير وحيد بوصفه تركيبا محدبا لرؤوس المثلث (نقصد بالتركيب المحدب التركيب الخطي الذي تكون فيها المعاملات غير سالبة و مجموعها يساوي 1)‎.
435- تمهيدية سبيرنر في الأبعاد زائدي. إن التقسيم المبسطي يعبر عن المبسط ذي البعد k بصفته اتحاد لمبسطيات (خلايا)‎ من البعد k بحيث تتقاطع أي خليتين في المبسط الذي تحدده زواياها المشتركة. و أن الخلية تامة الوسم هي الخلية التي زواياها {0,…,k}. أعط تعريفا للتعليم (وضع علامات دالة أو وسم)‎ الفعلي، بحيث يحوي كل وسم فعلي لتقسيم مبسطي لمبسط من الدرجة k خلية تامة الوسم. أثبت هذه النظرية. (مساعدة : تعد تمهيدية سبيرنر في البعد 2 (نظرية 17.3.8)‎ شاهدا حيا على خطوة الاستقراء لإثبات بالاستقراء على k)‎.
436- احسب عرض نطاق كل من : Pn, Kn, Cn.
437- احسب عرض نطاق (Eitner [1979]. Kn1,…,nk.
438- احصل على حدود عليا و أخرى و سفلى تختلف ب 1 للبعد الجدائي لبيان بيترسون (الحد العلوي سوف يكون على الأرجح القيمة الصحيحة، و لكن برهنة أنه لا يمكن تحسينه يكون صعبا و مملا)‎.
439- حدد البيانات على n من الرؤوس جميعها التي يساوي بعدها الجدائي n-1. (Lovẚsz-Ne→et řil Pultr[1980])‎.
440- إذا كانت r معطاة، فاحسب pdim (Kr+mK1)‎ لكل m≥1. (Lovẚsz-Ne→et řil Pultr[1980])‎.
441- احسب البعد الجذائي لكعب ثلاثي الأبعاد.
442- أثبت أن C2k+1 غير قابل لغمس يحافظ على المسافات في أي جداء كارتيزي لعصب إذا كان K>1.
443- حدد بعد المكعب المسحوق ل C5.
444- حدد بعد المكعب المسحوق ل K3,3. (مساعدة : استخدم التماثل لاختزال تحليل الحالة)‎.
445- تدعى مسألة انتشار الإشاعة "مسألة الهاتف" أيضا، أما المسألة المقابلة للبيانات الموجهة فتدعى "مسألة التلغراف". بوصفها دالة في n، حدد العدد الأصغر للتناقلات في اتجاه واحد بين n من الأشخاص بحيث يملك كل شخص مسارا ناقلا للأشخاص الآخرين جميعهم. (Harary-Schwenk [1974])‎.
446- ليكن D بيانا موجها يحل مسألة التلغراف بحيث يصل كل رأس معلومات من الرؤوس الأخرى مرة واحدة بالضبط. أثبت أنه يوجد n-1 رأسا في D على الأقل يسمعون معلوماتهم الخاصة. و لكل n، أنئ مثل D بحيث يكون n-1 رأسا فقط يسمعون معلوماتهم الخاصة، في حين يوجد مسار واحد متزايد تماما لكل x≠y من x إلى y(Seress [1987])‎.
447- الخاصية NOHO : a)‎ ليكن G بيانا مترابطا له 2n-4 ضلعا، و يملك ترتيبا خطيا يحل مسألة انتشار الإشاعة و يحقق NOHO (لا توجد حلقة متزايدة)‎. افترض أيضا أن n(G)‎ > 8. و أنه يوجد على الأكثر رأسان درجتهما 2. أثبت أن البيان الذي تم الحصول عليه بحذف المكالمات الأولى و الأخيرة للرؤوس في G يملك 4 مركبات ؛ اثنتين منهما رؤوس معزولة و الائنتين الأخريين جرارين يملكان الحجم نفسه. (West [1982a])‎. b)‎ لكل عدد زوجي n ≥ 4، أنشئ بيانا مرتبا مترابطا له 2n-4 ضلعا يحقق خاصية NOHO. (مساعدة : استخدم الخواص البنائية التي برهنت في فرع (a)‎ لترشدك في البحث)‎.
448- نهج (أسلوب NODUP (NODUP scheme)‎ (لا يوجد ناقلان متطابقان)‎ هو بيان مرتب مترابط بملك مسارا واحدا متزايدا بالضبط من كل رأس إلى أي رأس آخر : a)‎ (-)‎ أثبت أن كل نهج NOHOP يملك خاصية NOHO. b)‎ أثبت أن كل نهج NOHOP عندما تكون n ϵ {6, 10 14, 18}. (تعليق : أثبت سيرس [Seress, [1986]] أن هذه هي فقط القيم الزوجية ل n بحيث يكون نهج NOHOP غير موجود، و بنى نهجا NOHOP للقيم الأخرى جميعها. ل n=4k، بنى ويست [1982b] نهجا NOHOP يحتوي على (9n/4)‎-6 مكالمة، و برهن سيرس [1986] أن هذا هو الأمثل)‎.
449- أفترض أن رأسا في بيان بسيط G يرغب في نشر معلومات للرؤوس الأخرى جميعها. و أنه في كل وحدة زمنية، فإن كل {اس يعرف المعلومة يستطيع إجراء مكالمة مع جار لا يعرف هذه المعلومة. إن الزمن المطلوب لنشر المعلومة من v هو العدد الأصغر من الوحدات الزمنية، بحيث تستطيع الرؤوس جميعها معرفة المعلومة. ابن بيانا G على n من الرؤوس له أقل من 2n ضلعا بحيث يستطيع كل رأس في G نشر المعلومة على الأكثر في زمن يساوي (1+1gn)‎. . (Grigni-Peleg[1991])‎
450- أثبت أن Kk,m يكون قابلا للاختيار من الدرجة k إذا و فقط إذا كان m
451- أثبت أن كل بيان وتري G يكون قابلا للاختيار من الدرجة X(G)‎.
452- أثبت أن كل بيان مترابط G يملك تلوينا قائميا فعليا من قوائم، بحيث يكون ǀL(v)‎ǀ ≥ d(v)‎ لكل v إذا وجدت متباينة صارمة لرأس واحد على الأقل.
453- تكافؤ انظرية ديلورث و نظرية كونج و إيجرفاري : a)‎ إذا أعطيت بيانا ثنائي الفرع G، فطبق نظرية ديلورث على توجيه متعد له لتحصل على نظرية كونج و إيجرفاري. b)‎ إذا أعطيت بيانا موجها متعد D، و ليكن G هو الشطر ل D كما عرف في التعريف 20.4.1. فطبق نظرية كونج و إيجرفاري على g لتحصل على نظرية ديلورث ل D.
454- أثبت أن كل بيان سوي بسيط منتظم من الدرجة 3 مترابط ضلعيا من الدرجة 2 يتفكك إلى مسارات طولها 3. و برهن العبارة نفسها للتثليثات السوية. ( Jü nger -Reinelt-Pulleyblank [1985])‎.
455- أثبت أن النظرية 35.4.8 أفضل ما يمكن عنمدما تكون m-1 تقسم n-1.
456- ليكن G بيانا بحيث تكون Ġ يخلو من المثلثات، و ليس غاية. أثبت أن G يملك حلقة طولها n(G)‎/2 على الأقل. (مساعدة : استخدم النظرية 37.4.8)‎ (N. Graham)‎
457- استخدم نظرية و ودال لتثبيت نظرية أور، و استخدم نظرية مينيل نظرية و ودال.
458- استخدم نظرية مينيل لتبرهن أن بيانا موجها صارما على n من الرؤوس مسارا مولدا إذا تحقق أن : d(u)‎+d(v)‎≥2n-3 لكل زوج u,v من الرؤوس المختلفة غير المتجاورة.
459- حدد أصغر بيان بسيط مترابط بحيث لا يكون متوازنا. a)‎ تفسير الفضاء الحلقي و فضاء الروابط. معطى بيان G، أثبت أن : b)‎ الفرق التماثلي لبيانين جزئيين زوجيين زوجيين هو بيان جزئي زوجي. c)‎ الفرق التماثلي لقطعين ضلعيين هو قطع ضلعي. كل قطع ضلعي يشترك مع كل بيان جزئي زوجي بعدد زوجي من الأضلاع.
460- حدد العدد المتوقع للمثلثات الأحادية اللون في تلوين عشوائي من الدرجة 2 ل E(K6)‎.
461- جيش من الحواسيب مرتب على هيئة شجرة تامة ذات متعدد (k-ary tree)‎ k مع أوراق على بعد 2 من الجذر. عند زمن مثبت، بعمل كل رأس باحتمال p بصورة مستقلة عن الرؤوس الأخرى. و عندما لا يعمل رأس ما، فإنه لا يمكن الوصول إلى أي جزؤ من السجرة الجزئية التي تقع تحت هذا الرأس. ما العدد المتوقع للرؤوس التي يمكن الولوج إليها من الجذر.
462- لتكن G مواءمة حجمها n. اختنر مجموعة مونة من k من الرؤوس بصورة عشوائية. احسب العدد المتوقع للأضلاع المحدثة من خلال الرؤوس المختارة.
463- يتكون البيان الزائد (hypergraph)‎ من حشد رؤوس و حشد آخر من الأضلاع ؛ فإذا كانت مجموعة الرؤوس هي V، فإن الأضلاع هي مجموعات جزئية منV. و العدد اللوني c(H)‎ لبيان زائد H هو العدد الأصغر من الألوان الذي يحتاج إليه لوسم الرؤوس بحيث لا يوجد ضلع يكون أحادي اللون. و يكون البيان الزائد موحدا من الدرجة k (k-uniform)‎ إذا كانت أضلاعه جميعها حجمها k : a)‎ أثبت أن كل بيان زائد موحد من الدرجة k عدد أضلاعه أقل من 2K-1 يكون قابلا للتلوين من الدرجة 2. (Erdös [1963])‎. b)‎ استخدم فرع (a)‎ لتبرهن أنه إذا امتلك كل رأس في بيان ثنائي الفرع على n من الرؤوس قائمة فيها أكثر من 1+1gn من الأولان القابلة للاستخدام، فإن تلوينا فعليا يمكن اختياره من هذه القوائم.
464- استخدم طريقة الحذف لتبرهن أن البيان الذي n من الرؤوس، و معدل درجة رؤوسه d≥1 يملك مجموعة مستقلة لها n/(2d)‎ رأسا على الأقل. ( مساعدة : اختر مجموعة جزئية عشوائية تشمل كل رأس احتماله p بصورة مستقلة لتختار فيما بعد. و احسب العدد المتوقع للأضلاع المحدثة)‎.
465- ليكن H بيانا. للثابت p، أثبت أن Gp كله تقريبا يحوي H بوصفه بيانا جزئيا محدثا.
466- a)‎ ثبت p, t, s, k. أثبت أن Gp كله تقريبا يملك الخاصية التالية : لكل اختيار لمجموعات رؤوس منفصلة T, S حجمها t, s يوجد k على الأقل ممن الرؤوس تكون مجاورة لكل رأس في S و لكنها غير مجاورة لأي رأس في T. (Blass-Harary [1979])‎. استنتج أن Gp كله تقريبا بكون مترابطا من الدرجة k. d)‎ طبق التعليل نفسه للدوريات العشوائية : كل دوري تقريبا يملك الخاصية الآتية : لكل اختيار لمجموعات رؤوس منفصلة S,T حجمها t, s يوجد k على الأقل من الرؤوس تكون مجاورة لكل رأس في S ومن كل رأس في T.
467- يمكن توليد دوري عشوائي موسوم بتوجيه كل ضلع vi vj من vi→vj أو من vi→vj بصورة مستقلة مع احتمال 2/1 : a)‎ أثبت أن كل دوري تقريبا يكون مترابطا بصورة قوية. b)‎ في دوري ما، "الملك" هو رأس يمكنه الوصول إلى أي رأس آخر بسمار طوله 2 على الأكثر. و من المعلوم أن كل دوري يحوي ملكا. هل صحيح أنه في كل دوري تقريبا يكون كل رأس ملكا ؟ (Palmer [1985])‎.
468- جد دالة احتمال العتبة للخاصية الآتية : نصف الأضلاع المحتملة على الٌل لبيان ما تكون موجودة. ما مقدار دقة العتبة ؟
469- ل p=1/n و ل ϵ>0 مثبتة، بين أن Gp كله تقريبا لا يملك فيها أكثر من (1+ϵ)‎n/2 رأسا. (مساعدة : بدلا من محاولة وضع حد للاحتمال مباشرة، بين أنه محدود لاحتمال لحادث آخر، و يؤول إلى 0)‎.
470- حدد أصغر بيان بسيط مترابط بحيث لا يكون متوازرنا.
471- لتكن Q خاصية البيان الآتية : لكل اختيار لمجموعات رأسية منفصلة T,S حجمها c 1g n، يوجد ضلع نقاطه الطرفية في S و T. أثبت أنه إذا كان 2
472- أثبت أنه إذا كان k = l gn-(2+ϵ)‎ lg lg n، فإن كل دوري ألعاب على n من الرؤوس تقريبا يملك الخاصية الآتية : كل مجموعة فيها k من الرؤوس تملك تابعا مشتركا.
473- يكون دوري الألعاب متعديا إذا امتلك ترتيبا رأسيا un، ... ، u1 بحيث ui→uj إذا و فقط إذا كان j>i. أثبت أن كل دوري ألعاب يملك دوري ألعاب جزئيا متعديا في 1 gn من الرؤوس. و أنه إذا كان c عددا ثابتا أكبر من 1، فإن كل دوري ألعاب تقريبا لا يملك دوري ألعاب جزئيا متعديا فيه أكثر من 21 gn+c رأسا.
474- أثبت أن الطول لأطول مسافة مجتازة في قائمة مكونة من n من الرؤوس و الذيول العشوائية هو (o(1)‎+1)‎ Ign. بكلمات أخرى، ϵ<0، لا توجد قائمة تقريبا تملك على الأقل Ign (ϵ+1)‎ شقلبات متطابقة متتالية، و كل قائمة تقريبا تملك على الأقل -1)‎ϵ1gn ( شقلبات متطابقة متتالية.
475- مع p=(1-ϵ)‎ logn /n ، جد m كبيرة بحيث يكون كل بيان تقريبا يملك على الأقل m من الرؤوس المعزولة. ما (n)‎m التي تنتج من متباينة تشيبيجيف (Chebyshey'sInequality)‎ ؟
476- بفحص جيران مشتركين ؛ أثبت أنه إذا كانت P مثبتة، و k=o(n/logn)‎، فإن Gp كله تقريبا يكون مترابطا من الدرجة k.
477- مع p=(1-ϵ)‎ logn /n، كم يمكن أن تكون m كبيرة بحيث يملك كل بيان تقريبا على الأقل m من الرؤوس المعزولة ؟ (مساعدة : استخدم متبانية تشيبيجيف)‎.
478- فترة-t(t-interval)‎ هي مجموعة جزئية من R و التي تكون الاتحاد ل t من الفترات على الأكثر. أما عدد الفترات (Interval number)‎ لبيان G فهو t الصغرى بحيث يكون G بيانا مكونا من تقاطعات فترات من الدرجة t (كل رأس معين بمجموعة تكون الاتحاد ل t من الفترات على الأكثر)‎. أثبت أن البيانات جميعها تقريبا (احتمال ضلعي 2/1)‎ تملك عدد فترات يساوي (o(1)‎-1)‎n /(4 1gn)‎ على الأقل. (مساعدة : قارن عدد التمثيلات بعدد البيانات البسيطة. تعليق : بين شنيرمان [1990] أن البيناتا حميعها تقريبا تملك عدد فترات يساوي (1+o(1)‎)‎n/(2 1gn)‎ (Erdö-West [1985])‎.
479- تفسير الفضاء الحلقي و فضاء الروابط. معطى بيان G، أثبت أن : a)‎ الفرق التماثلي لبيانين جزئيين هو بيان جزئي زوجي. b)‎ الفرق التماثلي لقطعين ضلعيين هو قطع ضلعي. c)‎ كل قطع ضلعي يشترك مع كل بيان جزئي زوجي بعدد زوجي من الأضلاع.
480- تذكر أن الجوار المغلق لرأس v هو N(v)‎ U {v} : a)‎ لتكن S مجموعة رؤوس في بيان بسيط G بحيث إن جواراتها متطابقة أثبت أن إحدى القيم الذاتية ل G تكون مكرره على الأقل ǀSǀ-1 مرة. ما هي ؟ b)‎ لتكن S مجموعة رؤوس في بيان بسيط G بحيث إن جواراتها المغلقة أثبت أن إحدى القيم الذاتية ل G تكون مكرره على الأقل ǀSǀ-1 مرة. ما هي ؟
481- معطى بيان G، و لتكن R(G)‎ هي المصفوفة التي تكون مدخلتها i,j هي dg(vi,vj)‎. أثبت أن بعد المكعب المسحوق لبيان ما (التعريف 12.4.8)‎ يكون على الأقل العدد الأكبر لعدد القيم الذاتية الموجبة و عدد القيم الذاتية السالبة للمصفوفة R(G)‎. استنتج أن بعد المكعب المسحوق للبيان Kn هو n-1. (مساعدة : أعد كتابة الشكل التربيعي xTRx بوصفه مجموعا لمربعات دوال خطية، و طبق قانون سلفستر للقصور الذاتي)‎.
482- تكون المصفوفة محيدة كليا (totally unimodular)‎ إذا كانت محددة كل مصفوفة جزئية مربعة موجودة في {0, 1,-1}. أثبت أن مصفوفة الوقوع لبيان بسيط تكون محيدة كليا إذا و فقط إذا كان البيان ثنائي الفرع. (تذكيز : مصفوف الوقوع لبيان بسيط تملك +1 مرتين في كل عمود)‎.
483- ليكن G بيانا خاليا من المثلثات على n من الرؤوس، بحيث يكون لكل زوج من الرؤوس غير المتجاورة بالضبط جاران مشتركان. أثبت أن G منتظم، و أن n=1+1(2K+1)‎، حيث k هي درجة الرؤوس في G. أثبت أن G منتظم بقوة. ما القيود على k المتضمنة باستخدام شروط التكامل ؟ أنشئ أمثلة kϵ {1, 2, 5}. و هنالك تحقيق ل k=10 معروف باستخدام التصاميم التركيبية التوافقية)‎.
484- أثبت أن بيان بيترسون منتظم بقوة، و حدد طيفه (يكون الطيف سهلا بوجود خصائص البيانات المنتظمة بقوة و ليس صعبا من غيرها)‎. طبق الطيف لتبين أن أضلاع البيان K10 لا يمكن أت تجزأ إلى ثلاث نسخ منفصلة من بيان بيترسون. (مساعدة : استخدام الطيف لتبرهن أن نسختين من مصفوفة بيترسون تملكان متجها ذايتا مشتركا غير المتجه الثابت)‎ (Schwenk [1983])‎.
485- ليكن F=G□H، حيث G و H بيانان بسيطان. أثبت أنه إذا كان كل رأسين غير متجاورين في F يملكان جارين مشتركين بالضبط، فإن G و H يكونان بيانين تامين.
486- التشاكلات الذاتية و القيم الذاتية : a)‎ أثبت أن ƃ يكون تشاكلا ذاتيا ل G إذا و فقط إذا كانت مصفوفة التباديل المقابلة ل s إبدالية مع مصفوفة التجاور ل G ؛ بمعنى أن PA=AP. b)‎ ليكن x متجها ذاتيا ل G للقيمة الذاتية التي عدد مرات تكرارها 1، و لتكن P مصفوفة التباديل للتشاكل الذاتي ل G. أثبت أن Px=±x. c)‎ استنتج أنه عندما تكون كل قيمة ذاتية ل G مكررة مرة واحدة فقط، فإن كل تشاكل ذاتي ل G هو تبديلة عودة إلى الأصل (involution)‎، بمعنى أن مربع هذه التبديلة يعطي العنصر المحايد. (Mowshowitz.[1969], Petersdorf- Sachs [1969])‎
487- لتكن In، ...، I1 مصابيح ضوئية متحكما فيها من خلال المفاتيح sn، ....، s1. المفتاح i يغير حالة المصباح i إلى تشغيل / إغلاق و ربما مصابيح أخرى، و لن si يغير حالة Ij إذا و فقط إذا كان sj يغير حالة Ii، مبدئيا، أفترض أن المصابيح جميعها مغلقة. أثبت أنه يمكن تشغيل المصابيح جميعها. (Peled [1992])‎ (مساعدة : يستخدم هنا الفضاءات المتجهة، و ليس القيم الذاتية)‎.
Table of Contents