1- أثبت أن كل بيان هو بيان التقاطع لعائلة من الأشجار الجزئية لبيان معين.
2- تسمى البيانات التي تخلو من P4 مرافقات البيانات () و التي ترمز إلى " تصغير المتممة" نقول : إن البيان هو تصغير متممة إذا أمكن تصغير هذا البيان إلى البيان الخالي عن طريق أخذ متممات المركبات (مركبات البيان) بالتتابع : a) أثبت أن البيان G يخلو من P4 إذا و فقط كان تصغير متممة. b) استخدم الفرع (a) و نظرية البيان الكامل لتبرهن أن كل بيان خال من P4 يكون كاملا. (Seinsche [1974])
3- تحديد العصب. افترض أن G = G1UG2، و أن G1∩G2 عصبة، و أن G1 و G2 بيانات كاملة. أثبت أن G يكون بيانا كاملا دون استخدام تمهيدية مجموعة قطع النجمة.
4- جد بيانا ناقصا G له مجموعة قطع النجمة C بحيث إن القلق C- للبيان G هو بيانات كاملة (تعليق : التحديد عند مجموعات قطع النجمة لا يحافظ على الكمال، ع الرغم من عدم وجود مجموعة قطع النجمة للبيانات الحرجة من الدرجة P).
5- افترض أن G حاصل الضرب الكارتيزي لبيانات تامة. أثبت أن a(G)=ᶿ (G)، و برهن كذلك أن k2 □ k2 □k2 غير كامل.
6- أثبت أن C5 V K1 هو البيان الوحيد الحرج لونيا الذي درجته اللونية تساوي 4، و له ستة رؤوس.
7- أثبت أن G حلقة فردية إذا و فقط ‘ذا كان a(G) = (n(G-1) / 2 و a(G-u-v) = a(G) لكل u.v ϵ V(G) (Melnikov-vizing [1971], Greenwell [1978]).
8- أصف اختبارا لخوارزمية أل MCS ؛ لتختبر ما إذا كان الترتيب الناتج ترتيب حذف مبسطي (Tarjan-Yannakakis [1984].
9- أثبت مباشرة (دون استخدام ترتيب الحذف الميسطي) أن بيان التقاطع لعائلة أشجار حزئية من شجرة معينة لا يحوي حلقة غير وترية.
10- أثبت أنه يوجد لكل بيان وتري تمثيل تقاطع بأشجار جزئية لسجرة مضيفة درجتها الكبرى تساوي 3.
11- افترض أن Q عصبة عظمى في بيان وتري G، لكل x ϵV(G)، أثبت أنه يوجد ل Q رأسان، بحيث أن بعد كل منهما عن x يكون مختلفا عن بعد الآخر، (Voloshin [1982]).
12- بيانات تقاطع الأشجار الجزئية لبيان. يعرف التوجيه الأخوي (الودي) لبيان على أنه توجيه للبيان، بحيث يكون كل زوج من الرؤوس التي لها تابع (خلف) مشترك متجاورا : a) (-) أثبت أن البيان يكون بيانا وتريا إذا و فقط إذا وجد له توجيه أخوي غير حلقي. b) (-) احصل على بيان ليس له توجيه أخوي. c) تعد عائلة من الأشجار في بيان معين قابلة للتجذير إذا أمكن تعيين جذور لهذه الأشجار بحيث بتقاطع زوج منها إذا انتمى أحد الجذرين على الأقل إلى كلتا الشجرتين الجزئيتين. أثبت أن للبيان G توجيها أخوي إذا و فقط إذا كان G بيان تقاطع لعائلة أشجار جزئية لبيان معين، و بحيث تكون هذه العائلة قابلة للتجذير.
13- أثبت أن البيان البسيط G يكون غابة إذا و فقط إذا وجد رأس مشترك لكل عائلة مسارات متقاطعة زوجا زوجا في G. (مساعدة : لإثبات الكفاية ؛ استخدم الاستقراء على عدد المسارات في العائلة).
14- توصيف بيانات الانشقاق بمنع بعض البيانات الجزئية. نقول : إن البيان بيان انشقاق إذا أمكن تجزئة رؤوسه إلى عصبة و مجموعة مستقرة : a) أثبت أنه إذا كان G بيان انشقاق فإن G و Ġ يكونان بيانين و تريين. لاحظ أنه إذا كان كل من G و Ġ بيانا وتريا، فلا يوجد للبيان G بيانات جزئية مستحدثة ضمن المجموعة {C4, 2K2, C5}. b) أثبت أنه إذا كان G بيانا بسيطا بحيث لا يوجد له بيان جزئي مستحدث ضمن المجموعة {C4, 2K2, C5}، فإنه يكون بيان انشقاق. (مساعدة : من بين العصب ذات الحجم الأكبر، افترض أن Q أحد هذه العصب بحيث يكون عدد أضلاع G-Q أقل ما يمكن. أثبت أن G-Q تكون مجموعة مستقرة من خلال استخدام خيار Q، و شروط البيانات الجزئية الممنوعة)، (Hammer-Simeone [1981]).
15- حدد الأشجار التي تكون بيانات انشقاق، و ابن زوجا من بيانات الانشقاق غير المتشاكلة التي لها متتالية الدرجات نفسها.
16- تعرف الأشجار من نوع k على أنها البيانات التب تظهر من عصبة من الدرجة K بتكرار إضافة 0 أو أكثر من الرؤوس الجديدة التي تربط بالعصبة في البيان القديم. أثبت أن G يكون سجرة من نوع K إذا و فقط إذا حقق الخواص الثلاث الأتية : a) إذا كان مترابطا. b) إذا كانت له عصبة من الدرجة k،و لكن لا توجد له عصبة من الدرجة k+2. c) إذا كان كل فاصل رؤوس أصغري له عصبة من الدرجة k.
17- خاصية هيلي لخطا الأعداد الحقيقية. افترض أن Ik,...،I1 فترات حقيقة متقاطعة زوجا زوجا . أثبت أنه توجد نقطة مشتركة بين Ik,...،I1
18- أثبت مباشرة أن الشجرة تكون بيان فترة إذا و فقط إذا كانت جرارة (شجرة تحوي مسارا يحوي الأقل رأسا لكل ضلع).
19- افترض أن G بيان فترة. أثبت أن Ġ بيان مقارنة، و أن G بيان وتري. (مساعدة : جد ترتيب حذف مبسطي).
20- أثبت أنه يوجد للبيان G تمثيل بفترات إذا و فقط إذا كان لمصفوفة وقع العصبة و الرؤوس ل G خاصية الواحدات المتتابعة.
21- أثبت أن البيان G بيان فترة إذا و فقط إذا أمكن ترتيب رؤوسه على الشكل vn، ...، v1، حيث إن vi↔vk تعطي vj↔vk عندما i
22- أثبت أن G بيان فترة وحدة (يمكن تمثيله بفترات لها الطول نفسه) إذا و فقط إذا امتلك A(G)+1 خاصية الواحدات المتتابعة (Roberts [1968]).
23- أثبت أن G يكون بيان فترات فعلي (قابل للتمثيل بفترات بحيث لا توجد أي فترة تحوي فعليا فترة أخرى) إذا و فقط إذا كان لمصفوفة الوقوع للعصب و الرؤوس له خاصية الواحدات المتتابعة لكل من الصفوف و الأعمدة، (Fishburn [1985]).
24- أثبت أن كل بيان خال من P4 يكون بيان مينيل.
25- أثبت أن كل وتري يكون تثليثا o-.
26- افترض أن C حلقة في بيان ليس له حلقة فردية مستحدثة. أثبت أن ل V(C) ثلاثة رؤوس متجاورة زوجا زوجا بحيث إن المسارات جميعها التي تربط بين هذه الرؤوس في C لها طول فردي.
27- أثبت أن الشروط الآتية متكافئة : a) يوجد لكل حلقة فردية طولها 5 على الأقل زوج من الأوتار المتفاطعة. b) لكل زوج x, y ϵV(G)، تكون المسارات اللاوترية من x إلى y إما زوجية كلها أو فردية كلها. (مساعدة : ل A ←B، خذ في الحسبان زوجا P1 و P2 من المسارات من x إلى y لها نوعيات متضادة، بحيث يكون مجموع أطوالها أصغري)، (Burlet-Uhry [1984]).
28- أثبت أن كل بيان قابل للترتيب ترتيبا كاملا يكون كاملا بقوة (مساعدة : استخدم التمهيدية 25.1.8) (Chva tal [1984]).
29- نعرف التجزئة التخالفية (المتخالفة) للبيان G على أنها تجزئة ل V(G) إلى مجموعتين غير خاليتين X و Y، بحيث إن كلا من G [X]، و [Y] Ġ غير مترابط. لقج خمن كفتال (Chvaʼtal [1985 b) أنه لا توجد تجزئة تخالفية لأي بيان ناقص أصغري. أثبت أن هذا يعطي تمهيدية مجموعة قطع النجمة و أن ال SOGC تعطي هذه المخمنة.
30- نقول : يشكل الرأسان x و y زوجا زوجيا إذا كان لكل مسار لا وتري من x إلى y طول زوجي (بمعنى أن عدد أضلاع هذا المسار زوجي). تعد التوائم (الرؤوس غير المتجاورة التي لها الجوار نفسه) حالة خاصة : a) افترض أن S1 و S2 مجموعتنا متقرتان كبريان في بيان قابل للتجزئة G. أثبت أن البيان الجزئي المولد من الفرق التماثلي ل S1 و S2 يكون مترابطا. (Bland-Huang-Trotter [1979]). b) استخدم فرع (a) لتبرهم أنه لا يوجد زوج زوجي لأي بيان حرج من الدرجة p. (تعليق : إذن، لا يوجد توائم لأي حرج من الدرجة p، و هذا يبرهن ثانية أن مضاعفة الرؤوس يحافظ على الكمال)، (Meyniel [1987], Bertschi-Reed [1988])
31- افترض أن G بيان قابل للتجزئة، و أن S1 و S2 مجموعتان مستقرتان في التلوين الأمثل ل G-x. استخدم فرع (a) من المسألة السابقة لتبرهن أن البيان الجزئي الذي تولده {x} U S1 U S2 يكون ثنائي الترابط (مترابط من الدرجة 2). (Buckingham-Golumbic [1983])
32- إن البيان K1,3+e. باستخدام الكمال لبيانات مينيل، أثبت أن البيانات الخالية K1,3+e تحقق ال SPGC .(Meyniel [1976]).
33- 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 تحقق لبيانات الدائرة.
34- أعط توصيفا مميزا للبيانات التي تشكل مجموعاتها المستقرة عائلة من المجموعات المستقلة لما ترويد على مجموعة الرؤوس.
35- أثبت أن المجموعات المستقرة لبينا لا تكون بالضرورة هي المجموعات المستقلة لماترويد، وذلك من خلال إيجاد بيانات موزونة الرؤوس ؛ حيث إن النسبة بين أكبر وزن لمجموعة مستقرة الوزن الذي تم إيجاده بجشع إلى مجموعة مستقرة تكون كبيرة اختياريا.
36- أثبت أن كل ما ترويد تجزئة يكون ما ترويد مستعرضا.
37- عدل الخوارزمية الجشعة لتحصل (مع إثبات) على خوارزمية لإيجاد مجموعة مستقلة موزونة كبرى في ماترويد له أوزان حقيقية اختيارية (ليست بالضرورة غير سالبة) على العناصر.
38- أعط توصيفا مميزا للبيانات التي تشكل مواءمتها عائلة من المجموعات المستقلة لماترويد على مجموعة الأضلاع.
39- حدد الماترويدات التي تكون متحققة بيانيا. و أعط توصيفا مميزا للبيانات التي ماترويدات حلقاتها ماترويدات تجزئة.
40- باستخدام الاعتماد الخطي فقط، أثبت أن الماترويدات المتجهة تحقق خاصية الحلقات المستحدثة ؛ إن إضافة عنصر واحد إلى مجموعة مستقلة من المتجهات يوجد مجموعة غير مستقلة واحدة على الأكثر
41- صف حلقات الماترويد المستعرض M بدلالة البيان الثنائي الفرع المناظر G، باستخدام خواص البيانات الثنائية الفرع فقط. و برهن أن M تحقق خاصية الحذف الضعيف.
42- أفترض أن 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).
43- استخدم نظرية كونج و إيجرفاري (König- Egervʼary) لتبرهن-مباشرة-أن دالة الرتبة للماترويد المستعرض تكون مقياسية جزئية.
44- أفترض أن M نظام وراثي بأوزان غير سالبة على E، أثبت-مباشرة-أنه إذا كان M يحقق خاصية تبديل الأساس (B)، فإن الخوارزمية الجشعة تولد دائما أساسا موزونا أعظم.
45- بديهيات ماترويد بديلة. افترض أن M نظام وراثي، أثبت-مباشرة-أنه إذا كان M يحقق خاصية تبديل الأساس (B)، فإن الخوارزمية الجشعة تولد دائما أساسا موزونا أعظم.
46- بديهيات ماترويد بديلة. أفترض أن M نظام وراثي، أثبت تضمينات M الآتية مباشرة : a) تتضمن (-) المقياسية الجزئية (R) الامتصاص الضعيف (A). b) يتضمن الامتصاص القوي (ʼA) المقياسية الجزئية (R) (دون استخدام الانتظام (الاتساق)). (مساعدة : استخدام الاستقراء على X∆Y). c) يتضمن تبديل الأساس (B) وحدانية الحلقات المستحدثة (J). d) تتضمن (-) وحدانية الحلقات المستحدثة (J) الحذف الضعيف (C). e) تتضمن وحدانية الحلقات المستحدثة (J) التوسيع (J). (مساعدة : استخدم J و الاستقراء على I1-I2 لتحصل على التوسيع)
47- لأي نظام وراثي، لأثبت أن خاصية الحذف الضعيف تتضمن خاصية الحذف القوي مستخدما الاستقراء على ǀC1 U C2ǀ، .(Lehman [1964])
48- أثبت أنه يوجد على الأقل 2r مجموعة مغلقة للماترويد الذي رتبته r (Lazarson [1957]).
49- أثبت أن الماترويد يكون بسيطا إذا و فقط إذا تحقق ما يأتي : 1) لا يوجد أي عنصر يظهر في كل مستوى زائدي. 2) من كل زوج من العناصر المختلفة، يوجد مستوى زائدي يحوي واحدا منها بالضبط. أثبت أن هذين الشرطين يكفيان لأن تكون عائلة من المجموعات جمعا من المستويات الزائدية لماترويد بسيط.
50- في ماترويد ما، أثبت أن مجموعة تكون تحت أساس إذا و فقط إذا كانت مستوى زائديا.
51- استخدم خاصية الحذف الضعيف في إعطاء توصيف مميز عندما تكون عائلة من المجموعات عائلة مستويات زائدة لماترويد ما.
52- أثبت أن المجموعات المغلقة لماترود ما هي المتممات لاتحادات مرافقات الحلقات.
53- افترض أن 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) من المستويات الزائدية المختلفة.
54- أثبت الخواص الآتية للمجموعات المغلقة لماترويد : a) تقاطع أي مجموعتين مغلقتين يساوي مجموعة مغلقة. b) يساوي مولد أي مجموعة تقاطع المجموعات المغلقة جميعها التي تحوي هذه المجموعة. (تعليق : لذا، فإن Ƃx هي المجموعة الوحيدة المغلقة الصغرى التي تحوي X).
55- أثبت أن M.X لا تحوي عرى إذا و فقط إذا كانت Ẋ مغلقة.
56- الأساسات و مرافقات الحلقات في الماترويدات : 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 بديهيا و تافها لماترويدات الحلقات.
57- أثبت أن ثنوي الماترويد البسيط (لا يحوي عرى و لا عناصر متوازية) يمكن أن يكون غير بسيط. و بين إمكانية أن تكون مجموعة معينة حلقة أو مرافق حلقة في ماترويد ما.
58- استخدم ثنوية الماترويدات لتبرهن صيغة أوبلر لبيانات المستوى المترابطة.
59- إن بيان أساسات الماترويد هو البيان الذي له رأس لكل أساس للماترويد، حيث تكون الأساسات متجاورة إذا كان حجم الغرف التماثلي لهذه الأساسات يساوي 2. أثبت على وجود حلقة مولدة لكل بيان أساسات ماترويد، و وضح النتيجة لكل من الماترويدات البيانية و الموحدة (مساعدة : استخدم التقليص و الحصر استقرائيا لإيجاد حلقة مولدة من خلال أي ضلع)، ([ 1986,p72], Kung [1972]Holzmann-Harary)
60- استخدم نظرية تقاطع الماترويدات لتبرهن أنه في كل توجيه لا حلقي ل G يمكن تغطية الرؤوس على الأكثر ب a(G) من المسارات المنفصلة زوجا زوجا. (Chappell [1994])، (تعليق : هذه حالة خاصة من النظرية 33.4.8. للبيانات الموجهة اللاحلقية).
61- أثبت أن حصر الماترويدات المستعرضة و اتحادها يكون ماترويدات مستعرضة، لكن التقليص، و الماترويدات الثنوية للماترويدات المستعرضة ليست بالضرورة ماترويدات مستعرضة.
62- أفترض أن G بيان موزون على n من الرؤوس، و افتض أيضا أن، E1…En-1، تجزئة ل E(G) ل n-1 مجموعة. هل توجد خوارزمية على صورة كثيرة حدود بالنسبة إلى الزمن، لحساب عدد الأشجار المولدة التي لها وزن أصغر من بين الأشجار المولدة التي لها وزن أصغر من بين الأشجار التي لها ضلع واحد بالضبط في كل مجموعة جزئية Ei ؟
63- استخدم التوصيف المميز للبيانات التي لها k من الأسجار المولدة المنفصلة ضلعيا زوجا زوجا (النتيجة 59.2.8) لتبرهن على وجود k سجرة مولدة منفصلة ضلعيا زوجا زوجا لكل بيان مترابط ضلعيا من الدرجة 2k، و كل k جد بيانا مترابطا ضلعيا من الدرجة 2k بحيث لا يوجد له k+1 من الأشجار المولدة المنفصلة ضلعيا زوجا زوجا. (]Nash-Williams [1961]).
64- افترض أن S مجموعة من نسع نقاط في المستوى (لا يوجد منها ثلاث نقاط على استقامة واحدة). أثبت أن S تحوي رؤوس مضلع خماسي محدب. أعط مثالا على ثماني نقاط لا تتحقق فيها هذه النتيجة.
65- 1. افترض أن لديك قرصين متحدين في المركز، و أن لكل منهما 20 قطاعا دائريا من الحجم نفسه. تم طلاء عشرة قطاعات و لكل قرص بالون الأحمر، و عشرة قطاعات أخرى باللون الأزرق ضمن ترتيب معين. أثبت أنه يمكن محاذاة القرصين أو صفهما بطريقة معينة بحيث إن لعشرة من قطاعات القرص الداخلي على الأقل اللون نفسه لقطاعات القرص الخارجي المرتبطة بها.
66- لكل n ϵ N، اجعل S هي المجموعة المؤلفة من n+1 عنصرا في {1,…,2n}. أثبت أنه يوجد في S عنصران بحيث يقسم أحدهما الآخر، و يوجد كذلك عنصران آخران، القاسم المشترك الأعظم لهما يساوي 1. أثبت أن هاتين النتيجتين هما أفضل ما يكمن من خلال إيجاد مجموعة جزئية حجمها n لا تتحقق عليها هذه النتائج.
67- استخدم مبدا طواقي الحمام و المجاميع الجزئية لتبرهن كلا من العبارتين الآتيتين : a) تحوي كل مجموعة مؤلفة من n من الأعداد الصحيحة مجموعة جزئية غير خالية مجموعها يقبل القسمة على n( أعط مثالا على مجموعة مؤلفة من n-1 من الأعداد الصحيحة لا تحقق فيها هذه الخاصية). b) لتكن x ϵ R، أثبت أن عنصرا واحدا على الأقل من المجموعة {x, 2x, …,(n-1)x} يختلف عن عدد صحيح بمقدار 1/n على الأكثر.
68- يوجد في ناد خاص 90 غرفة و 10 عضو. زود الأعضاء بمفاتيح لهذه الغرف بحيث يكون ل 90 منهم مقدرة لدخول الغرف، بمعنى أنه تم تزويد كل شخص من هؤلاء ال 90 بمفتاح لغرفة مختلفة. (أفترض عدم اشتراكهم بالمفاتيح). أثبت أنه يلزمنا 990 مفتاحا، و أن العدد 990 كاف.
69- أفترض أن T شجرة. استخدم التقنية الموجودة في النظرية 2.3.8 لترهن أن مركز t يتألف من رأس واحد، أو من رأسين متجاورين (هذا يبرهن النظرية 13.1.2 مرة أخرى)، (Jordan [1869], Graham-Entringer- Szeʼkey [1994]).
70- أثبت أن كل مجموعة مؤلفة من 2m+1 من نقاط شبكية صحيحة (شبكية أعداد صحيحة) في Rm تحوي زوجا من النقاط بحيث يكون مركزه المتوسط (متجه الوسط) أيضا نقطة شبكية صحيحة.
71- أثبت أنه يوجد لكل تلوين ثنائي لنقاط شبكية صحيحة في Rm جمع فيه n من النقاط التي لها اللون نفسه بحيث يكون مركزها المتوسط (متجه الوسط) نقطة صحيحة لها أيضا اللون نفسه (مساعدة : لا حاجة إلى نظرية رامزي بسبب وجود إثبات قصير باستخدام مبدأ طواقي الحمام فقط)، (Boʼna [1990]).
72- أفترض أن S جمع مؤلف من n+1 عدد صحيحا مجموعه يساوي .k ل K≤2n+1، أثبت أنه يوجد ل S مجموعة جزئية، حاصل جمع عناصرها يساوي i لكل i ϵ [K]. لكل n، أعط مثالا لجمع بحيث تفشل هذه النتيجة عندما k=2n+2.
73- لكل عدد زوجي n، جد ترتيبا ل E(Kn)، بحيث يساوي أكبر طول لمسرب متزايد n-1. (تعليق : هذا يبرهن أن النظرية 4.3.8 هي أفضل ما يمكن عندما يكون n عدد زوجيا، إضافة ما يمكن عندما يكون n عدد فرديا يساوي 9 على الأقل. إلا أن البناء يكون أصعب كثيرا)، (Graham- Kleitman [1973]).
74- أفترض أن S مجموعة مؤلفة من R(m,m ; 3) من نقاط المستوى بحيث لا يوجد منها ثلاث نقاط على استقامة واحدة، أثبت أن S تحوي m نقطة بحيث تشكل هذه النقاط مضلعا (Tarsi) عدد أضلاعه m.
75- تذكر ان البينا الموجه يكون بسيططا إذا لم يشترك أي ضلعين من أضلاعه بالزوج المرتب نفسه من النقاط الطرفية. يعرف الدوري الرتيب على أنه دوري يكون فيه توجيه الأضلاع متوافقا دائما مع رتبة الدلائل على الرؤوس، أو أنه بكون غير متوافق دائما مع هذه الرتبة. و يكون للبيان الموجه خالي العرى التام نسخة واحدة من كل زوج مرتب من الرؤوس المختلفة بوصفها ضلعا. إذا أعطيت m، فبرهن أنه إذا كانت N كبيرة جدا، فإن لكل بيان موجه بسيط خالي العرى رؤوسه [N] مجموعة مستقلة من الرتبة m، أو له دوري رتيب رتبته m، أو له بيان موجه خالي العرى تام رتبته m
76- جد قيمة عدد رامزي R(K1,m,K1,m). (مساعدة : يعتمد الجواب على ما إذا كانت m و n زوجية أو فردية).
77- أفترض أن T شجرة على m من الرؤوس، إذا علمت أن m-1 يقسم n-، فجد عدد رامزي R(t, k1,n). (Burr [1974]).
78- أثبت أن R(c4,c4) = 6. (تعليق : يوجد العديد من البراهين).
79- أثبت أن R(2K3, 2K3). (مساعدة : اختزال المسألة لحالة الشكل الفراشي الذي فيه مثلثات من اللونين بالإضافة إلى حلقة خماسية أحادية اللون، ثم استخدم التماثل).
80- أثبت أن R(mK2, mK2)=3m-1.
81- يعرف تضاعف رامزي للبيان G على أنه أصغر عدد من النسخ أحادية اللون من G في تليون ثنائي لأضلاع عصبة على R(G,G) من الرؤوس. أثبت أن تضاعف رامزي ل K3 يساوي 2.
82- أثبت أنه يوجد لكل نقطة في منطقة مثلثية تعبير وحيد بوصفه تركيبا محدبا لرؤوس المثلث (نقصد بالتركيب المحدب التركيب الخطي الذي تكون فيها المعاملات غير سالبة و مجموعها يساوي 1).
83- تمهيدية سبيرنر في الأبعاد زائدي. إن التقسيم المبسطي يعبر عن المبسط ذي البعد k بصفته اتحاد لمبسطيات (خلايا) من البعد k بحيث تتقاطع أي خليتين في المبسط الذي تحدده زواياها المشتركة. و أن الخلية تامة الوسم هي الخلية التي زواياها {0,…,k}. أعط تعريفا للتعليم (وضع علامات دالة أو وسم) الفعلي، بحيث يحوي كل وسم فعلي لتقسيم مبسطي لمبسط من الدرجة k خلية تامة الوسم. أثبت هذه النظرية. (مساعدة : تعد تمهيدية سبيرنر في البعد 2 (نظرية 17.3.8) شاهدا حيا على خطوة الاستقراء لإثبات بالاستقراء على k).
84- احسب عرض نطاق كل من : Pn, Kn, Cn.
85- احسب عرض نطاق (Eitner [1979]. Kn1,…,nk.
86- احصل على حدود عليا و أخرى و سفلى تختلف ب 1 للبعد الجدائي لبيان بيترسون (الحد العلوي سوف يكون على الأرجح القيمة الصحيحة، و لكن برهنة أنه لا يمكن تحسينه يكون صعبا و مملا).
87- حدد البيانات على n من الرؤوس جميعها التي يساوي بعدها الجدائي n-1. (Lovẚsz-Ne→et řil Pultr[1980]).
88- إذا كانت r معطاة، فاحسب pdim (Kr+mK1) لكل m≥1. (Lovẚsz-Ne→et řil Pultr[1980]).
89- احسب البعد الجذائي لكعب ثلاثي الأبعاد.
90- أثبت أن C2k+1 غير قابل لغمس يحافظ على المسافات في أي جداء كارتيزي لعصب إذا كان K>1.
91- حدد بعد المكعب المسحوق ل C5.
92- حدد بعد المكعب المسحوق ل K3,3. (مساعدة : استخدم التماثل لاختزال تحليل الحالة).
93- تدعى مسألة انتشار الإشاعة "مسألة الهاتف" أيضا، أما المسألة المقابلة للبيانات الموجهة فتدعى "مسألة التلغراف". بوصفها دالة في n، حدد العدد الأصغر للتناقلات في اتجاه واحد بين n من الأشخاص بحيث يملك كل شخص مسارا ناقلا للأشخاص الآخرين جميعهم. (Harary-Schwenk [1974]).
94- ليكن D بيانا موجها يحل مسألة التلغراف بحيث يصل كل رأس معلومات من الرؤوس الأخرى مرة واحدة بالضبط. أثبت أنه يوجد n-1 رأسا في D على الأقل يسمعون معلوماتهم الخاصة. و لكل n، أنئ مثل D بحيث يكون n-1 رأسا فقط يسمعون معلوماتهم الخاصة، في حين يوجد مسار واحد متزايد تماما لكل x≠y من x إلى y(Seress [1987]).
95- الخاصية NOHO : a) ليكن G بيانا مترابطا له 2n-4 ضلعا، و يملك ترتيبا خطيا يحل مسألة انتشار الإشاعة و يحقق NOHO (لا توجد حلقة متزايدة). افترض أيضا أن n(G) > 8. و أنه يوجد على الأكثر رأسان درجتهما 2. أثبت أن البيان الذي تم الحصول عليه بحذف المكالمات الأولى و الأخيرة للرؤوس في G يملك 4 مركبات ؛ اثنتين منهما رؤوس معزولة و الائنتين الأخريين جرارين يملكان الحجم نفسه. (West [1982a]). b) لكل عدد زوجي n ≥ 4، أنشئ بيانا مرتبا مترابطا له 2n-4 ضلعا يحقق خاصية NOHO. (مساعدة : استخدم الخواص البنائية التي برهنت في فرع (a) لترشدك في البحث).
96- نهج (أسلوب 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] أن هذا هو الأمثل).
97- أفترض أن رأسا في بيان بسيط G يرغب في نشر معلومات للرؤوس الأخرى جميعها. و أنه في كل وحدة زمنية، فإن كل {اس يعرف المعلومة يستطيع إجراء مكالمة مع جار لا يعرف هذه المعلومة. إن الزمن المطلوب لنشر المعلومة من v هو العدد الأصغر من الوحدات الزمنية، بحيث تستطيع الرؤوس جميعها معرفة المعلومة. ابن بيانا G على n من الرؤوس له أقل من 2n ضلعا بحيث يستطيع كل رأس في G نشر المعلومة على الأكثر في زمن يساوي (1+1gn). . (Grigni-Peleg[1991])
98- أثبت أن Kk,m يكون قابلا للاختيار من الدرجة k إذا و فقط إذا كان m
99- أثبت أن كل بيان وتري G يكون قابلا للاختيار من الدرجة X(G).
100- أثبت أن كل بيان مترابط G يملك تلوينا قائميا فعليا من قوائم، بحيث يكون ǀL(v)ǀ ≥ d(v) لكل v إذا وجدت متباينة صارمة لرأس واحد على الأقل.
101- تكافؤ انظرية ديلورث و نظرية كونج و إيجرفاري : a) إذا أعطيت بيانا ثنائي الفرع G، فطبق نظرية ديلورث على توجيه متعد له لتحصل على نظرية كونج و إيجرفاري. b) إذا أعطيت بيانا موجها متعد D، و ليكن G هو الشطر ل D كما عرف في التعريف 20.4.1. فطبق نظرية كونج و إيجرفاري على g لتحصل على نظرية ديلورث ل D.
102- أثبت أن كل بيان سوي بسيط منتظم من الدرجة 3 مترابط ضلعيا من الدرجة 2 يتفكك إلى مسارات طولها 3. و برهن العبارة نفسها للتثليثات السوية. ( Jü nger -Reinelt-Pulleyblank [1985]).
103- أثبت أن النظرية 35.4.8 أفضل ما يمكن عنمدما تكون m-1 تقسم n-1.
104- ليكن G بيانا بحيث تكون Ġ يخلو من المثلثات، و ليس غاية. أثبت أن G يملك حلقة طولها n(G)/2 على الأقل. (مساعدة : استخدم النظرية 37.4.8) (N. Graham)
105- استخدم نظرية و ودال لتثبيت نظرية أور، و استخدم نظرية مينيل نظرية و ودال.
106- استخدم نظرية مينيل لتبرهن أن بيانا موجها صارما على n من الرؤوس مسارا مولدا إذا تحقق أن : d(u)+d(v)≥2n-3 لكل زوج u,v من الرؤوس المختلفة غير المتجاورة.
107- حدد أصغر بيان بسيط مترابط بحيث لا يكون متوازنا. a) تفسير الفضاء الحلقي و فضاء الروابط. معطى بيان G، أثبت أن : b) الفرق التماثلي لبيانين جزئيين زوجيين زوجيين هو بيان جزئي زوجي. c) الفرق التماثلي لقطعين ضلعيين هو قطع ضلعي. كل قطع ضلعي يشترك مع كل بيان جزئي زوجي بعدد زوجي من الأضلاع.
108- حدد العدد المتوقع للمثلثات الأحادية اللون في تلوين عشوائي من الدرجة 2 ل E(K6).
109- جيش من الحواسيب مرتب على هيئة شجرة تامة ذات متعدد (k-ary tree) k مع أوراق على بعد 2 من الجذر. عند زمن مثبت، بعمل كل رأس باحتمال p بصورة مستقلة عن الرؤوس الأخرى. و عندما لا يعمل رأس ما، فإنه لا يمكن الوصول إلى أي جزؤ من السجرة الجزئية التي تقع تحت هذا الرأس. ما العدد المتوقع للرؤوس التي يمكن الولوج إليها من الجذر.
110- لتكن G مواءمة حجمها n. اختنر مجموعة مونة من k من الرؤوس بصورة عشوائية. احسب العدد المتوقع للأضلاع المحدثة من خلال الرؤوس المختارة.
111- يتكون البيان الزائد (hypergraph) من حشد رؤوس و حشد آخر من الأضلاع ؛ فإذا كانت مجموعة الرؤوس هي V، فإن الأضلاع هي مجموعات جزئية منV. و العدد اللوني c(H) لبيان زائد H هو العدد الأصغر من الألوان الذي يحتاج إليه لوسم الرؤوس بحيث لا يوجد ضلع يكون أحادي اللون. و يكون البيان الزائد موحدا من الدرجة k (k-uniform) إذا كانت أضلاعه جميعها حجمها k : a) أثبت أن كل بيان زائد موحد من الدرجة k عدد أضلاعه أقل من 2K-1 يكون قابلا للتلوين من الدرجة 2. (Erdös [1963]). b) استخدم فرع (a) لتبرهن أنه إذا امتلك كل رأس في بيان ثنائي الفرع على n من الرؤوس قائمة فيها أكثر من 1+1gn من الأولان القابلة للاستخدام، فإن تلوينا فعليا يمكن اختياره من هذه القوائم.
112- استخدم طريقة الحذف لتبرهن أن البيان الذي n من الرؤوس، و معدل درجة رؤوسه d≥1 يملك مجموعة مستقلة لها n/(2d) رأسا على الأقل. ( مساعدة : اختر مجموعة جزئية عشوائية تشمل كل رأس احتماله p بصورة مستقلة لتختار فيما بعد. و احسب العدد المتوقع للأضلاع المحدثة).
113- ليكن H بيانا. للثابت p، أثبت أن Gp كله تقريبا يحوي H بوصفه بيانا جزئيا محدثا.
114- 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.
115- يمكن توليد دوري عشوائي موسوم بتوجيه كل ضلع vi vj من vi→vj أو من vi→vj بصورة مستقلة مع احتمال 2/1 : a) أثبت أن كل دوري تقريبا يكون مترابطا بصورة قوية. b) في دوري ما، "الملك" هو رأس يمكنه الوصول إلى أي رأس آخر بسمار طوله 2 على الأكثر. و من المعلوم أن كل دوري يحوي ملكا. هل صحيح أنه في كل دوري تقريبا يكون كل رأس ملكا ؟ (Palmer [1985]).
116- جد دالة احتمال العتبة للخاصية الآتية : نصف الأضلاع المحتملة على الٌل لبيان ما تكون موجودة. ما مقدار دقة العتبة ؟
117- ل p=1/n و ل ϵ>0 مثبتة، بين أن Gp كله تقريبا لا يملك فيها أكثر من (1+ϵ)n/2 رأسا. (مساعدة : بدلا من محاولة وضع حد للاحتمال مباشرة، بين أنه محدود لاحتمال لحادث آخر، و يؤول إلى 0).
118- حدد أصغر بيان بسيط مترابط بحيث لا يكون متوازرنا.
119- لتكن Q خاصية البيان الآتية : لكل اختيار لمجموعات رأسية منفصلة T,S حجمها c 1g n، يوجد ضلع نقاطه الطرفية في S و T. أثبت أنه إذا كان 2
120- أثبت أنه إذا كان k = l gn-(2+ϵ) lg lg n، فإن كل دوري ألعاب على n من الرؤوس تقريبا يملك الخاصية الآتية : كل مجموعة فيها k من الرؤوس تملك تابعا مشتركا.
121- يكون دوري الألعاب متعديا إذا امتلك ترتيبا رأسيا un، ... ، u1 بحيث ui→uj إذا و فقط إذا كان j>i. أثبت أن كل دوري ألعاب يملك دوري ألعاب جزئيا متعديا في 1 gn من الرؤوس. و أنه إذا كان c عددا ثابتا أكبر من 1، فإن كل دوري ألعاب تقريبا لا يملك دوري ألعاب جزئيا متعديا فيه أكثر من 21 gn+c رأسا.
122- أثبت أن الطول لأطول مسافة مجتازة في قائمة مكونة من n من الرؤوس و الذيول العشوائية هو (o(1)+1) Ign. بكلمات أخرى، ϵ<0، لا توجد قائمة تقريبا تملك على الأقل Ign (ϵ+1) شقلبات متطابقة متتالية، و كل قائمة تقريبا تملك على الأقل -1)ϵ1gn ( شقلبات متطابقة متتالية.
123- مع p=(1-ϵ) logn /n ، جد m كبيرة بحيث يكون كل بيان تقريبا يملك على الأقل m من الرؤوس المعزولة. ما (n)m التي تنتج من متباينة تشيبيجيف (Chebyshey'sInequality) ؟
124- بفحص جيران مشتركين ؛ أثبت أنه إذا كانت P مثبتة، و k=o(n/logn)، فإن Gp كله تقريبا يكون مترابطا من الدرجة k.
125- مع p=(1-ϵ) logn /n، كم يمكن أن تكون m كبيرة بحيث يملك كل بيان تقريبا على الأقل m من الرؤوس المعزولة ؟ (مساعدة : استخدم متبانية تشيبيجيف).
126- فترة-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]).
127- تفسير الفضاء الحلقي و فضاء الروابط. معطى بيان G، أثبت أن : a) الفرق التماثلي لبيانين جزئيين هو بيان جزئي زوجي. b) الفرق التماثلي لقطعين ضلعيين هو قطع ضلعي. c) كل قطع ضلعي يشترك مع كل بيان جزئي زوجي بعدد زوجي من الأضلاع.
128- تذكر أن الجوار المغلق لرأس v هو N(v) U {v} : a) لتكن S مجموعة رؤوس في بيان بسيط G بحيث إن جواراتها متطابقة أثبت أن إحدى القيم الذاتية ل G تكون مكرره على الأقل ǀSǀ-1 مرة. ما هي ؟ b) لتكن S مجموعة رؤوس في بيان بسيط G بحيث إن جواراتها المغلقة أثبت أن إحدى القيم الذاتية ل G تكون مكرره على الأقل ǀSǀ-1 مرة. ما هي ؟
129- معطى بيان G، و لتكن R(G) هي المصفوفة التي تكون مدخلتها i,j هي dg(vi,vj). أثبت أن بعد المكعب المسحوق لبيان ما (التعريف 12.4.8) يكون على الأقل العدد الأكبر لعدد القيم الذاتية الموجبة و عدد القيم الذاتية السالبة للمصفوفة R(G). استنتج أن بعد المكعب المسحوق للبيان Kn هو n-1. (مساعدة : أعد كتابة الشكل التربيعي xTRx بوصفه مجموعا لمربعات دوال خطية، و طبق قانون سلفستر للقصور الذاتي).
130- تكون المصفوفة محيدة كليا (totally unimodular) إذا كانت محددة كل مصفوفة جزئية مربعة موجودة في {0, 1,-1}. أثبت أن مصفوفة الوقوع لبيان بسيط تكون محيدة كليا إذا و فقط إذا كان البيان ثنائي الفرع. (تذكيز : مصفوف الوقوع لبيان بسيط تملك +1 مرتين في كل عمود).
131- ليكن G بيانا خاليا من المثلثات على n من الرؤوس، بحيث يكون لكل زوج من الرؤوس غير المتجاورة بالضبط جاران مشتركان. أثبت أن G منتظم، و أن n=1+1(2K+1)، حيث k هي درجة الرؤوس في G. أثبت أن G منتظم بقوة. ما القيود على k المتضمنة باستخدام شروط التكامل ؟ أنشئ أمثلة kϵ {1, 2, 5}. و هنالك تحقيق ل k=10 معروف باستخدام التصاميم التركيبية التوافقية).
132- أثبت أن بيان بيترسون منتظم بقوة، و حدد طيفه (يكون الطيف سهلا بوجود خصائص البيانات المنتظمة بقوة و ليس صعبا من غيرها). طبق الطيف لتبين أن أضلاع البيان K10 لا يمكن أت تجزأ إلى ثلاث نسخ منفصلة من بيان بيترسون. (مساعدة : استخدام الطيف لتبرهن أن نسختين من مصفوفة بيترسون تملكان متجها ذايتا مشتركا غير المتجه الثابت) (Schwenk [1983]).
133- ليكن F=G□H، حيث G و H بيانان بسيطان. أثبت أنه إذا كان كل رأسين غير متجاورين في F يملكان جارين مشتركين بالضبط، فإن G و H يكونان بيانين تامين.
134- التشاكلات الذاتية و القيم الذاتية : a) أثبت أن ƃ يكون تشاكلا ذاتيا ل G إذا و فقط إذا كانت مصفوفة التباديل المقابلة ل s إبدالية مع مصفوفة التجاور ل G ؛ بمعنى أن PA=AP. b) ليكن x متجها ذاتيا ل G للقيمة الذاتية التي عدد مرات تكرارها 1، و لتكن P مصفوفة التباديل للتشاكل الذاتي ل G. أثبت أن Px=±x. c) استنتج أنه عندما تكون كل قيمة ذاتية ل G مكررة مرة واحدة فقط، فإن كل تشاكل ذاتي ل G هو تبديلة عودة إلى الأصل (involution)، بمعنى أن مربع هذه التبديلة يعطي العنصر المحايد. (Mowshowitz.[1969], Petersdorf- Sachs [1969])
135- لتكن In، ...، I1 مصابيح ضوئية متحكما فيها من خلال المفاتيح sn، ....، s1. المفتاح i يغير حالة المصباح i إلى تشغيل / إغلاق و ربما مصابيح أخرى، و لن si يغير حالة Ij إذا و فقط إذا كان sj يغير حالة Ii، مبدئيا، أفترض أن المصابيح جميعها مغلقة. أثبت أنه يمكن تشغيل المصابيح جميعها. (Peled [1992]) (مساعدة : يستخدم هنا الفضاءات المتجهة، و ليس القيم الذاتية).
