پاورپوینت گراف ها

توضیحات محصول

دانلود پاورپوینت گراف ها با فرمت ppt و در 34 اسلاید قابل ویرایش

قسمتی از متن پاورپوینت گراف ها

اهداف

§آشنايي با گراف

§ماتريس مجاورتي

§جستجوي گراف

§شبکه ها

هر گراف G شامل دو مجموعه V وE است :

V : مجموعه محدود و غيرتهي از رئوس است

E : مجموعه اي محدود و احتمالا غيرتهي از لبه ها مي باشد.

V(G) و E(G) : مجموعه رئوس و لبه هاي گراف G را نمايش مي دهند.

براي نمايش گراف هم مي توانيم بنويسيم G=(V ، E)

§براي گراف بدون جهت ، لبه ها به صورت خطوط يا منحني نمايش داده مي شوند.

§ براي گراف هاي جهت دار لبه ها به صورت فلش هايي که از انتها به ابتدا رسم شده است ، ارايه مي گردند.

1-6 محدوديت هاي گراف ها

§محدوديت هاي زير بر روي گراف ها اعمال مي شود :

§ يک گراف فاقد لبه اي از يک راس مانندi ، به خودش مي باشد. اين مطلب بدين معني است که لبه غير معتبر مي باشد.

§ يک گراف فاقد رويداد چندگانه از يک لبه مي باشد.

گراف کامل : گراف کامل گرافي است که داراي حداکثر تعداد لبه باشد.

§ طول يک مسير تعداد لبه هاي موجود در آن است.

§ مسير ساده ، مسيري است که همه رئوس آن به جز اولي و آخري مجزا باشند.

§ حلقه يا سيکل ، يک مسيرساده است که اولين و آخرين راس آن يکي باشد.

براي مثال 0،1،2،0 يک حلقه در است.

در گراف بدون جهت مانند G ، دو راسورا متصل مي گويند، اگر مسيري در G ازبهوجود داشته باشد.

يک گراف بدون جهت را متصل مي ناميم اگر براي هر زوج راس در V(G) ،مسيري از به در G وجود داشته باشد.

يک مولفه اتصال يا به طور ساده تر يک مولفه ، در گراف بدون جهت ، بزرگترين زيرگراف متصل آن است.

يک گراف جهت دار کاملا متصل ناميده مي شود ، اگر براي هر زوج از رئوس در V(G) ، مسيري جهت دار از به و همچنين از به وجود داشته باشد.

يک مولفه کاملا متصل ، بزرگترين زيرگرافي است که کاملا متصل باشد.

§ درجه يک راس تعداد لبه هاي متلاقي با آن راس است .

اگر در گراف G با n راس ، درجه راس i و e تعداد لبه ها باشد ، به آساني مي توان ديد که تعداد لبه ها برابر است با :