29 دانلود پروژه: بررسی انواع نظریه های گراف و کاربرد آنها و تطابق ها و درخت ها

فرمت فایل: ورد – Word و قابل ویرایش

تعداد صفحات: 50

فهرست مطالب

فصل اول

مقدمه: 3

آشنایی با گراف 5

یکریختی گراف ها: 5

ماتریس وقوع و ماتریس مجاورت: 6

درجه راس ها: 8

مسیرها : 8

دورها: 10

کاربردها: 11

فصل دوم

درخت ها: 16

یال های برشی و باندها: 18

فرمول کیلی: 19

مساله ارتباطی دهی: 20

همبندی: 22

ساخت شبکه‌های ارتباطی قابل اعتماد: 24

تورهای اویلری 26

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

الگوریتم فلوری: 29

فصل چهارم

تطابق‌ها: 33

تطابق ها و پوشش ها در گراف های دو بخشی: 34

تطابق کامل: 36

رنگ آمیزی یالی 36

قضیة ویزینگ: 38

فصل پنجم

پیوست 45

گراف های قابل توجه 46

منابع 50

فصل اول

مقدمه:

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

گراف G یک سه تایی مرتب است که تشکیل شده از یک مجموعه ناتهیV(G) از راس ها، یک مجموعه E(G) – مجزای از V(G) – از یال ها و یک تابع وقوع که به هر یال G ، یک زوج نا مرتب از راس های G را – که الزاماً متمایز نیستند – نسبت می دهد. اگر e یک یال وu و دو راس باشند به طوری که ، در این صورت گفته می شود که e، راس هایu و را به یکدیگر وصل کرده است و راس های u و ، دو سر یال e نامیده می شوند.

دلیل نامگذاری گراف ها بدین نام، این است که می توان آنها را به صورت گرافیکی نمایش داد و همین نمایش گرافیکی است که ما را در درک بسیاری از خواص گراف ها یاری می کند. در این گونه نمایش داده می شود.

آشنایی با گراف

نمودار یک گراف ، فقط رابطه وقوعی را که بین راس ها و یال ها برقرار است، نشان می دهد، با این حال در غالب اوقات ، نموداری از یک گراف را رسم کرده ، به جای خود گراف ، به نمودار آن اشاره می کنیم. به همین منوال نقطه های آن را «راس» و خطوط آن را «یال» می نامیم.

اگر یک گراف ، نموداری داشته باشد که در آن یال ها تنها در راس های دو سر خود متقاطع باشند، مسطح نامیده می شود، چون می توان به سادگی این گونه گراف ها را روی یک صفحه مسطح رسم کرد. دو راس که برروی یال مشترکی واقعند ، مجاور نامیده می شوند. به همین ترتیب دو یال واقع بر روی یک راس مشترک نیز مجاورند. یک یال با دو سر یکسان ، طوقه و یک یال با دو سر متمایز ، یال پیوندی نامیده‌می‌شود.

دانلود فایل >>>

سایر محصولات :
29 دانلود پروژه: بررسی انواع نظریه های گراف و کاربرد آنها و تطابق ها و درخت ها

29 دانلود پروژه: بررسی انواع نظریه...

پاورپوینت آبخیز و آبخیزداری

پاورپوینت آبخیز و آبخیزداری...

تحقیق جامع و کامل در مورد زلزله 97 ص

تحقیق جامع و...

28 _ دانلود پروژه جزوه پاورپوینت مبانی کامپیوتر و برنامه سازی

28 _ دانلود...

تحقیق در مورد زعفران قاینات 50 ص

تحقیق در مورد زعفران قاینات 50...

تحقیق در مورد زبان شناسی و گفتگو 50ص