۰۳ شهریور ۱۳۹۸

نظریه گراف و کاربردها

دانشکده / گروه دانشکده ریاضیات و علوم کامپیوتر/ گروه ریاضیات و کاربردها
رشته تحصیلی ریاضی
عنوان و کد درس نظریه گراف و کاربردها- 454401
تعداد واحد و نوع 3 (نظری)
پیش نیاز درس مبانی ترکیبیات
ترم تحصیلی نیمسال دوم سال تحصیلی 95-96
 

نام استاد: دکتر سمیه بندری

شماره اتاق: اتاق اساتید طبقه اول ساختمان شهید احمدی روشن

شماره تماس: -

آدرس ایمیل:somayeh.bandari@yahoo.com

 

خلاصه درس: در اين درس ضمن آشنايي با مفاهيم پايه اي نظريه گراف و همچنين قضاياي اصلي و ابتدايي در اين نظريه، به برخي كاربردهاي مهم نيز پرداخته می شود و ارتباط اين نظريه با شاخه هاي ديگر علوم رياضي و علوم مهندسي مورد تأكيد قرار مي گيرد.

 

اهداف یادگیری درس:
LO1: تعریف گراف و معرفی انواع آن
LO2: تشریح مفهوم رنگ آمیزی گرافها
LO3: تعریف درختها ، جنگلها و درختهای گسترنده و بیان قضایایی از آنها
LO4: تشریح مفهوم بهینه سازی در نظریه گراف و بیان چند الگوریتم کاریردی
LO5: تعریف شبکه حمل و نقل  و شارشها و بیان نحوه بدست آوردن شارش ماکسیمم
LO6:تشریح مفهوم تطابق و بیان ارتباط آن با  شبکه ها

 

ماتریس همپوشانی اهداف یادگیری و حیطه یادگیری(LO->H3)

اهداف یادگیری درس

درکی ، شناختی

(Cognitive)

طراحانه و خلاقانه

(Psychomotor)

مدیریتی و عاطفی

(Affective)

LO1 2    
LO2 3    
LO3 3    
LO4 3    
LO5 3    
LO6 3    

نکته:  1=کم   2= متوسط   3= زیاد

 

روش تدریس و یادگیری:

 

 - این درس با کمک حل تمرین‌ هایی که از دانشجویان گرفته می‌شود ارائه می‌گردد.

 - استفاده از پایگاه مدیریت یادگیری  Schoology

 

برنامه  زمانی هفتگی کلاس:

 

 شنبه 8-10 کلاس  426

 شنبه هفته های زوج 10-12  کلاس  426     

ساعت مشاوره هفتگی و محل:  یکشنبه‌ها 10-12 در اتاق اساتید طبقه اول ساختمان شهید احمدی روشن

 

برنامه هفتگی:

هفته موضوع جلسه تعداد ساعات تدریس
1-6

مقدمه ای بر نظریه گراف

تعریف گراف-  مسیر- تور گشت- دور

ماتریسهای وقوع و مجاورت

گرافهای همبند

زیرگرافها- حذف راس و یال از گرافها

 معرفی انواع گرافها  (منظم-کامل- دوبخشی ...)

مکمل گرافها- حاصل ضربهای گرافها- یکریختی  گرافها

گرافهای جهت دار

 مدارهای اویلری و همیلتونی

گرافهای مسطح-  قضیه کوراتوفسکی

16

6

7

8

رنگ آمیزی گرافها

رنگ آمیزی یالها- قضیه وایزینگ

رنگ آمیزی راسها- قضیه بروکس

چند جمله ایهای رنگی

6

8

9

درختها

تعریف درخت و جنگل

درخت گسترنده

4

10

11

12

بهینه سازی

گرافهای وزندار

الگوریتم کوتاهترین مسیر

یافتن درخت گسترنده مینیمال (الگوریتم کروسکال و پریم)

8

13

14

شبکه

شارها و برشها

قضیه شارش ماکسیمم - برش مینیمم

قضیه منگر

6

15

16

تطابق

تطابق در گرافها

تطابق ماکسیمم

ارتباط تطابق ماکسیم - برش مینیمم
6

سیستم ارزشیابی:

متد ارزشیابی وزن المان ارزشیابی (%) شماره هفته برگزاری
تکلیف فردی(فصل های اول، دوم) 5%

هفته 3 شروع

هفته 9 تحویل

تکلیف فردی(فصل های سوم و چهارم) 2.5%

هفته 9 شروع

هفته 13 تحویل
امتحان میان ترم (فصلهای اول، دوم، سوم و چهارم) 30%

هفته 13

تکلیف فردی (فصل های پنجم و ششم) 2.5%

هفته  13 شروع

هفته 16 تحویل
امتحان پایان ترم(تمام سر فصل ها) 60%  

ماتریس همپوشانی ارزشیابی و اهداف یادگیری:

متد ارزشیابی LO1 LO2 LO3 LO4 LO5 LO6
تکلیف فردی * *        
تکلیف فردی     * *    
امتحان میان ترم * * * *    
تکلیف فردی         * *
امتحان پایان ترم * * * * * *

 

مراجع اصلی:

نظریه گراف و کاربردهای آن- باندی، مورتی

Graph Theory with Applications, J. A. Bond, U. S. R. Murty, north-Hooland, 1976.

مراجع فرعی:

ریاضیات گسسته و ترکیبیاتی جلد 3، گریمالدی

Discrete and combinatorial mathematics, Ralph P. Grimaldi

 

قوانین در صورت تاخیر تکالیف تحویلی و شرایط اعطاء وقت اضافه:

1- دانشجویان می بایست تکالیف و گزارش ها را در زمان مقرر بصورت فایل نرم softcopy  در پایگاه Schoology درس بفرستد و گزارش پرنیت شده hardcopy را مستقیما" به استاد درس تحویل دهد.

2- هرگونه دیرکرد در تحویل گزارش و یا پروژه چه softcopy  ویا  hardcopy مشمول خسارت خواهد شد و به ازای هر روز دیرکرد 20% از نمره احتسابی شما برای آن المان ارزشیابی کسر خواهد شد.

قوانین برخورد با سرقت ادبی :

1-  درصورت مشاهده هر یک از مصادیق تقلب در آیتم های ارزشیابی، نمره شما صفر منظور گردیده و از شرکت شما در امتحان پایان ترم ممانعت خواهد شد.

2-  سرقت علمی باعث مخدوش شدن چهره علمی و نابودی حیثیت دانشگاه  می شود و خسارتی بی جبران را برای جامعه علمی کشور در پی خواهد داشت. لذا مرکز آموزش عالی فنی و مهندسی بوئین زهرا با هر گونه مصادیق سرقت علمی  ( در سایت دانشگاه اعلام شده است)  به شدت برخورد خواهد کرد. در صورت کشف چنین جرایمی نمره دانشجو در هر مرحله از تحصیل  به صفر تغییر یافته و پرونده آموزشی دانشجو معلق و جهت اتخاذ تصمیماتی شدیدتر به کمیته انضباطی دانشگاه ارجاع می گردد.