دانلود با لینک مستقیم و پر سرعت .
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 23
فهرست مطالب
فصل اول
مقدمه: 2
آشنایی با گراف 2
یکریختی گراف ها: 3
ماتریس وقوع و ماتریس مجاورت: 3
درجه راس ها: 4
مسیرها : 4
دورها: 4
کاربردها: 5
فصل دوم
درخت ها: 7
یال های برشی و باندها: 8
فرمول کیلی: 9
مساله ارتباطی دهی: 9
همبندی: 10
ساخت شبکه‌های ارتباطی قابل اعتماد: 11
تورهای اویلری 12
دورهای همیلتنی: 12
الگوریتم فلوری: 13
فصل چهارم
تطابق‌ها: 14
تطابق ها و پوشش ها در گراف های دو بخشی: 15
تطابق کامل: 16
رنگ آمیزی یالی 16
قضیة ویزینگ: 17
فصل پنجم
پیوست 20
گراف های قابل توجه 21
منابع 23
نظریه های گراف و کاربرد آنها
فصل اول
مقدمه:
در دنیای اطراف ما، وضعیف های فراوانی وجود دارند که می توان توسط نموداری متشکل از یک مجموعه نقاط ، به علاوه خطوطی که برخی از این نقاط را به یکدیگر متصل می کنند، به توصیف آنها پرداخت، به عنوان مثال ، برای نشان دادن رابطه دوستی بین یک دسته از انسان ها می نوانیم هر شخص را با یک نقطه مشخص کنیم . نقاط متناظر با هر دو دوست را با یک خط به یکدیگر وصل نماییم، یا در جای دیگر ممکن است برای نشان دادن یک شبکه ارتباطی، از نموداری استفاده کنیم که در آن ، نقاط نمایانگر مراکز ارتباطی و خطوط، نشان دهنده پیوندهای ارتباطی بین مراکز باشند. توجه داشته باشید که در این گونه نمودارها، آن چه بیشتر مورد توجه است این است که آیا دو نقطه داده شده ، به وسیله یک خط به یکدیگر متصل هستند یا نه و طریقه اتصال آنها اهمیتی ندارد. تجربه ریاضی این وضعیت ها به مفهوم گراف منتهی می شود.
گراف G یک سه تایی مرتب است که تشکیل شده از یک مجموعه ناتهیV(G) از راس ها، یک مجموعه E(G) – مجزای از V(G) – از یال ها و یک تابع وقوع که به هر یال G ، یک زوج نا مرتب از راس های G را – که الزاماً متمایز نیستند – نسبت می دهد. اگر e یک یال وu و دو راس باشند به طوری که ، در این صورت گفته می شود که e، راس هایu و را به یکدیگر وصل کرده است و راس های u و ، دو سر یال e نامیده می شوند.
دلیل نامگذاری گراف ها بدین نام، این است که می توان آنها را به صورت گرافیکی نمایش داد و همین نمایش گرافیکی است که ما را در درک بسیاری از خواص گراف ها یاری می کند. در این گونه نمایش داده می شود.
آشنایی با گراف
نمودار یک گراف ، فقط رابطه وقوعی را که بین راس ها و یال ها برقرار است، نشان می دهد، با این حال در غالب اوقات ، نموداری از یک گراف را رسم کرده ، به جای خود گراف ، به نمودار آن اشاره می کنیم. به همین منوال نقطه های آن را «راس» و خطوط آن را «یال» می نامیم.
اگر یک گراف ، نموداری داشته باشد که در آن یال ها تنها در راس های دو سر خود متقاطع باشند، مسطح نامیده می شود، چون می توان به سادگی این گونه گراف ها را روی یک صفحه مسطح رسم کرد. دو راس که برروی یال مشترکی واقعند ، مجاور نامیده می شوند. به همین ترتیب دو یال واقع بر روی یک راس مشترک نیز مجاورند. یک یال با دو سر یکسان ، طوقه و یک یال با دو سر متمایز ، یال پیوندی نامیده‌می‌شود.
اگر مجموعه راس ها و مجموعه یال های یک گراف، متناهی باشند، گراف مزبور را متناهی می نامند. گرافی را که یک راس داشته باشد بدیهی و سایر گراف ها را غیر بدیهی می نامیم.
یک گراف ساده است، اگر هیچ طوقه ای نداشته باشد و بین هر دو راس آن ، بیش از یک یال نباشد . نمادهای را به ترتیب برای نشان دادن تعداد راس ها و تعداد یال های گراف G به کار می بریم.
یکریختی گراف ها:
دو گراف Gو H همسان اند(و نوشته می شود G=H) ، اگرE(G)=E(H),V(G)=V(H) . مسلماً اگر همسان باشند، می‌توان آنها را با نمودارهای یکسانی نمایش داد. به هر حال این امکان نیز وجو دارد که دو گراف نا همسان ، نمودارهای یکسانی داشته باشند. در حالت کلی ذو گراف GوH ، یکرخت نامیده می شوند (ونوشته می شود اگر نگارشت های دو سویی وجود داشته باشند، به طوری که داشته باشیم:اگر تنها اگر . این زوج از نگارشت ها، یک یکریختی بین GوH نامیده می شود.
از طرف دیگر گراف تهی، گرافی است که هیچ یالی نداشته باشد. گراف دو بخشی ، گرافی است که می توان مجموعه راس های آن را به دو زیرمجموعه XوY چنان افراز کرد که یک سر تمام یال های آن در X و سر دیگرآنها در Y باشد. گراف دوبخشی کامل، یک گراف دوبخشی با بخش های X وY است که در آن هر راس X ،به هر راس Y وصل شده باشد. اگر گراف دو بخشی کامل را با نمایش می دهیم.
ماتریس وقوع و ماتریس مجاورت:
متناظر با هر گراف G ، یک ماتریس وجود دارد که ماتریس وقوع G نامیده می‌شود. اگر راس های G را با و یال های آن را با نمایش دهیم، آنگاه ماتریس وقوع G ، ماتریسی مانند است که در آن برابر با تعداد دفعاتی است (0،1 یا2) که بر واقع شده است. در حقیقت ماتریس وقوع یک گراف ، طریقه دیگری یرای معین نمودن آن گراف است.
راه دیگر معین نمودن یک گراف ، استفاده از مارتیس مجاورت آن است که مارتیسی است مانند و در آن برابر تعداد یال هایی است که رابه وصل می کند.
زیر گراف :
می گوئیم گراف H، زیر گراف G است (نوشته می شود) ، اگر از محدود کردن به E(H) حاصل شده باشد. اگر ولی داشته باشیم می نویسم و می گوئیم H یک زیر گراف سره از G است. اگر H یک زیر گراف G باشد، درآن صورت G را یک زبرگراف H می نامیم. در صورتی که زیر گراف (یا زبرگراف) H از G در شرط V(H)=V(G) صدق کند، آن را یک زیرگراف فراگیر(یا زبرگراف فراگیر) از G خواهیم نامید.
اگر در یک گراف تمام طوقه ها را حذف کنیم و همچنین از بین هر دو راس مجاور، تمام یال های پیوندی به جز یکی را حذف نماییم ، به زیر گراف فراگیر ساده‌ای از G می رسیم که گراف ساده زمینهG نامیده می شود.
فرض کنید ، یک زیر مجموعه ناتهی از V باشد. زیر گرافی از G که مجموعه راس های آن و مجموعه یال هایش برابر مجموعه یال هایی از Gباشد که هر دو سر آنها در واقع است، زیر گراف القاء شده توسط نامیده شده، با نمایش داده می‌شود. همچنین می گوئیم یک زیر گراف القاییG می باشد. زیر گراف القایی که با نمایش داده می شود، زیر گرافی است که با حذف راس های و یال های واقع بر آنها، از G به دست می آید. اگر به جای می نویسیم .
فرض کنید کهیک مجموعه ناتهی از E باشد. زیر گرافی از G که مجموعه راس های آن ، برابر مجموعه راس های دو سریال هایباشد، زیر گراف القاء شده توسط نامیده شده ، با نمایش داده می شود. همچنین می گوئیم یک زیرگراف القایی یالی G می باشد. زیر گراف فراگیری از G که مجموعه یال های آن باشد ، به طور ساده به صورت نوشته می شود و می توان آن را با حذف یال های از به دست آورد. به طور مشابه گرافی که با افزودن مجموعه یال های به به دست می آید، با نمایش داده می شود. اگر به جای و می نویسیم و.
درجه راس ها:
درجه راس در گراف ، برابر تعداد یال های واقع بر می باشد. در این تعریف ،هر طوقه به عنوان دو یال شمرده می شود.
کمترین و بیشترین درجه راس های G را به ترتیب با نمایش می دهیم.
اثبات:
ماتریس وقوع M را در نظر بگیرند. مجموع داریه های سطر متناظر با راس دقیقاً برابر است و بنابراین برابر مجموع تمام داریه های M می باشد که این جمع برابر است.
مسیرها :
یک گشت از G دنباله نا صفر متناهی است به طوری که جملات آن یک درمیان از راس ها ویال ها بوده و به ازای دو سر باشند. در این صورت می گوئیم w ، یک گشت از تا یا به عبارتی دیگر یک گشت است. راس های به ترتیب ابتدا و انتهای w و راس های داخلی آن نامیده می شود. همچنین عدد صحیح k را طول w می نامیم.
اگر دوگشت باشند ، گشت را که از به هم پیوستن در راس به دست می آید با نمایش می دهیم. یک قسمت از گشت ، گشتی است مانند ، که زیر دنباله ای از جملات متوالی wمی باشد و این زیر دنباله را - قسمت w می نامیم.
اگر یال های در گذشت w متمایز باشند، w یک گذرگاه نامیده می شود. در این حالت ، طول w برابر با می باشد. اگر علاوه بر یال ها ، راس های نیز متمایز باشند ، wیک مسیر نامیده می شود.
می گوئیم دو راس uو از G همبند یا متصلند، اگر یک (,u ( مسیر در G وجود داشته باشد . همبندی یک رابطه هم ارزی روی مجموعه راس های V تشکیل میدهد. بنابراین افرازی از V به زیر مجموعه های ناتهی وجود دارد که در آن دو راس u و همبندند اگر و تنها اگر u و هر دو متعلق به مجموعه یکسانی باشند.
زیر گراف های مولفه های G نامیده می شود. اگر گراف G دقیقاً یک مولفه داشته باشد ، همبند است و در غیر این صورت ناهمبند خواهد بود. تعداد مولفه های G را با نمایش می دهیم.
دورها:
می گوئیم یک گشت ، بسته است ، اگر طول آن مثبت بوده ابتدا و انتهای آن یکسان باشند. یک گذرگاه بسته که ابتدا و راس های داخلی آن متمایز باشند، دور نامیده می‌شود. همانند مسیرها، گاهی اوقات لفظ «دور» را به منظور اشاره به گرافی که متناظر با یک دور است به کار می بریم ، یک دور با طول kراk- دور می نامیم.
یک k- دور بسته به اینکهk زوج یا فرد باشد ، یک دور زوج یا فرد می نامیم. غالباً به 3- دور ، مثلث گفته می شود.
یک گراف ، دو بخشی است اگر و تنها اگر هیچ دور فردی نداشته باشد.
