معمای آب و برق و گاز
- rohamavation
نام: roham hesami radرهام حسامی راد
محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2
عضویت : سهشنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴
پست: 3278-
سپاس: 5494
- جنسیت:
تماس:
معمای آب و برق و گاز
اگر 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
رهام حسامی ترم ششم مهندسی هوافضا
-
نام: محمد حسن
عضویت : دوشنبه ۱۴۰۱/۸/۹ - ۰۰:۲۰
پست: 1-
- جنسیت:
- rohamavation
نام: roham hesami radرهام حسامی راد
محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2
عضویت : سهشنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴
پست: 3278-
سپاس: 5494
- جنسیت:
تماس:
Re: معمای آب و برق و گاز
سه خانه A، B، و C، و سه ابزار (گاز، برق، آب) با برچسب X، Y و Z وجود دارد. BY، BZ، CX، CY، و CZ، که هیچکدام به جز در نقاط پایانی تلاقی نمیکنند:
سپس، فقط با استفاده از B، X، Y و Z، و منحنی های اتصال BX، BY، و BZ، ورق لاستیکی را می توان کشید تا به دست آورد:
سپس ورق لاستیکی را می توان کشید و خانه C و منحنی CY را مانند:
حالا برای دیدن سخت ترین قسمت:
منحنی CZ را می توان به یکی از دو حالت کشش داد:
سمت چپ ترین تصویر (مورد 1) به وضوح یکی از این منحنی ها است، اما برای متقاعد کردن خود که سمت راست ترین تصویر (مورد 2) تنها منحنی ممکن دیگر CZ است، باید کمی فکر کرد. یکی از راه های استدلال این است که حلقه BY CZ یا X را محصور می کند یا نه.
مورد مناسب را در نظر بگیرید.
باید یک منحنی CX وجود داشته باشد، و تنها امکان این است که بتوان آن را تغییر شکل داد و به این ترتیب:
سپس خانه A باید در یکی از مناطق I، II یا III باشد.
اگر A در ناحیه I باشد، نمی توان آن را با منحنی که از هیچ منحنی دیگری عبور نمی کند، به ابزار Y متصل کرد. اگر A در II باشد، نمی تواند به Z وصل شود و در نهایت اگر A در ناحیه III باشد، نمی تواند به X متصل شود.
بنابراین فقط مورد 1 باقی می ماند. با کشش منحنی CX، دوباره دو حالت دریافت میکنیم (با همان استدلال بالا - تنها دو منحنی ممکن است با تعیین اینکه آیا Z در داخل حلقه توسط CX قرار دارد یا نه):
خانه A را در نمودار سمت چپ قرار دهید. اگر در منطقه I باشد، نمی تواند به Y وصل شود، اگر A در II باشد، نمی تواند به Z وصل شود، و اگر A در منطقه III باشد، نمی تواند به X متصل شود. همین جملات در نمودار سمت راست نیز صدق می کند.
بنابراین همه موارد مورد مطالعه قرار گرفته اند و پازل خدمات رفاهی Utilities هیچ راه حلی درصفحه ندارد. به طور معادل نمودار K3,3 غیر مسطح است.
در اینجا یک راه منظم دیگر برای حل آن وجود دارد: پازل را روی یک ورق کاغذ بازتولید کنید، سپس آن را بغلتانید تا یک استوانه شکل بگیرد و همانطور که در شکل نشان داده شده است یک نوار کاغذی به آن اضافه کنید. ب تصویر نهایی c نشان می دهد که چگونه پازل باید ظاهر شود و چگونه خانه های A، B و C در نهایت به تامین کنندگان ابزار وصل می شوند.نمودار 3 اگر تامین کننده های تاسیسات را به خانه ها متصل کنیم، 3 x 3 = 9 یال بدست می آوریم (نمودار K3،3 بالا را ببینید)، زیرا هر یک از 3 تامین کننده ابزار به 3 خانه متصل است. ما می دانیم که مرز هر Face یک حلقه بسته از Edgesلبه ها است، و می دانیم که هر Edgeلبه بین یک خانه و یک تامین کننده ابزار قرار می گیرد (دلیلی وجود ندارد که از یک خانه به یک ابزار مفید برویم و به همان خانه برگردیم). این بدان معناست که مرز یک صورت توسط حداقل 4 لبه ساخته شده است (شکل f روبرو را ببینید).
حالا بیایید از فرمول اویلر استفاده کنیم تا بفهمیم چند چهره در پازل وجود دارد:
$V - E + F = 2$
$ F = 2 + E - V$و
$F = 2 + 9 - 6$
$F = 5 $وجه
هر Face حداقل 4 لبه دارد، بنابراین تعداد لبه ها در همه Faces حداقل 4 x 5 = 20 Edge است. این هر لبه را دو بار میشمارد، زیرا هر لبه مرزی برای 2 چهره است. بنابراین، کوچکترین تعداد لبه ها 20 / 2 = 10 لبه است. با این حال، ما می دانیم که تنها 9 لبه وجود دارد! این یک تناقض است... از آنجایی که هیچ چیز نمی تواند همزمان 9 یال و 10 لبه داشته باشد، ترسیم راه حلی برای پازل سه ابزار مفید باید غیرممکن باشد.
سپس، فقط با استفاده از B، X، Y و Z، و منحنی های اتصال BX، BY، و BZ، ورق لاستیکی را می توان کشید تا به دست آورد:
سپس ورق لاستیکی را می توان کشید و خانه C و منحنی CY را مانند:
حالا برای دیدن سخت ترین قسمت:
منحنی CZ را می توان به یکی از دو حالت کشش داد:
سمت چپ ترین تصویر (مورد 1) به وضوح یکی از این منحنی ها است، اما برای متقاعد کردن خود که سمت راست ترین تصویر (مورد 2) تنها منحنی ممکن دیگر CZ است، باید کمی فکر کرد. یکی از راه های استدلال این است که حلقه BY CZ یا X را محصور می کند یا نه.
مورد مناسب را در نظر بگیرید.
باید یک منحنی CX وجود داشته باشد، و تنها امکان این است که بتوان آن را تغییر شکل داد و به این ترتیب:
سپس خانه A باید در یکی از مناطق I، II یا III باشد.
اگر A در ناحیه I باشد، نمی توان آن را با منحنی که از هیچ منحنی دیگری عبور نمی کند، به ابزار Y متصل کرد. اگر A در II باشد، نمی تواند به Z وصل شود و در نهایت اگر A در ناحیه III باشد، نمی تواند به X متصل شود.
بنابراین فقط مورد 1 باقی می ماند. با کشش منحنی CX، دوباره دو حالت دریافت میکنیم (با همان استدلال بالا - تنها دو منحنی ممکن است با تعیین اینکه آیا Z در داخل حلقه توسط CX قرار دارد یا نه):
خانه A را در نمودار سمت چپ قرار دهید. اگر در منطقه I باشد، نمی تواند به Y وصل شود، اگر A در II باشد، نمی تواند به Z وصل شود، و اگر A در منطقه III باشد، نمی تواند به X متصل شود. همین جملات در نمودار سمت راست نیز صدق می کند.
بنابراین همه موارد مورد مطالعه قرار گرفته اند و پازل خدمات رفاهی Utilities هیچ راه حلی درصفحه ندارد. به طور معادل نمودار K3,3 غیر مسطح است.
در اینجا یک راه منظم دیگر برای حل آن وجود دارد: پازل را روی یک ورق کاغذ بازتولید کنید، سپس آن را بغلتانید تا یک استوانه شکل بگیرد و همانطور که در شکل نشان داده شده است یک نوار کاغذی به آن اضافه کنید. ب تصویر نهایی c نشان می دهد که چگونه پازل باید ظاهر شود و چگونه خانه های A، B و C در نهایت به تامین کنندگان ابزار وصل می شوند.نمودار 3 اگر تامین کننده های تاسیسات را به خانه ها متصل کنیم، 3 x 3 = 9 یال بدست می آوریم (نمودار K3،3 بالا را ببینید)، زیرا هر یک از 3 تامین کننده ابزار به 3 خانه متصل است. ما می دانیم که مرز هر Face یک حلقه بسته از Edgesلبه ها است، و می دانیم که هر Edgeلبه بین یک خانه و یک تامین کننده ابزار قرار می گیرد (دلیلی وجود ندارد که از یک خانه به یک ابزار مفید برویم و به همان خانه برگردیم). این بدان معناست که مرز یک صورت توسط حداقل 4 لبه ساخته شده است (شکل f روبرو را ببینید).
حالا بیایید از فرمول اویلر استفاده کنیم تا بفهمیم چند چهره در پازل وجود دارد:
$V - E + F = 2$
$ F = 2 + E - V$و
$F = 2 + 9 - 6$
$F = 5 $وجه
هر Face حداقل 4 لبه دارد، بنابراین تعداد لبه ها در همه Faces حداقل 4 x 5 = 20 Edge است. این هر لبه را دو بار میشمارد، زیرا هر لبه مرزی برای 2 چهره است. بنابراین، کوچکترین تعداد لبه ها 20 / 2 = 10 لبه است. با این حال، ما می دانیم که تنها 9 لبه وجود دارد! این یک تناقض است... از آنجایی که هیچ چیز نمی تواند همزمان 9 یال و 10 لبه داشته باشد، ترسیم راه حلی برای پازل سه ابزار مفید باید غیرممکن باشد.