Що таке проблема 2 непересічних шляхів?

Дано чотири різні вершини s 1, s 2, t 1 і t 2 графа G, проблема 2-непересічних шляхів є визначити два непересічних шляхи, p 1 від s 1 до t 1 і p 2 від s 2 до t 2, якщо такі шляхи існують. Неперетин може означати роз’єднання вершин або ребер.

Два шляхи є непересічними, якщо вони не мають спільного ребра. Наприклад: мережі зв'язку.

Проблема непересічних найкоротших шляхів визначається наступним чином. Дано граф G і k пар різних вершин (si, ti), 1 ⩽ i ⩽ k, знайдіть, чи існує k попарно непересічних найкоротших шляхів Pi між si і ti для всіх 1 ⩽i ⩽ k. Ми можемо розглядати орієнтовані або неорієнтовані графи, а шляхи можуть бути непересічними вершинами або ребрами.

Проблема індукованих непересічних шляхів є щоб вирішити, чи містить граф G з k парами заданих вершин (s_i,t_i) k взаємно індукованих шляхів P_i, таких що кожен P_i починається з s_i і закінчується в t_i. Це класична графова задача, яка є NP-повною навіть для k=2.

У теорії множин у математиці та формальній логіці дві множини називаються непересічними, якщо вони не мають спільного елемента. Рівнозначно, дві непересічні множини є множинами, перетин яких є порожньою множиною. Наприклад, {1, 2, 3} і {4, 5, 6} є непересічними множинами, тоді як {1, 2, 3} і {3, 4, 5} не є непересічними.