1- أثبت العبارة الآتية أو انقضها : مل شجرة لها مواءمة مكتملة واحدة على الأكثر.
2- حدد الحجم الأصغر لمواءمة أعظمية في الحلقة Cn.
3- لتكن S مجموعة الرؤوس المشبعة بالمواءمة M في البيان G. أثبت أن بعض المواءمات العظمى أيضا تشبع S. و هل هذه العبارة يجب أن تكون صحيحة لكل مواءمة كبرى ؟
4- لتكن Tشجرة على n من الرؤوس، و ليكن k الحج الأكبر لمجموعة مستقلة في T. حدد (T)’a بدلالة n و k.
5- يخطط أعضاء ناد لقضاء عطلتهم الصيفية، حيث يتوافر لديهم الرحلات tn،....،t1، ولكن سعة الرحلة ti هي ni. و كل شخص يرغب في بعض هذه الرحلات سيسافر على الأكثر في واحدة منها. بدلالة أي الأشخاص يرغب بأي الرحلات، اشتق الشرط الضروري و الكافي لملء الرحلات جميعها (بسعتها) من الأشخاص الذين يرغبون فيها.
6- مصفوفة التباديل (permutation matrix) P : هي مصفوفة، مدخلاتها 1.0 فقط و تحوي في كل صف و عمود العدد 1 بالضبط مرة واحدة. أثبت أن أي مصفوفة مربعة مدخلاتها أعداد صحيحة غير سالبة يمكن كتابتها في صورة حاصل جمع k من مصفوفات التباديل، إذا كانت مجاميع الفوف جميعها و مجاميع الأعمدة جميعها كذلك تساوي k.
7- تتكون مجموعة من أوراق اللعب من mn بطاقة مع m و n نقشا عليها، بحيث يكون هنالك بطاقة واحدة لكل قيمة في كل تفش. وزعت البطاقات إلى صفيف n في m : a) أثبت أن هنالك مجموعة تتكون من m بطاقة، بواقع بطاقة واحدة في كل عمود، ذات قيم مختلفة. b) استخدم فرع (a) لبرهنة أنه بمتتالية من تبديلات البطاقات التي لها القيمة نفسها، يمكن إعادة ترتيب البطاقات بحيث يتكون كل عمود من n بطاقة من النقوش المختلفة. (Enchev [1997]).
8- استخدم نظرية كونج و إيجرفاري لإثبات أن كل بيان ثنائي الفرع G له مواءمة حجمه e(G)/∆(G) على الأقل. استخدم هذا لتستنتج أنه توجد لكل بيان جزئي منKn,n عدد أضلاعه أكثر من n(1-k)مواءمة حجمها k على الأقل.
9- حدد اكبر عدد من الأضلاع في البيان الثنائي الفرع البسيط الذي لا يحوي مواءمة عدد أضلاعها k و لا يحوي نجما عدد أضلاعه I (Isaak).
10- استخدم نظرية كونج و إيجرفاري لإثبات نظرية هال.
11- ليكن G بينانا ثنائي الفرع. أثبت أن a (G) = n(G)/2 إذا و فقط إذا وجدت ل G مواءمة مكتملة .
12- أعط توصيفا مميزا للبيانات التي عدد سيطرتها 1.
13- أوجد أصغر شجرة لا يتساوي فيها عدد كل من السيطرة و الغطاء الرأسي.
14- حدد عدد السيطرة لبيان بيترسون، و حدد الحجم الأصغر لمجموعة مسيطرة كلية في بيان بيترسون كذلك.
15- في المكعب الزائد Q4، حدد الأحجام الصغرى لكل من : مجموعة مسيطرة، و مجموعة كسيطرة مستقلة، و مجموعة مسيطرة مترابطة، و مجموعة مسيطرة كلية.
16- أوجد طريقة لوضع خمسة أزواج من الملكات غير المهاجمة زوجا زوجا على لوح شطرنج 8 في 8 بحيث تهاجم هذه الملكات المربعات الأخرى جميعها.
17- في البيان المترابط G الذي درجته n، أثبت أن الحجم الأصغر لمجموعة مسيطرة مترابطة هو n ناقص أكبر عدد للأوراق في سجرة مولدة
18- باستعمال أوزان غير سالبة للأضلاع، أنشئ بيانا موزونا على أربعة رؤوس بحيث لا تكون المواءمة ذات الوزن الأكبر مواءمة ذات حجم أكبر.
19- بين كيفية استعمال الخوارزمية النهجارية لفحص إمكانية وجود مواءمة كاملة في البيان الثنائي
20- أعط مثالا على مسألة المواءمة المستقرة يتكون من رجلين و امرأتين، بحيث يكون هناك أكثر من مواءمة مستقرة.
21- مسألة سائق الحافلة. افترض أن هناك n سائقا و n مسلكا صباحيا يقضي فيها السائق أوقاتا Xn،....X1، و n مسلكا مسائيا يقضي فيها أوقاتا yn،....y1. و يدفع للسائق أجر إضافي عندما يتجاوز المسلكين الصباحي و المسائي زمنا كليا t. و الهدف هو تعيين شوطين ؛ صباحي و مسائي لكل سائق من أجل تخفيض قيمة الأجور الإضافية الكلية إلى الحد الأدنى. عبر عن هذه بوصفها مسألة مواءمة موزونة، و برهن أن إعطاء أطول مسلك صباحي رقمه i و أقصر مسلك مسائي رقمه i للسائق نفسه لكل i يعطي حلا مثاليا. (مساعدة : لا تستخدم الخوارزمية الهنجارية ؛ خذ التركيب الخاص للمصفوفة). (R.B. Potts)
22- افترض أن لديك n رجلا و n امرأة. و قد خصص كل منهم n –i نقطة إلى الشخص i في قائمة أولوياته، و ليكن الوزن لزوج من الأشخاص هو مجموع النقاط المخصصة من ذلك الزوج من الأشخاص أنشئ مثالا لا تكون فيه أي مواءمة وزن كبرى مواءمة مستقرة.
23- أثبت أنه إذا وضع رجل x في زوج مع امرأة a في مواءمة مستقرة، فإن a لم ترفض x في خوارزمية مقترحات جيل و شابلي. استنتج أنه من بين المواءمات المستقرة جميعها، فإن كل رجل يكون أكثر سعادة في المواءمة الناتجة عن هذه الخوارزمية. (مساعدة : خذ في الحسبان الحدوث الأول لمثل هذا الرفض).
24- في مسألة رفقاء الغرف المستقرة، كل شخص من 2n شخصا له ترتيب أولويات على ال (2n-1) شخصا الآخرين. و المواءمة المستقرة هي مواءمة كاملة لا يوجد فيها زوج غير متوائم يفضل فيه كل منهما شخصا آخر على رفقاء غرفهم الحاليين. أثبت أنه لا توجد مواءمة مستقرة عندما تكون الأولويات على النحو الآتي أدناه. (Gale-Shapley [1962]) a : b˃ c˃ d b : c˃ a ˃ d c : a ˃ b ˃ d d : a ˃ b ˃ c
25- في مسألة رفقاء الغرف المستقرة، افترض أن كل شخص يصرح بالقسم العلوي من قائمة الأولويات بوصفه جزءا "مقبول". عرف بيان المقبولية على أنه البيان الذي تكون رؤوسه الناس و أضلاعه هي الأزواج من الناس الذين افترضوا أن كلا منهما مقبول للآخر. أثبت أن المجموعات العالية المنزلة في المقبولية G كلها تؤدي إلى مواءمة مستقرة إذا و فقط إذا كان G ثنائي الفرع.
26- في خوارزمية المقترحات حيث يقترح الرجل، أثبت أنه لا يوجد رجل مرفوض دائما من النساء جميعهن. (مساعدة : ماذا يحدث بعد أن يرفض X من النساء جميعهن ما عدا امرأة واحدة).
27- ليكن G بيانا منتظما من الدرجة 3 و له صلعا قطع على الأكثر. أثبت أن G يملك معاملا من الدرجة 1. ([1891] Petersen)
28- ليكن G بيانا ثنائي الفرع منتظما نت الدرجة k. أثبت أنه يمكن تفكيكه إلى معاملات من الدرجة r و فقط إذا كانت r تقسم k.
29- ليكن G و H بيانين. حدد عدد المركبات و الدرجة العظمى لH G ˅ بدلالة متغيرات G و H.
30- أثبت أن الشجرة T تملك مواءمة كاملة إذا و فقط إذا كان o(T-v) = 1 لكل (Chungphaisan) vϵV(T) .
31- ليكن G بيانا زوجيا منتظما من الدرجة k (درجته زوجية) بحيث يبقى مترابطا بعد حذف أي (K-2 ضلعا. أثبت أن G يملك معاملا من الدرجة 1.
32- أثبت أن البيان البسيط المنتظم من الدرجة 3 يملك معاملا من الدرجة 1 إذا و فقط إذا كان يتفكك إلى نسخ من P4.
33- 6. ليكن G بيانا مترابطا خاليا من المخالب ذا درجة زوجية : a) لتكن T شجرة مولدة للبيان G بالبحث الأفقي أولا (الخوارزمية 8.3.2). و ليكن x و y رأسين لهما والد مشترك في T غير الجذر. أثبت أن x و y يجب أن يكونا متجاورين. b) استخدم فرع (a) لتثبت أن G يملك معاملا من الدرجة 1. ( تعليق : دون الاستعانة بفرع (a) يمكن إثبات النتيجة الأقوى، و هي أن الضلع الأخير في المسار الأطول ينتمي إلى معامل من الدرجة 1 .(Las Vergnas [1975], Sumner [1974a])
34- لتكن M مواءمة في البيان g، و ليكن U رأسا غير مشبع للمواءمة M. أثبت أنه إذا كان G لا يملك مسارا موسعا للمواءمة M يبدأ عند u، فإن u غير مشبع في مواءمة كبرى ما في G.
