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

Question

سلام دوستان

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

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

Comments

منظورتون گراف مسطح «کامل» هست؟

---

منظورت چیه چند تا ناحیه اضافه میشه ؟ مگه اضافه کردن راس ربطی به اضافه شدن ناحیه داره ؟ خب میشه یک راس اضافه کرد وهیچ یالی هم رسم نکرد  و هم میشه n تا یال رسم کرد !

---

در مورد سوال دوم این لینک رو ببین (البته من که نفهمیدم چی به چیه :)  )
http://dharwadker.org/

---

ببین یه گراف مسطح با تعداد یال(e) و راس(v) و نواحی(f) ... حالا با استقرا باید ثابت کنیم که v+f-e=2

---

فکر کنم سوال دوم رو اشتب گذاشتی. چون این رابطه برای گراف های هامنی(مسطح) و «همبند» صدق میکنه و با استقرا هم ثابت میشه. (اگر سوال این بود، میتونم بگم جواب رو)

---

منظورت از سوال دوم اینه :یه گراف مسطح با تعداد یال(e) و راس(v) و نواحی(f) ... حالا با استقرا باید ثابت کنیم که v+f-e=2
؟؟

---

آهان خب همون اول بپرس چطوری فرمول اولر اثبات میشه :)

---

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

---

ممنون.
....
ذکر نکرده باید همبند باشه !!
چرا ؟

---

دلیلی نداره که همبند باشه !
فرمول اولر برای همه ی گراف ها درسته !

---

فرض کن n تا راس داریم
و بین اون ها n-3 یال رسم کرده ایم به طوری که تعداد نواحی 0 است (سه زنجیره ساخته ایم / سه مولفه ی همبند داریم)
این جا رابطه درسته؟
1+n - n +3 برابر 2 نیست

---

برای اون گراف هم درسته تفاوتش اینه که مشخصه اویلریش اون جا 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

نه کامل نیست.

---

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

---

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