بخشی از مقاله
چکیده
یک گراف هندسی را وترافزایشی گویند هرگاه بین هر دو رأس از گراف، مسیری وجود داشته باشد به طوری که برای هر چهار نقطه a، b، c و d که به ترتیب روی مسیر قرار گرفته اند، فاصله a و d از فاصله b و c کمتر نباشد. در این مقاله نشان می دهیم برای دورها و - گراف های هندسی با n رأس، در زمان - ٢O - n می توان وترافزایشی بودن را تشخیص داد. برای گراف هایی که هر یال آنها روی حداکثر یک دور قرار دارد و هر دور دقیقا یک رأس برشی دارد، می توان در زمان n - ٢+ k ٢O - n که k مجموع تعداد دورها و رئوس درجه یک گراف و n تعداد رئوس گراف است، وترافزایشی بودن را تشخیص داد. همچنین نشان می دهیم تشخیص وترافزایشی بودن گراف های هندسی متعامد با n رأس و m یال در زمان O - nm - ممکن است.
مقدمه
گرافی که در صفحه رسم شده باشد بهطوری که منحنی متناظر با هر یال، پاره خط واصل بین دو انتهای آن یال باشد، گراف هندسی نام دارد. گراف های هندسی وترافزایشی ١ اولین بار در سال ٢٠١٢ در ]١[ تعریف شدند. یک گراف هندسی را وترافزایشی گویند هرگاه بین هر دو رأس آن، یک مسیر وترافزایشی وجود داشته باشد. یک مسیر را وترافزایشی گویند هرگاه برای هر چهار نقطه a، b، c و d که به ترتیب روی مسیر قرار گرفته اند، فاصله a و d از فاصله b و c کمتر نباشد. برای تشخیص وترافزایشی بودن مسیرهای هندسی، الگوریتمی با پیچیدگی O - n - و برای درخت ها، الگوریتمی با پیچیدگی - ٢O - n وجود دارد ]١.[ اما تاکنون هیچ الگوریتمی برای تشخیص وترافزایشی بودن گراف ها در حالت کلی ارائه نشده است. در این مقاله مسئله وترافزایشی بودن را برای دورها، - گراف ها، کلاسی از گراف ها به نام گراف های خوشه انگوری و گراف های هندسی متعامد بررسی می کنیم.
محققان دو مسئله دیگر را در زمینه گراف های هندسی وترافزایشی مورد بررسی قرار داده اند. اول اینکه برای یک گراف داده شده، آیا رسمی وترافزایشی از آن گراف وجود دارد؟ این سؤال برای درخت ها و گراف های مثلث بندی ٢ در مراجع ]١[ و ]۴[ پاسخ داده شده است. در مسئله دوم برای یک تعداد نقطه داده شده در صفحه، وجود و ساخت پوشش های هندسی ٣ وترافزایشی روی نقاط مورد بحث و بررسی قرار می گیرد که در مراجع ]٢[ و ]٣[ به این مسئله پرداخته شده است.
در این مقاله شامل مطالبی است که در ادامه می آید: در قسمت ٢ تعاریف مقدماتی و نتایج مورد نیاز بیان می شود. در قسمت ٣ نشان می دهیم، وترافزایشی بودن یک دور هندسی و یک - گراف هندسی با n رأس را می توان در زمان - ٢O - n تشخیص داد. در قسمت ۴ نشان می دهیم، می توان در زمان n - ٢+ k ٢O - n برای گراف های خوشه انگوری هندسی با n رأس و k دور و رأس درجه یک، وترافزایشی بودن را تشخیص داد. در نهایت در قسمت ۵ نشان می دهیم وترافزایشی بودن گراف های هندسی متعامد با منهتن ۴ بودن آنها معادل است و تشخیص منهتن بودن آنها در زمان O - nm - امکان پذیر است.
تعاریف مقدماتی
یک مسیر بین دو رأس s و t، از s به t خودگرا ۵ است هرگاه به ازای هر سه نقطه a، b و c به طوری که s; a; b; c; t به ترتیب روی مسیر قرار گرفته اند، فاصله اقلیدسی a و c از فاصله اقلیدسی b و c کمتر نباشد. با توجه به تعاریف واضح است که یک مسیر بین دو رأس s و t وترافزایشی است اگر و فقط اگر هم از s به t و هم از t به s خودگرا باشد.
نمادگذاری: پاره خط pq در صفحه را در نظر بگیرید. lpq خط عمود بر pq و شامل نقطه q است. نیم صفحه بسته که مرز lpq دارد و شامل نقطه p نیست را با l+pq نمایش می دهیم. ناحیه محدود بین دو خط lpq و lqp را نوار pq می گوییم.
شکل ١: خطوط lpq و lqp، نوار pq که خاکستری تیره است و l+pq که خاکستری روشن است.
بر اساس قضیه ٢. ١ در مرجع ]١[، الگوریتمی ارائه شده است که می تواند در زمان خطی با شروع از ابتدای یک مسیر، رأسی را بیابد که زیرمسیر از آن رأس به رأس ابتدای مسیر، خودگرا باشد و نسبت به این ویژگی ماکسیمال باشد.
توجه ٢. ٢. در درخت ها خاصیت وترافزایشی و خاصیت خودگرایی معادلند زیرا بین هر دو رأس دلخواه، دقیقا یک مسیر وجود دارد.
لم ٢. ٣. ]١[ نوار هر یال دلخواه uv از درخت هندسی وترافزایشی T، با T uv برخوردی ندارد.
عکس گزاره فوق نیز درست است، بنابراین می توان در زمان - ٢O - n، وترافزایشی بودن یک درخت را تشخیص داد.
دورها و - گراف ها
با توجه به قضیه ٢. ١، می توان خودگرا یا وترافزایشی بودن هر گراف که تعداد ثابتی مسیر بین هر دو رأس آن وجود دارد را در زمان - ٣O - n تشخیص داد. در ادامه الگوریتمی با زمان اجرای - ٢O - n برای تشخیص وترافزایشی بودن دورها و - گراف های هندسی ارائه می دهیم.
فرض کنید u یک رأس دلخواه از یک دور هندسی باشد. طولانی ترین مسیر وترافزایشی از دور که از u شروع می شود و به صورت ساعتگرد ادامه می یابد را در نظر بگیرید. رأس انتهای این مسیر را رأس راست u می نامیم و با r - u - نشان می دهیم. رأس چپ u، l - u - به صورت مشابه تعریف می شود.
گزاره ٣ . ١. ا گر u یک رأس دلخواه از یک دور هندسی وترافزایشی باشد، آنگاه l - u - = r - u - و یا اینکه r - u - و l - u - مجاورند بهطوری که r - u - در ترتیب دوری ساعتگرد، قبل از l - u - قرار می گیرد.
برهان. r - u - و l - u - از هم عبور نمی کنند چون در این صورت یالی از دور وجود دارد که در نوار آن، هیچ نقطه ای از دور قرار ندارد و در صورتی که حالت های ذکر شده در گزاره رخ ندهد رأسی وجود دارد که بین آن رأس و u، مسیر وترافزایشی وجود ندارد.
شکل ٢: - a - عبور r - u - و l - u - از یکدیگر، - b - نمونه ای از یک گراف خوشه انگوری
در یک دور هندسی، رأس u را یک رأس خوب می نامیم هرگاه l - u - = r - u - و یا اینکه l - u - و r - u - مجاورباشند بهطوری که در ترتیب ساعتگرد، r - u - قبل از l - u - قرار گیرد.
نتیجه ٣. ٢. یک دور هندسی وترافزایشی است اگر و فقط اگر همه رأس های آن خوب باشند.
قضیه ٣. ٣. می توان در زمان - ٢O - n وترافزایشی بودن یک دور هندسی با n رأس را تشخیص داد.
برهان. - خلاصه - با استفاده از الگوریتم یافتن زیرمسیر ماکسیمال خودگرا در مرجع ]١[ و گزاره ٣ . ١ می توان خوب بودن یک رأس از یک دور هندسی را در زمان O - n - تشخیص داد.
لم ٣. ۴. ]۴[ در یک دور هندسی خودگرا، هیچ دو زاویه غیرمتوالی همزمان کمتر از ◦٩٠ نیستند.
از لم ٣ . ۴ می توان نتیجه گرفت در یک دور هندسی خودگرا با حداقل چهار یال، حداکثر دو زاویه حاده وجود دارد. در حالت هایی که حداقل یک زاویه حاده داریم، بررسی وترافزایشی بودن دور در زمان خطی ممکن است. همان طور که در شکل ٣ مشاهده می کنید
