درج کردن حریصانه

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

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

تعاریف

در مسیریابی حریصانه، یک پیام از یک راس مبدأ s به یک راس مقصد t، با یک سری قدم در بین راس‌های میانی سفر می‌کند، که هر کدام از آن قدم‌ها، پیام را به یک راس مجاور می‌دهد که به t نزدیک‌تر است. اگر پیام به یک راس میانی x برسد که راس مجاور نزدیک‌تری به t نداشته‌باشد، پس نمی‌توان پیش‌رفت کرد، و روند مسیریابی حریصانه شکست می‌خورد. یک برازش حریصانه، برازشی است از گراف داده‌شده، با ویژگی‌ای که این‌گونه شکست غیرممکن باشد. پس، می‌توان برازش حربصانه را برازشی از گراف تعریف کرد که برای هر دو راس x و t، یک راس مجاور x به نام y وجود دارد که y به t نزدیک‌تر است.

گراف‌های بدون برازش حریصانه

K_1,6، یک گراف بدون برازش حریصانه در فضای دوبعدی

هر گرافی در فضای دوبعدی دارای برازش حریصانه نیست؛ یک مثال نقض ساده، ستارهٔ شش‌پر K1,6 است، درختی با یک راس میانی و شش برگ. به طوری که در هر برازش این گراف، دو برگ وجود دارند که زاویهٔ بین آن‌ها، کمترمساوی ۶۰ درجه‌اند، که نتیجه می‌شود که حداقل یکی از این دو راس، راس مجاوری که به راس دیگر نزدیک‌تر باشد ندارند.

در فضاهای اقلیدسی با بعدهای بالا، گراف‌های بیش‌تری دارای برازش حریصانه‌اند؛ برای مثال، ستارهٔ شش‌پر در فضای سه‌بعدی دارای برازش حریصانه است، به‌طوری که راس میانی در مرکز و برگ‌ها هر کدام در فاصلهٔ واحد از مرکز در شش جهت بردار نشان هستند. البته، در هر فضا با بعد ثابت، گراف‌هایی هستند که نمی‌توانند حریصانه برازش شوند؛ زمانی که n, از عدد تماس یک فضا، بیش‌تر باشد، ستارهٔ nپر دارای برازش حریصانه نیست.

برازش‌های هیپربولیک و فشرده

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

حالت‌های خاص گراف‌ها

درخت‌ها

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

گراف‌های مسطح

پاپادیمیتریو و راتاژاک، حدس زده‌بودند که تمام گراف‌های پلی‌هدرال (یک گراف مسطح 3 راس)، دارای برازش حریصانه در فضای دوبعدی‌اند.