رابطه ی بین اعداد موقعیت عمومی راس و یال

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