عبير حميدى جباره الحربى

434 math

Introduction to combinatorics and graph theory

المدخل لنظرية الرسومات والتراكيب

434M Introduction to Graphs and Combinatorics 4(3+1) credit-hours

Basic concepts(syllabus): Eulerian graphs. Hamiltonian graphs. Planar graphs. Coloring. Minimal spanning trees. Orientation of graphs. Matching. Ordered sets. Dilworth's theorem. Applications. Permutations and combinations. Inclusion-exclusion. Recurrence relations. Generating functions. Analyzing algorithms and problems. Sorting. Algorithms in graphs and digraphs.

الوحدات الدراسية:      4(  3+1)

متطلب سابق:      242 ريض           يعطى لطلاب المستوى الثامن لتخصص رياضيات

وصف المقرر ومحتوياته الأساسية:

الرسوم الاويليرية الرسوم الهاملتونية الرسوم المستوية التلوين الأشجار المولدة الاصغرية توجيه الرسوم تطبيقات التباديل والتوافيق مبدأ التضمين والإقصاء العلاقات الارتدادية الدوال المولدة تحليل الخوارزميات في الرسوم الموجهة مسائل الفرز

Course Description(syllabus):

- Inclusion-exclusion principle Recurrence relations Generating functions permutation combination (5 weeks), first midterm in chapter (1-4). 

- Euler graphs Hamiltonian graphs Planar graphs Coloring spanning trees Orientation of graphs Matching analyzing algorithms and problem sorting algorithms in graphs and digraphs (9 weeks),second midterm in chapters (6-7).

- Final exam in chapters (1-8). 

طرق التدريس المقترحة: 

1- يدرس أولا المواضيع الخاصة بالتراكيب والتوافيق والدوال المولدة والعلاقات الارتدادية وهي الأربع أبواب الأولى في الكتاب ويختبر الطالب فيها كاختبار فصلي أول(5 اسابيع)

 2- ثم يدرس الجزء الثاني من المنهج وهو الخاص بالرسومات والأشجار(الباب السادس والسابع) ويختبر في هذه المواضيع الطالب الامتحان الفصلي الثاني.(9 اسابيع)

3-  يكون الامتحان النهائي شاملا لكل المنهج (من الأول إلى الثامن)

عدد الاختبارات الفصلية  :2  من    40 درجة

10      درجات للتمارين تقسم بين امتحان قصير (Quiz)و واجب منزلي(Assignment)

 50     درجة  للامتحان النهائي

الكتاب المقرر:                                                                Text book

Discrete Mathematics Applied combinatorics and Graph theory

 by M.Townsend

Benjamin Cummings Publishing Company Inc

المراجع :                                                                                           

1-Introductory Combinatorics

by  K. P. Bogart

Harcourt Brace Jovanovich Academic Press.

2-Introductory Combinatorics

by  R. Brualdi

 North Holland

3-Discrete Mathematics

 by  N. Biggs

Oxford University Press

Important links :

 graph theory tutorials