گراف مسطح و فرمول اویلر؛ رأس، یال و ناحیه
آموزش نمایش مسطح، ناحیهها، فرمول اویلر و کران تعداد یال برای تستهای نظریه گراف کنکور.
پاسخ کوتاه
گراف مسطح را میتوان طوری روی صفحه رسم کرد که یالها جز در رأس مشترک همدیگر را قطع نکنند. در یک نمایش مسطح همبند، تعداد رأسها، یالها و ناحیهها با فرمول اویلر مرتبطاند.
مسطحبودن
تقاطع یالها در یک رسم خاص لزوماً غیرمسطحبودن را ثابت نمیکند؛ ممکن است با جابهجایی رأسها تقاطع حذف شود. گراف زمانی مسطح است که دستکم یک نمایش بدون تقاطع داخلی یالها داشته باشد.
ناحیهها
یالهای یک نمایش مسطح صفحه را به ناحیهها تقسیم میکنند. ناحیه نامحدود بیرونی نیز یک ناحیه حساب میشود. تعداد ناحیهها ممکن است با افزودن یالی که دور میسازد یک واحد افزایش یابد.
فرمول اویلر
برای گراف مسطح همبند با V رأس، E یال و F ناحیه داریم V-E+F=2. اگر گراف چند مؤلفه داشته باشد، شکل فرمول تغییر میکند؛ بنابراین پیش از استفاده همبندی را بررسی کن.
کران یالها
در گراف مسطح ساده با V≥3، هر ناحیه دستکم سه ضلع دارد و از شمارش مرزها نتیجه E≤3V-6 به دست میآید. برای گراف دوبخشی مسطح که مثلث ندارد، کران قویتر E≤2V-4 است.
مثال و تست کوتاه
یک گراف مسطح همبند با 8 رأس و 12 یال چند ناحیه دارد؟ از 8-12+F=2 نتیجه میشود F=6. این عدد شامل ناحیه بیرونی نیز هست و حذف آن پاسخ 5 را بهاشتباه میدهد.
چکلیست حل تست
- ناحیه بیرونی را هم بشمار.
- فرمول V-E+F=2 برای حالت همبند است.
- تقاطع در یک رسم، غیرمسطحبودن قطعی نیست.