1- أعط مثالا ناقضا للعبارة الآتية، و أضف فرضيات لتصحيحها، ثم أثبت صحة العبارة المصححة : إذا كان e ضلعا فاصلا (cut-edge) ل G، فإن أحد طرفيه على الأقب يكون رأسا فاصلا ل G.
2- أثبت أو انقض كلا من العبارة الآتية : إذا كان مقياس ترابط بيان معين يساوي 4، فإن هذا البيان يكون مترابطا من الدرجة 2.
3- أثبت أو انقض كلا من العبارة الآتية : إذا كان البيان مترابطا من الدرجة 3، فإن مقياس ترابطه يساوي 3.
4- أثبت أو انقض كلا من العبارة الآتية : إذا كانت درجة ترابط بيان تساوي k، فإن درجة ترابطه الضلعية تساوي k.
5- أثبت أو انقض كلا من العبارة الآتية : إذا كان البيان مترابطا ضلعيا من الدرجة K، فإنه يكون مترابطا من الدرجة k.
6- افترض أن G بيان له أكثر من k من الرؤوس، و بحيث إن G ليس بيانا تام. أثبت أنه إذا لم يكن G مترابطا من الدرجة k، فإن هناك مجموعة فاصلة حجمها k-1 لهذا البيان.
7- أثبت أن البيان G مترابط من الدرجة k إذا و فقط إذا كان Kr G ˅ (التعريف 6.3.3) مترابطا من الدرجة k + r.
8- جد صيغة تعطي عدد الأشجار المولدة لبيان مترابط بدلالة الأشجار المولدة لقوالبه.
9- جد أصغر بيان بسيط منتظم من الدرجة الثالثة بحيث يكون مقدار ترابطه يساوي 1، و أثبت ذلك.
10- افترض أن k,n أعداد صحيحة موجبة، بحيث n عدد زوجي، و k عدد فردي، و n>k>1. افترض أن G هو البيان البسيط المنتظم من الدرجة k المشكل بوضع n من الرؤوس على دائرة، و بجعل كل رأس يجاور (يرتبط بضلع) الرأس المضاد له على الدائرة بالإضافة إلى مجاورته لأقرب (k-1)/2 رأسا في كلا الاتجاهين على الدائرة، أثبت أن k(G) = k (Harary [1962a]).
11- ليكن G بيانا مترابطا، بحيث توجد لكل ضلع e حلقتان هما : C1 و C2 تحتويان على e، و بحيث إن e الضلع الوحيد المشترك بينهما. أثبت أن G مترابط ضلعيا من الدرجة 3، استخدم هذه النتيجة لإثبات أن بيان بيترسون مترابط ضلعيا من الدرجة الثالثة.
12- استخدم القضية 12.1.4 و النظرية 11.1.4 لإثبات أن بيان بيترسون مترابط من الدرجة 3.
13- أثبت أن حذف قاطعة ضلعية حجمها 3 من بيان بيترسون يعزل رأسا.
14- افترض أن G بيان زوجي الرتبة مترابط من الدرجة r، بحيث إن K1,r+1 بيان جزئي من G. أثبت أن ل G معامل 1. (1-facter) (Summer [1976b])
15- افترض أن F مجموعة جزئية من الأضلاع في بيان G. أثبت أن F قاطعة ضلعية إذا و فقط إذا كانت تحوي عدد زوجيا من أضلاع كل حلقة في G. فعلى سبيل المثال، عندما G = Cn، فإن كل مجموعة زوجية من الأضلاع تشكل قاطعة ضلعية، و لا توجد أي مجموعة فردية تمثل قاطعة ضلعية (مساعدة : لإثبات الشرط الكافي ؛ علينا أن نثبت أنه يمكن وضع مركبات F في مجموعتين، بحيث إن لكل ضلع في F نقطة طرفية في كل من المجموعتين).
16- إذا كان H بيانا جزئيا مولدا لبيان مترابط G، فأثبت أن H يمثل شجرة مولدة للبيان G إذا و فقط إذا كان H* = G-E(H) لا يحوي أي رابطة من G، و إضافة أي ضلع ل H بحدث بيانا جزئيا من G يحوي رابطة من G.
17- افترض أن G بيان بسيط، رؤوسه ؛ [11،......،2،1] حيث i ↔ j إذا و فقط إذا كان i و j عامل مشترك أكبر من 1. حدد قوالب G.
18- أثبت أن درجة كل رأس من رؤوس بيان تكون زوجية إذا و فقط إذا كان كل قالب فيه أويلريا.
19- افترض أن G بيان مترابط، أثبت أنه مترابط ضلعيا من الدرجة k إذا و فقط إذا كان كل قالب فيه مترابطا ضلعيا من الدرجة k.
20- افترض أن H و ’H بيانان جزئيان من البيان G، بحيث إنهما كبيران مترابطان من الدرجة k. أثبت أنهما يشتركان في k-1 رأسا على الأكثر. (Harary-Kodama. [1964])
21- أثبت أن الخوارزمية 23.1.4 تحسب بدقة عدد قوالب أي بيان.
22- طور خوارزمية لحساب المركبات القوية لبيان موجه، و أثبت أن خوارزميتك تعمل. (مساعدة : اعمل نموذجا لهذه الخوارزمية متعمدا على الخوارزمية 23.1.4).
23- استخدم النتائج الموجودة في هذا الدرس لإثبات أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا وفقط إذا أمكن الحصول على G من C3 بعمل مجموعة من عمليات إضافة الأضلاع و قسمتهما.
24- أثبت أنه إذا كان G مترابطا ضلعيا من الدرجة 2، و إذا حصلنا على ’G من G بقسمة أحد أضلاع G، فإن ’G مترابط ضلعيا من الدرجة 2. استخدم هذا الإثبات أنه إذا كان للبيان تحليل مقبضي مغلق، فإن البيان يكون مترابطا ضلعيا من الدرجة 2 (تعليق : هذا إثبات بديل للكفاية في النظرية 10.2.4).
25- افترض أن G بيان موجه حيث [12] تمثل مجموعة رؤوسه، و حيث إن i → j إذا و فقط إذا كانت i تقسم j. جد (12 و 1) k و (12, 1)’k.
26- أثبت العبارة الآتية أو انقضها : إذا كان P مسارا من u إلى v في بيان G مترابط من الدرجة 2. فإنه يوجد مسار Q من ع إلى v بحيث إن Q منفصل داخليا عن P.
27- افترض أن G بيان بسيط، و اجعل H(G) تمثل البيان الذي رؤوسه V(G) بحيث إن uv ϵ E(H) إذا و فقط إذا ظهر كل من u و v في الحلقة نفسها التي في G. أعط توصيفا للبيانات G بحيث يكون H بيانا تاما.
28- استخدم النتائج الموجودة في هذا الدرس لإثبات أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا و فقط إذا أمكن الحصول على G من C3 بعمل مجموعة من عمليات إضافة الأضلاع و قسمتهما.
29- أثبت أن البيان البسيط G يكون مترابطا من الدرجة 2 إذا و فقط إذا تحقق ما يأتي : لكل ثلاثية مرتبة (x, y, z) من الرؤوس المختلفة، يوجد مسار من x إلى z يمر من خلال y (chein [1968]).
30- افترض أن G بيان له أربعة رؤوس على الأقل. أثبت أن G يكون مترابطا من الدرجة 2 إذا و فقط إذا تحقق ما يأتي : لكل زوج X وy حيث X و Y مجموعتان جزئيتان من رؤوس G و بحيث إن ǀXǀ , ǀYǀ ≥2، يوجد مساران منفصلان تمام هما : P1 و P2 في G بحيث يوجد لكل منهما نقطة طرفية في X، و نقطة طرفية أخرى في Y، دورن وجود رؤوس داخلية لأي منهما لا في X و لا في Y.
31- نعرف التحليل المقبضي الجشع لبيان مترابط من الدرجة 2 على أنه تحليل مقبضي يبدأ بأطول حلقة، ثم يكرر إضافة أطول مقبض ممكن. استخدم تحليلا مقبضيا جشعا لإثبات أن كل بيان G مترابط من الدرجة 2 خال من المخالب يحوي [n (G)/3] نسخة من P3، بحيث إن هذه النسخ منفصلة زوجا زوجا. (kaneko-kelmans-Nishimura [2000]).
32- افترض أن G بيان مترابط له ثلاثة رؤوس على الأقل، أثبت أن العبارات الآتية متكافئة (يمكن استخدام نظرية منجر) : a) G مترابط ضلعيا من الدرجة 2. b) كل ضلع في G يظهر في حلقة. c) يوجد في G مسرب مغلق لا يكرر أضلاعا (closed trail)، و يحوي أي ضلعين محددين. d) يوجد في G مسرب مغلق لا يكرر أضلاعا، و يحوي أي رأسين محددين.
33- استخدم نظرية منجر لإثبات أنه إذا كان G بيانا منتظما من الدرجة 3، فإن k(G) = k׳(G) (النظرية 11.1.4).
34- افترض أن 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.
35- افترض أن v رأس في بيان G المترابط من الدرجة 2، أثبت أنه يوجد ل u جوار ر، بحيث إن G – u –v مترابط (Chartrand-Lesniak [1986, p51]).
36- افترض أن G بيان مترابط من الدرجة 2. أقبت أنه إذا كانت كل من T1 و T2 شجرتين مولدتين للبيان G فيمكن تحويل T1 و T2 بإجراء عدة عمليات يتم من خلالها إزالة ورقة (leaf) و إعادة تثبيتها باستخدام ضلع آخر للبيان G.
37- جد أصغر بيان مقدار ترابطه 3، بحيث يكون له رأسان غير متجاورين و منفصلان معا بواسطة أربعة مسارات منفصلة داخليا زوجا زوجا.
38- افترض عدم وجود رؤوس معزولة للبيان G. أثبت أنه إذا خلا هذا البيان من الحلقات الزوجية، فإن كل قالب فيه يكون إما ضلعا أ, حلقة فردية.
39- العضوية في الحلقات المشتركة : a) أثبت أن ضلعين مختلفين ينتميان إلى القالب نفسه في بيان G إذا و فقط إذا كانا ينتميان إلى الحلقة نفسها. b) افترض أن e, ƒ, g ϵ E(G)، و افترض أيضا وجود حلقة في G تمر خلال e و g، و حلقة أخرى تمر خلال f و g. أثبت أنه توجد حلقة في G تمر في e و g. (تعليق : لاحظ أن هذه المسألة تضمن أن علاقة "المساواة أو الانتماء إلى الحلقة" نفسها هي علاقة تكافؤ على أضلاع البيانات التي ليس لها أضلاع فاصلة أو قاطعة، و أن صفوف التكافؤ لهذه العلاقة هي مجموعات أضلاع قوالب البيان).
40- أثبت أن المكعب الزائدي مترابط من الدرجة Qk بإيجاد k من المسارات x,y المنفصلة داخليا زوجا زوجا و ذلك لكل زوج رؤوس x.y ϵ V(Qk).
41- افترض أن G بيان مترابط ضلعيا من الدرجة 2k بحيث إن له على الأكثر رأسين درجتهما فردية، أثبت أنه يوجد لهذا البيان توجيه مترابط ضلعيا من الدرجة k. (Nash-Williams [1960]).
42- افترض أن G بينا مترابط من الدرجة k، و افترض أيضا أن S و T مجموعتان جزئيتان غير متقاطعتين من V(G) حجم كل منهما يساوي k على الأقل، أثبت أنه يوجد للبيان G, k من المسارات T,S المنفصلة (غير المتقاطعة) زوجا زوجا.
43- أثبت لتطبيق عملية التمديد الموجود في المثال 1.3.26 على أن البيان المترابط من الدرجة 3 يعطينا بيانا مترابطا من الدرجة 3. ثم احصل على بيان بيترسون بإجراء تمديد (توسيع) على K4. (تعليق : لقد أثبت Tutte [1966] أن البيان المنتظم من الدرجة 3 بكون مترابطا من الدرجة 3 إذا و فقط إذا أمكن الحصول عليه من K4 بإجراء عدد من عمليات التوسع (التمدد))
44- افترض أن G بيان بسيط مترابط من الدرجة k : a) افترض أن C و D حلقتان في G طولهما أكبر ما يمكن، إذا كانت k =2 أو k = 3، فأثبت أن C و D تشتركان في k من الرؤوس على الأقل، (مساعدة : إذا لم تشتركا فاحصل على حلقة أطول). b) لكل k ≥2، جد بيانا مترابطا من الدرجة k له حلقات مختلفة ، طولها أكبر ما يمكن و تشترك في k من الرؤوس فقط (مساعدة : اعتبر k2,4 عندما k =2).
45- أثبت أنه إذا كان G مترابطا من الدرجة 2، فإن G-xy يكون مترابطا من الدرجة 2 إذا و فقط إذا وقع كل من x و y على حلقة G-xy. ثم استنتج أن البيان المترابط من الدرجة 2 يكون مترابطا من الدرجة 2 بحده الأدنى إذا و فقط إذا كانت كل حلقة بيانا جزئيا مستحدثا (induced subgraph)
46- أثبت أن كل مصفوفة حجمها 2x2 يمكن تدويها تدويرا منسجما.
47- افترض أن N شبكة لأضلاعها سعات معينة، و لنقاط لاتصال قيود محافظة بالإضافة إلى حدود دنيا ƒ(e) ≥ L(e). إذا كان التدفق الملائم الابتدائي معطى فبين كيف يمكن تعديل خوارزمية فورد و فولكرسون لوضع العلامات من أجل البحث عن أكبر تدفق ملائم عبر هذه الشبكة.
48- افترض أن G بيان موجه فيه x, y ϵV (G). و افترض أيضا أن السعات قد حددت على الرؤوس المختلفة عن x و y بدلا من تحديدها على الأضلاع، و افترض وجود حد ثابت للتدفق الكلي عبر كل رأس، و لا يوجد أي حصر على التدفق عبر الأضلاع، وضح كيف يمكن استخدام نظرية تدفق الشبكات العادية لتحديد أكبر قيمة لتدفق ملائم من x إلى y في البيان G الذي حددت سعات رؤوسه.
49- استخدم تدفق الشبكات لإثبات أن البيان G يكون مترابطا إذا و فقط إذا وجد لكل تجزئة ل V(G) لمجموعتين غير خاليتين S و T ضلع له نقطة طرفية في S، و أخرى في T. (تعليق : يوجد إثبات مباشر لهذه المسألة في الفصل الأول. لذا، فهذا مثال على استخدام مطرقة ضخمة لقتل بعوضة أو ذبابة).
50- افترض أنه يوجد k من الأقسام الأكاديمية في إحدى الجامعات الكبيرة. و افترض أيضا أننا نرغب في تعيين لجنة مهمة تختار أستاذا من كل قسم، علما بأن بعض الأساتذة معينين تعيينا مشتركا بين قسمين أو أكثر، و افترض كذلك أنه لا يمكن تعيين أي شخص ليكون ممثلا لأكثر من قسم، و افترض أيضا أن عدد الأساتذة المساعدين يساوي عدد الأساتذة المشاركين و يساوي عدد الأساتذة في هذه اللجنة (افرض أن k تقبل القسمة على 3). بين كيف يمكن إيجاد مثل هذه اللجنة. (مساعدة : جد شبكة بحيث ترتبط وحدات التدفق بالأساتذة الذين تم اختيارهم لهذه اللجنة، و أن السعات تمثل القيود المختلفة، ثم و ضح كيفية استخدام هذه الشبكة لاختبار ما إذا وجدت مثل هذه اللجنة، و أوجدها إن وجدت). (Hall [1956]).
51- استخدم نظرية Gale و Ryser (نظرية 18.3.4) لتحديد ما إذا وجد بيان بسيط ثنائي الفرع تكون درجات رؤوس إحدى مجموعتي رؤوسه هي : (5.4.4.2.1) و كذلك درجات رؤوس المجموعة الثانية من رؤوسه هي : (5.4.4.2.1) أيضا.
52- أكمل تفاصيل إثبات النتيجة 21.3.4، و ذلك بإثبات الشروط الضرورية و الكافية لوجود دوران في شبكة لها حدود دنيا و عليا.
