گراف شبکه‌ای

گراف شبکه‌ای، گراف مشبک، گراف گریدی یا گراف مش، گرافی است که رسم آن در فضای اقلیدسی $\Re ^{n}$ جاسازی شده است و یک کاشی کاری منظم را تشکیل می‌دهد. این نشان می‌دهد که گروهی از تبدیل‌های دوطرفه که گراف را به خود می‌فرستند یک شبکه به معنای نظری گروهی هستند.

گراف شبکه مربعی

گراف شبکه مثلثی

به‌طور معمول، هیچ تمایز روشنی بین چنین گرافی به معنای انتزاعی تر نظریه گراف و ترسیم آن در فضا (اغلب فضای صفحه یا سه بعدی) وجود ندارد. این نوع گراف را می‌توان به‌طور خلاصه فقط یک شبکه، مش یا گرید نامید. علاوه بر این، این عبارات معمولاً برای بخش محدودی از گراف بی‌نهایت نیز استفاده می‌شوند، مانند "یک شبکه مربع 8 × 8 ".

اصطلاح گراف شبکه نیز در ادبیات به انواع دیگر نمودارها با ساختاری منظم، مانند حاصل ضرب دکارتی تعدادی گراف کامل، داده شده‌است.

گراف شبکه مربعی

یک نوع رایج گراف شبکه ای (که با نام‌های مختلف شناخته می‌شود، مانند گراف شبکه ای مربعی) گرافی است که رئوس آن با نقاط صفحه با مختصات عدد صحیح مطابقت دارد، مختصات افقی(x-coordinates) در محدوده $1,\cdots ,n$ دارند.$1,\cdots ,n$ مختصات عمودی y-coordinates در محدوده $1,\cdots ,m$ و هر زمان که نقاط مربوطه در فاصله ۱ قرار گیرند، دو راس توسط یک یال به هم متصل می‌شوند. به عبارت دیگر، یک گراف فاصله واحد برای مجموعه نقاط توصیف شده‌است.

خواص

یک گراف شبکه ای مربعی حاصل ضرب دکارتی از نمودارها، یعنی از دو گراف مسیر با n - 1 و m - 1 لبه است. از آنجایی که یک گراف مسیر یک گراف میانه است، واقعیت اخیر نشان می‌دهد که گراف شبکه مربع نیز یک گراف میانه است. همه نمودارهای شبکه دو بخشی هستند، که به راحتی با این واقعیت تأیید می‌شود که می‌توان رئوس را به شکل شطرنجی رنگ کرد.

یک گراف مسیر ممکن است به عنوان یک گراف شبکه ای در شبکه n ضربدر ۱ در نظر گرفته شود. الف 2 × گراف شبکه ۲ یک ۴ چرخه است.

هر گراف مسطحی H جزئی از h است × h grid، که در آن $h=2|V(H)|+4|E(H)|$ .

انواع دیگر

گراف شبکه مثلثی گرافی است که مطابق با یک شبکه مثلثی است.

گراف شبکه ای هانان برای مجموعه محدودی از نقاط در صفحه توسط شبکه ای که از تقاطع تمام خطوط عمودی و افقی در هر نقطه از مجموعه به دست می‌آید، تولید می‌شود.

گراف رخ (گرافی که تمام حرکات قانونی مهره شطرنج رخ روی صفحه شطرنج را نشان می‌دهد) گاهی اوقات گراف شبکه نیز نامیده می‌شود، اگرچه این گراف کاملاً با گراف مشبکی که در این مقاله توضیح داده شده متفاوت است. حرکات معتبر مهره شطرنج خیالی وزیر گراف شبکه مربعی را تشکیل می‌دهد.

جستارهای وابسته

• مسیر مشبک
• قضیه پیک
• مثلث‌های عدد صحیح در یک شبکه دو بعدی
• مشبک (ترتیب)