گراف: يك گراف ، سـه تايي مرتب مي باشد كه شامل يك مجموعه غيرتهي از رئوس، يك مجموعه (متمايز از ) از يالها و يك تابع وقوع كه به هر ضلع يك زوج نامرتب (نه لزوما متمايز) از رئوس اختصاص مي دهد. در مباحث پيشرفته نظريه گراف مبحث گرافهاي جهت دار مطرح مي شود كه در آن تابع تعريف شده فوق به هر ضلع يك زوج مرتب ( نه لزوما متمايز) از رئوس اختصاص مي دهد.
پس از ترسيم نمودارگراف، سوالي كه در بينمتخصصين اين رشته مورد سوال قرارگرفت،
چگونگي رنگ آميـزي رئـوس گراف بـود بـه گـونه اي كه هيچ دورنگي مجاورنباشد.
اين سوال تا آنجايي خاص شدكه حداقل رنگ مورد نياز براي رنگ آميزي گراف چقدر است. موضوع مورد بحث در اين مقاله، پاسخ به همين سوال است كه تحت يك قضيه به اوج خود مي رسد. قبل از بيان اين قضيه بايد پارهاي تعارف و اصطلاحات را بياموزيم تا درك قضيه آسانتر شود در طي اين راه قضايايي نيز بيان و ثابت مي شود.
گراف متناهي: اگر و متناهي باشند گراف را متناهي ناميم؛ در غير اين صورت گراف نامتناهي است.
قابل به ذكر است موضوع مورد بحث در اين مقاله پيرامون گرافهاي متناهي است.
گرافهاي مسطح: گراف را مسطح گوييم اگر يالهاي آن فقط در رئوس، يكديگر را قطع كنند، يعني يالهاي گراف از روي يكديگر عبور نكنند.
گراف ساده: گراف ساده است اگر داراي حلقه (اتصال يك راس به خودش) و يالهاي موازي (يالهايي كه هر يك زوج راس يكساني را بهم وصل مي كنند) نباشد.
قرارداد: قرارداد مي كـنـيم و كـه تعداد رئـوس و تعداد يالهاست كه به اختصار به و نمايش مي دهيم.
زيرگراف: زيرگراف است اگر و و تحديد به باشد و مي نويسيم است.
زيرگراف پديد آرنده: زيرگراف از با و مي باشد.
زيرگراف القاء شده رأسي: فرض كنيد، زير مجموعه غيرتهي از باشد، زيرگرافي از كه مجموعه رئوسآن ومجموعه يالهايآن مجموعه يالهايي از است كه انتهاي
آن در است، زيرگراف القاء شده توسط گوئيم و به نمايش دهيم.زيرگراف
القاء شده توسط زيرگرافي استاز كه بوسيله حذف رئوس واقع در همراه با يالهاي مجاور آن بدست آمده باشد، كه با نمايش مي دهيم. اگر تنها راس حذف شود با نمايش دهيم.
زيرگراف القاء شده يالي: اگر زير مجموعه غيرتهي از باشد زيـرگراف القاء شده يالي ، زيرگرافي از است كه مجموعه يالهاي آن و مجموعه راسهاي آن، راسهاي دو انتهاي يالهاي موجود در باشد؛ اين زيرگراف را با نمايش دهيم.
زيرگراف القاء شده يالي به وسيله را به نمايش دهيم و زيرگرافي است حاصل از حذف يالهاي موجود در ؛ و زيرگراف القاء شده يالي به وسيله را به نمايش دهيم و زيرگرافي است حاصل از افزودن يالهاي موجود در به گراف . اگر تنها يك يال از گراف حذف يا به آن اضافه كنيم به ترتيب به و نمايش دهيم.
درجه رئوس: درجه راس از گراف كه با نمايش مي دهيم عبارت است از تعداد يالهايي از كه به منتهي مي شوند.
ماكسيمم و مينيمم درجه هاي هر گراف را بترتيب به و نمايش مي دهيم.
ماتريس وقوع : براي هرگراف يك ماتريس موجود است كه به نمايش دهيم كه تعداد دفعاتي استكه روي قرار ميگيرد.
قضيه 1: مجموعه درجه هاي هرگراف برابر استيعني .
برهان: ماتريس وقوع گراف را مي ناميم. مجموعه درايه هاي سطر متناظر بـه
برابر اسـت با . بنابراين دقيقـا بـرابـر مجمـوع كلـيه درايههاي
مي باشد و اين مجموعه برابر است با زيرا تمام ستونهاي داراي مجموع 2 است.*
راه: يك راه در دنباله متناهي و غيرتهي است كه جملات به ترتيب رئوس و يالها مي باشد به طوريكه براي هر ؛ يالي بين و است در اين صورت گوئـيم راهـي از به است يا يك - راه است. راه را به اختصار به نيز نمايش دهند.
جاده: راه جاده است اگـر براي ؛ ها متمايز باشند.
مسير: جاده اي است كه در آن رئوس متمايز باشند.
دور: جادة بسته اي است كه رئوس ابتدا و انتها با هم برابرند ولي رئوس داخلي آن متمايز از هم اند.
جاده اويلري: جاده اي كه كليه يالهاي گراف را بپيمايد را جاده اويلري ناميم.
مسير هاميلتوني: مسيري كه شامل همه رئوس باشد يك مسير هاميلتوني است.
دور هاميلتوني: دوري است كه شامل همه رئوس باشد
رئوس همبند: دو راس و را از همبند گوئيم اگــــر يـك - مسير در موجود باشد.
ناحيه گراف: در گراف مسطح قسمتهايي از سطح مسطح كه توسط نقاط و يالهاي گراف مشخص و متمايز شده است را ناحيه هاي گوئيم؛ تعداد نواحي را به
نمايش مي دهيم.
ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
* براي كسب اطلاعات بيشتر به منبع]1 [ داده شده در پيوست رجوع كنيد.
قضيه 2 (فرمول اويلر): فرض كنيد مسطح و همبند باشد همواره داريم؛ (كه تعداد نواحي است)*.
گـراف دوگــان: گـراف مسطـح را در نظر مي گيريم. متناظر هر ناحيه ازگراف ؛
راسي از است و متـناظر هـر يال در گراف ؛ يالي در است.
دو راس و به وسيلــــة يال به هم متصلند اگر و تنها اگر نواحي و در به وسيـلــه يال از هـم جـدا شده باشد.مجمـوعه نواحي را در گراف مسطح به نمايش مي دهيم.
خم ژوردان: يك خم ژوردان يا كمان ژوردان در صفحه يك خم پيوسته است كه خودش را قطع نمي كند، و يك خم بستة ژوردان، خمي است كه نقاط انتهايي آن بر هم منطبق هستند.بعداً از يك صورت، قضيه مشهور خم ژوردان استفاده مي كنيم كه مي گويد: اگر يك خم بستة ژوردان در صفحه باشد، و و دو نقطــــهمتمايز از باشند، آنگاه هر خـم ژوردان كه و را به هم وصل مي كند يا كاملاًداخل قرار دارد( به استثناي نقاط و ) يا كاملاً در بيرون قرار خواهد گرفت( با همان استثناء ) و يا را در نقاطي بجز و خواهد بريد.
قضيه 3 :اگر گراف سادهو مسطحباشد بهطوريكه آنگاه.
برهان: بدون از دست دادن كليت فرض كنيم گراف همبند است.
ــــــــــــــــــــــــــــــــــــــــــــــــــ
* اين قضيه در اينجا اثبات نمي شود، براي كسب اطلاعات بيشتر به كتابهاي معرفي شده در پيوست
3 مراجعه نمائيد.
با توجه به فرض مطلب زير بطور مستقيم نتيجه مي شود: .
(براي )
همچنين داريم:
با استفاده از قضيه 1 داريم: لذا .
از طرفي بنا به قضيه 2 (فرمول اويلر) داريم :
قضيه 4 : براي هر گراف ساده مسطح داريم : .
برهان : براي و بديهي است .
براي حكم را ثابت مي كنيم.
مي دانيم : . حال با گرفتن سيكما از طرفين نامساوي داريم:
از اين قضيه اين مطلب استنباط ميشود كه هر گراف ساده مسطح داراي راسي است
كه درجه آن حداكثرپنج است.
رنگ آميزي راسي : تخصيص رنگ 1 و 2 و… و به رئوس را رنگ ـ آميزي راسي ناميم.
رنگ آميزي سره :رنگ آميزي سره است اگر هيچ دو راس مجاور متمايز داراي يك رنگ نباشد . لذا رنگ آميزي راسي سره گراف بدون حلقه ،افراز از به مجموعه(احتمالا تهي) مستقل است.
گوئيم ، رنگپذير راسياست اگر داراي رنگآميزي ر نگ راسي سره باشد.از
اين پس رنگ آميزي راسي سره را به اختصار رنگ آميزي و رنگ پذير راسي سره را رنگ آميزي ناميم.به طور مشابه، رنگ پذير راسي را به اختصار ، رنگ پذير مي خوانيم.به وضوح گراف ، رنگ پذير است اگر و تنها اگر گراف ساده زمينه آن، نگ پذير باشد.
عدد فامي : ي مـربوط به ، مينيـمـم يي است كه برايآن ، رنگ ـ پذيراست؛ در اين صورت را فام ناميم.
وقتي با رنگ آميزي سروكار داريم، مطالعة ويژگيهاي رده خاصي از گرافهاي كه گرافهاي بحراني ناميده مي شوند، بسيار مفيد است.
گراف بحراني : گراف بحراني است اگر براي هر زير گراف اكيد از داشته باشيم .
گراف بحراني : به گراف رنگ و بحراني گوئيم ؛ قابل به ذكر اينكه هر گراف رنگ داراي زير گراف بحراني است.
قضيه 5: اگر ، بحراني باشد؛ .
برهان: ( فرض خلف) فرض كنيم گراف مفروض با باشد و فرض كنيم؛ يك راس از درجه در باشد.
از آنجايي كه ؛ بحراني است؛ ، رنگ پذير است.
فرض كنيم يك رنگ آميزي براي باشد بنا به تعريف، ؛ راس مجاور دارد كه است. و بنابراين بايد نامجاور به هر راس در باشد. اما در اين صورت يك رنگ آميزي براي است كه اين تناقض است.
با توجه به آنچه گفته شد، حال وقت آن است كه ثابت كنيم هر گراف مسطح ،
با حداقل شش رنگ قابل رنگ آميزي است.(به قضيه زير توجه كنيد)
قضيه 6 رنگ: هر گراف مسطح 6 رنگ پذير است.
برهان: قضيه را به روش استقرا روي تعداد رئوس ثابت مي كنيم، حكم براي گرافهايي كه تعداد رئوسشان كمتر از 7 است بديهي است. حال فرض مي كنيم يك گراف مسطح راسي است و تمام گرافهاي مسطح راسي 6- رنگ پذير هستند. بدون آنكه از كليت قضيه كاسته شود، فرض مي كنيم يك گراف ساده است، بنا به قضيه 4،يك راس دارد كه درجه آن حداكثر 5 است. اگر را حذف كنيم، گراف حاصل راس دارد و از اين روي 6- رنگ پذير است. پس با رنگ آميزي با رنگي به غير از اين ( حداكثر 5 رنگ) رنگ آميزي 6- رنگي از بدست مي آيد.
قضيه 6 رنگ در فوق ثابت شد، با دقت بيشتر در احكام و قضاياي گفته شده
ميتوان نتيجه قويتري موسوم به قضيه 5- رنگ بدست آورد.
در زير به بيان و اثبات اين قضيه ميپردازيم.
قضيه 5 رنگ: هر گراف مسطح پنج رنگ پذير است.
برهان: فرض كنيم حكم غلط است. در اين صورت گراف مسطح شده 6- بحراني وجود دارد و چون گراف بحراني ساده است بنا به قضيه 4 داريم . از طرف ديگر بنا به قضيه 5 داريم:
با توجه به مطالب فوق داريم: .
حال فـرض كنيم يك راس از درجه 5 ؛ در باشد و فرض كنيم يك 5 رنگ آميزي از باشد. اين چنين رنگ آميزي موجود است. زيرا يك گراف بحراني اسـت . از آنجايي كه خودش 5- رنگ پذير نيست بايد با پنج رنگ هر راس مجاور باشد.
فرض كنيم همسايه هاي در جهت عقربه اي ساعت به ترتيب است. به طوريكه براي .
زيرگراف را كه به وسيله القاء شده است با نشان مي دهيم. اكنون و بايـد متـعلـق به مولفـه هاي يكسـانــي از باشد. زيـرا در غيـر اين صورت،مولفه اي از را كه شامل، است را در نظر بگيريد. با عوض كردن رنگهاي و در اين مولفه، يك 5- رنگ آميزي اصلي جديد اختصاص داده شده به مجاوران براي با چهار رنگ ( بدون ) بدست مي آوريم.
هم اكنون نشان داديم كه اين وضعيت نمي تواند روي دهد. بنابراين و بايد متعلق به مولــفه باشند. فرض كنيد ، مسير در است و فرضكنيد دور باشــــد.( با توجـــــه به شكـــل زير)
از آنجايي كه جــــدا كننــــده و است،
بنا به شكـــل و
بنا به قــضـــيه خــــم ژوردان اين نقطــه بايد
را در نقــــطه اي قطع كند. اين نقطه بايد يـك
راس باشـد چـون يك گــراف مسطـح اسـت. ( شكل-1 )
اما اين مطلب غير ممكن است زيرا راسهاي داراي رنگهاي 2 و 4 هستند كه در آن هيچ رأس واقع در داراي يكي از اين رنگها نيست.
بعد از بيان قضيه پنج رنگ واينكه هر گراف مسطح پنج رنگ پذير است ، سؤالي كه در اينجا به ذهن مي آيد اينست كه چگونه از اين قضيه براي رنگ كردن يك گراف مسطح دلخواه استفاده كنيم .براي پاسخ به اين سؤال سعي مي كنيم با ارائه
يك فلوچارت راه حل مناسبي براي اين سؤال بيابيم .اين فلوچارت راه كار بهتر و واضح تري براي رنگ آميزي گراف با پنج رنگ به دست مي دهد.
قابل توجه اينكه از اين جهت نمودار فلوچارتي (شكل-2)را براي ارائه روش رنگ آميزي گراف انتخاب كرديم كه در ابتدا فهم آن راحـت تر و كليه حالات آن را مي توان با چشم دنبال كرد و مطلب مهمتر اين كه علاقه منداني كه مايل به ارائه نرم افزاري براي رنگ كردن گراف با پنج رنگ هستند ، فلوچارت ( شكل–2) آنها را به چند مرحله جلوتر هدايت مي كند.
حال به اين فلوچارت كه در صفحه بعد نمايش داده شدهاست توجه كنيد.
i>0
رئوس مجاور با
كمتر از 5 رنگ متفاوت ،
رنگ شده اند
(شكل - 2 ) فلوچارت رنگ آميزي گراف با پنج رنگ
حـال بـيايـيد بـا هـم گراف ( شكل – 3 ) را بـا هم رنگ كنيم . چنانكه مي بينيم درشكل (3) لذا راس را انتخـــاب كرده و آنرا از حذف مـي كنيم.
(به شكل (4) دقت كنيد) با توجـه به شكل (4) ملاحــظه ميكنيم كه لذا راس را حذف ميكنيم و گراف حاصل مي شود. (شكل (5) )
( شكل –5 ) ( شكل –4) ( شكل –3 )
با توجه به شكل (5)
لذا رئـــوس باقي مانده را با حـداكثرپنج رنگ
متفـاوت a وb وc وd وe مي توان رنـگكرد.
حال را به ميافزاييم .ملاحظه
ميكنيم مجاوران با رنگـهاي a وb وd وe
رنگ شده اند. تنها بـــدون رنگ استكه آن
را هـم با رنگ c رنـگ ميكنيـم. لــذا گراف
به اين صورت رنگ شده است.(شكل(6)) ( شكل –6)
حال در مجاوران سابق دقيق مي شويم. مي بينيم كه آنها با رنگهاي aوb وc وd وe
رنـــگ شـده اند و بـدون رنــگ اسـت و ما مجبوريم آنرا با رنگي بغير از ايـن پنــج
رنگ، رنگ كنيم. ولــي با كـمي دقت متوجه مي شويم كه چندان هم مجبور به اين كار
نيستيم، زيرا اگر ما در تغيير رنگي ايجاد كنيم ( به عنوان مثال را به جاي رنگ a با
e رنگ كنيم ) مشكـلي به وجــود نخواهد آمد. ( يعـنــي دوراس مـجاور داراي رنـ¬¬ـــگ
يكسان نخواهند بود ) بعد از اين تغييـررنگ ، براي مجاوران رنگ آميزي يافت شد،
كه با چهار رنگ، رنگ شدهاند حال بدون هيــچ
مشكلي ما مي توانيم را بـــا رنــگ پـــنجم
رنگ كنيم ، بــا توجه به( شكل –7 ) مشاهــده
ميكنيم گراف بـا پنج رنگ متـفاوت رنـگ شـده
است . اين مثالي بود برايآن چيـــزي كه ما آنـرا
بــه صـورت فلـوچارت ارائـه داديـم.
( شكل –7 )
سوالي كه اكنون پيش مي آيد اين است كه آيا قضيه پنج رنگ بهترين جواب ممكن براي مسئله است. در سال 1852 ميـلادي بود كه حـــدس زدند هر گـراف مسـطح، 4- رنگ پذير است*. ايـن حـدس به حـدس چهـار رنگ شهرت يافت. با وجود تلاشهاي زياد رياضـيدانان بزرگ براي حـل اين حـدس، حـدس چهار رنگ براي بيش از يك سده حل نشده باقيماند. تا اينكه در سال 1976 اپل و هاكن برهاني براي ايــــن حدس
*براي حدس چهار رنگ، حدس هم ارز ديگري هم هست كه مشهور به حدس ها دويگر است. قابل توجه اينكه طبق اطلاعاتي كه بدست آوردم تا سال 1999 ميلادي برهاني براي حدس هادويگر ارائه نشده است براي كسب اطلاعات بيشتر رجوع كنيد به صفحات 123 و 124 منبع شمارة ]1[ اشاره شده درپيوست سوم ..
ارائه دادند. اثبات آنها كه 4 سال طول كشيد تا نتيجه مطلوب حاصل شود و طي آن وقت زيادي صرف كار با كامپيوترشد، و اساس برهان آن همان ايده اي است كه در اثبات قضيه 5 رنگ بكار رفت. با ارائه برهان براي اين حدس، حدس چهار رنگ به قضيه چهار رنگ بدل شد.
ما در اينجا اين را به صورت قضيه عنوان و آنرا بدون برهان مي پذيريم.
قضيه 4 رنگ: هر گراف مسطح 4 - رنگ پذير است.
حال بعد از طي اين راه دراز بايد تاكنون پاسخ اين سوال را يافته باشيد كه حداقل رنگ مورد نياز براي يك گراف مسطح چقدر است وچگونه آنرا رنگ آميزي كنيم.
اگر ادعا مي كنيد كه قضيه چهار رنگ صورت قوي تري دارد مي توانيد آنرا بيان و اثبات نماييد. مطمئن باشيد كه با اثبات صورت قوي تر اين مسئله براي ابد نامتان در تاريخ رياضيات خواهد ماند.
رابرت هريك مي گويد: ” فقط كمي بيشتر كه بنويسم، كار به اتمام رسيده، به دنيا شب بخير خواهم گفت.”
سيـد حامد عبــداللهيان