تعداد نواحی در گراف مسطح

Question

سلام دوستان

در گراف مسطح به ازای اضافه شدن هر راس چه تعداد به نواحی اضافه میشه ؟؟

و اینکه چرا نواحی یک نقشه را حداکثر با 4 رنگ میتوان رنگ امیزی کرد ؟؟

Comments

برای اون گراف هم درسته تفاوتش اینه که مشخصه اویلریش اون جا 4 هستش

---

منم نگفتم رابطه بالا همه جا درسته گفتم فرمول اویلر برای همه ی گراف ها بر قراره .

---

مگه فرمول ثابت نیست ؟
یعنی چی مشخصه اویلریش اونجا 4 ؟!!!
واه .. خب این دو حرفت چه فرقی با هم میکنند ؟؟

---

نه ثابت نیست برای گراف همبند همونیه که نوشتی ولی اگر همبند نباشه این طور نیست
http://fa.wikipedia.org/wiki/%D9%85%D8%B4%D8%AE%D8%B5%D9%87_%D8%A7%D9%88%D9%84%D8%B1

---

پس StefanSalvatore درست گفتن
ممنون.

Answer 1

اگر e =0 ,v=1 باشه ما 1 راس داریم پس 1 ناحیه داریم   یعنی میشه  0-1+1 = 2

فرض می کنیم این قضیه برای e یال برقراره   v+f-e=2

ثابت می کنیم برایe'  =e +1 هم درسته  یعنی عبارت روبرو باید ثابت بشه  v'+f'-e'=2

  اگر گراف حداقل یک دور داشت یکی از یال های روی اون دور رو انتخاب می کنیم و حذف می کنیم وقتی که این کارو بکنیم یعنی ما یکی از نواحی مسطح رو حذف کردیم یعنی 'f  میشه f'-1  و تعداد یال های جدید  یعنی  'e میشه  ( e+1 -1 =e )

از اون جایی که میدونیم فرض برای e یال  برقراره پس عبارت زیر بنابه فرض درسته     :   

   v'-(e'-1)+(f'-1)=v'+f'-e' =2   l
 
اگر هم گراف دور نداشته باشه میشه درخت که میدونیم  این رابطه براش درسته . (تعداد راس ها توی درخت همیشه یکی از یال ها بیشتره و 1 سطح هم بیشتر نداریم )

پس رابطه اثبات میشه .

 

Answer 2

اولاً: چه دلیلی داری که یه تعداد ثابتی اضافه بشه؟ (مگر اینکه شرط های دیگه ای داشته باشیم.)

ثانیاً: سوال دومت از اون سوال هایی که با کامپیوتر اثبات شده (مثل خیلی سوال های دیگه گراف!) ولی یکی از اساتیدمون فرمود:

هر نقشه ای رو با کمک برنامه نویسی به حدود 180 نوع گراف مختلف تناظر دادند بعد همه ی حالت ها رو بررسی کرد و دیدند که این حدس درسته !

 

اطلاعات اضافه شده:

یه سری دسته بندی کلی شده بعد با کمک نظریه گروه ها و کامپیوتر همه ی حالت ها رو حساب کردند.

Answer 3

انتظار نداشته باش که قضیه ی رنگ آمیزی نقشه با چهار رنگ رو بشه این جا اثبات کرد. چون حدود 100 سال وقت ریاضی دان ها رو به خودش مشغول کرد. اما ارزش فکر کردن داره...

صرفا جهت اصلاح پاسخ قبلی، جواب رو میذارم.

کم ترین تعداد یال ها در یک گراف n راسی که همبند باشد، n-1 است. در این حالت تعداد ناحیه ها برابر 1 است. ما این n-1 یال رو به این شکل در گرافمون قرار میدیم.

•---•---•---•--- ............ •---•---•

خط فاصله ها یال هامون هستند و نقطه ها، راس هامون.

(البته مدل های دیگه هم میشه و ما در این قسمت، حالت خاص در نظر نگرفتیم)

حالا هر راسی که به گراف بالا اضافه کنیم، تعداد ناحیه ها هم دقیقا به علاوه ی 1 میشود. و رابطه برقرار میماند.

ولی هنوز هم نفهمیدم که چه ربطی به تعداد راس ها داره. (چون معلوم نیست چند تا یال به راسی که اضافه میشه متصل هست)

Comments

نه کامل نیست.

---

پس ربطی به نواحی نداره

---

اون چیزی که تو دیدگاه بالا گفتم را چی ؟
با استقرا نمیشه ثابت کرد ؟