توضیحات

مقاله در مورد گراف

واژه گراف، نه تنها در ریاضیات، بلکه در سایر علوم و حتی در زندگی روزانه به نام های گوناگون مانند طرح دیاگرام،

نگاره، نقشه، ماز و… بکار می رود. مثلا ممکن است به بهانه های مختلف شکلی رسم کنیم که از نقطه هایی

تشکیل شده باشد و اگر چند نقطه، رابطه هایی با هم داشته باشند این روابط را با کشیدن خط بین آن ها نشان

دهیم. نیز می توانیم تیم های ورزشی را در نظر بگیریم و آن ها را با نقاط A,B,C,… روی صفحه رسم کنیم و خطوط

را با این شرط وصل کنیم که آن تیم ها با هم بازی داشته باشند، در ابتدا که بازی صورت نگرفته فقط چند نقطه

داریم، ولی وقتی تیم ها باهم بازی کردند، بین تمام نقاط خط هایی وصل کنیم، بدین ترتیب یک گراف ساخته ایم،

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

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

قابل ذکر است که اگر نقاط را رئوس گراف و خطوط را یال بنامیم داریم: G(V.E) که آن را گراف G با رئوس V. و یال های E می نامیم.

۷۸ صفحه فایل ورد (Word) فونت ۱۴ منابع دارد همراه با عکس و توضیحات

پس از پرداخت آنلاین میتوانید فایل کامل این پروژه را دانلود کنید

اکنون به معرفی چند نوع گراف می پردازیم:

۱) گراف های یکریخت: اگر در دو گراف، تعداد راس ها برابر بوده، بطوریکه هر دو راس متناظر، با یک حرف

نام گذاری شده باشد، آن گاه وقتی دو راس بوسیله ی یالی بهم مربوط باشند، راس های هم نام آن ها در گراف دوم نیز بوسیله ی یالی بهم مربوط شوند.
۲) گراف همبند و ناهمبند: اگر از هر دو راس دلخواه گراف، بتوان با حرکت روی یال ها، به راس دلخواه دیگر رسید، چنین گرافی همبند و در غیر این صورت ناهمبند است، یعنی گراف همبند از یک قطعه و ناهمبند از چند قطعه تشکیل می شود.

مرتبه، اندازه و درجه گراف:

به تعداد رئوس هر گراف مرتبه و به تعداد یالهای آن، اندازه و تعداد یال های منتهی به یک راس را درجه ی آن گراف گوییم.
بدیهی است که در گراف صفر درجه، هر راس برابر صفر است و در گراف کامل با n راس درجه، هر راس برابر با n-1 خواهد بود.

راس هایی که درجه زوج دارند راس های زوج و راس هایی که درجه فرد دارند راس های فرد، نامیده می شوند. مساله حایز اهمیت این است که در هر گراف، تعداد رئوس فرد، زوج هستند، یعنی نمی توان گرافی رسم کرد که مثلا: ۳ تا راس فرد داشته باشد. بعنوان مثال نمی توان گرافی رسم کرد که درجه راس های آن ۵،۰،۲،۲،۵،۸،۷،۶ باشد زیرا تعداد رئوس فرد ۳ تا هستند یعنی(۵،۷،۵(!

رنگ‌آمیزی گراف :     

…………………………………………………..

…………………………

در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص مساله‌های برچسب‌گذاری گرافاست.

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

رنگامیزی گراف کاربردهای زیادی در زمینه‌های عملی و تئوری گوناگون دارد.

علاوه بر مساله‌های کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیت‌های مختلفی روی نوع گرافها، روی روش رنگامیزی و حتی تعداد و رنگ عناصر گراف مساله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. با وجود اینکه این مساله از نظر علمی هنوز در حال رشد و بررسی بیشتر می‌باشد، با ظهور جدول سودوکو در بین عموم م…………………………..

در نظریه گراف، رنگ‌آمیزی کامل گراف یک نوع از رنگ‌آمیزی یالها و راسهای گراف می‌باشد. اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه‌است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند.

عدد رنگی کامل (χ(G یک گراف حداقل تعداد رنگهای لازم برای رنگ آمیزی کامل یک گراف G است

. گراف کامل T = T(G) گراف G یک گراف است با این شرایط : اولاً اینکه مجموعهٔ رئوس T متناظر باشند با رئوس و یالهای G و دوماً اینکه دو راس در T مجاورند اگر و فقط اگر عناصر متناظر آنها در G یا مجاور باشند و یا متلاقی.

رنگ آمیزی یالیk : رنگ امیزی یالی ϐاز گراف بدون طوقه G تخصیص k رنگ ۳,۲,۱,…k به یالهای G است.

رنگ امیزی سره: رنگ امیزی ϐ سره است اگر هیچ دو یال مجاور همرنگ نباشند.

متقابلا K-رنگ امیزی یالی را می توان به صورت یک افراز (E1,E2,…,Ek) از E تصور کرد، که در ان Ei زیرمجموعه ای

( احتمالا خالی ) از E را نشان می دهد که رنگ i را اختیار کرده است. پس k-رنگ امیزی یالی سره، k-رنگ امیزی یالی ( E1, E2, …,Ek) است ک………………………..