معمای آب و برق و گاز

مدیران انجمن: parse, javad123javad

ارسال پست
نمایه کاربر
rohamjpl

نام: Roham Hesami رهام حسامی

محل اقامت: فعلا تهران قیطریه بلوار کتابی 8 متری صبا City of Leicester Area of Leicestershire LE7

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 2141

سپاس: 3824

جنسیت:

تماس:

معمای آب و برق و گاز

پست توسط rohamjpl »

تصویر
اگر G(V,E) یک گراف مسطح باشه و هیچ چرخه ای به طول 3 نداره آنگاه |E|≤2|V|-4.
در مورد ما |V|=6 (تعداد گره ها) و ما به |E|=9 (تعداد لبه ها) نیاز داریم. نموداری که ما داریم نمی تواند مثلثی داشته باشد، زیرا دو قسمتی است و هر گراف دو بخشی فقط می تواند چرخه های طول زوج داشته باشد.در اینجا یک راه حل وجود دارد: یک گراف G مسطح است سپس $|E(G)|\leq 3|v(G)|-6$. اگر علاوه بر این، بدون مثلث باشد،$|E(G)| \leq 2|V(G)|-4$ برای K3،3، دارای مثلث نیست زیرا شامل چرخه فرد نیستش میبینید که پس. بنابراین فرمول دوم را اعمال میکنم : $9\leq 2*6-4=8$که ممکن نیست بنابراین نمی تونه مسطح باشه.
برای نشون دادن$|E(G)| \leq 2|V(G)|-4$، از معادله اویلر استفاده می کنیم:$|V|-|E|+|F|$ برای نمودار مسطح. توجه داشته باشید که اگر تعداد کل لبه های اطراف وجه ها را بشمارید ، هر یال را دو بار می شمارید. پس$\sum_{a\in F(G)}{len(a)}=2|E(G)|$. اکنون از آنجایی که نمودار مثلثی نداره هر صورت حداقل با 4 یال محدود میشه. بنابراین $\sum_{a\in F(G)}{len(a)}=2|E(G)|$ حل برای |F| در معادله اویلر و جایگزینی با نامساوی قبلی برای به دست آوردن نابرابری مورد نظر. امیدوارم درست متوجه شده باشینhope I helped you understand the question. Roham Hesami, sixth
semester of aerospace engineering
smile072 smile072 رهام حسامی ترم ششم مهندسی هوافضاتصویر
smile260 smile016 :?:
تصویر

ارسال پست