음이 아닌 간선 가중치와 두 개의 고유 정점 s,t

$s,t$ 로 연결된 무 방향 그래프를 고려하십시오 . 다음은 모두 다음과 같은 형식의 일부 경로 문제입니다. 경로에서 가장자리 가중치의 일부 기능이 최소가 되도록 s−t

$s-t$ 경로를 찾으십시오 . 이런 의미에서 그것들은 모두 최단 경로 문제의 “상대적”입니다. 후자의 함수는 단순히 합계입니다.

참고 : 우리는 간단한 경로, 즉 반복 정점이없는 것을 찾고 있습니다. 문헌에서 이러한 문제에 대한 표준 이름을 찾지 못했기 때문에 스스로 이름을 지정했습니다.

최소 무게 차이가있는 경로 : 경로에서 가장 큰 가장자리 가중치와 가장 작은 가장자리 가중치의 차이가 최소가 되도록 s−t

$s-t$

$s-t$ 경로를 찾으십시오 .

가장 부드러운 경로 : 경로에서 가장 큰 단계 크기가 최소가 되도록 s−t

$s-t$

$s-t$ 경로를 찾으십시오. 여기서 단계 크기는 두 개의 연속 모서리 사이의 무게 차이의 절대 값입니다 .

최소 고도 가있는 경로 : 경로를 따라 단계 크기의 합으로 경로의 고도를 정의합니다 (위의 단계 크기 정의 참조). 최소 고도로 s−t

$s-t$

$s-t$ 경로를 찾으십시오 .

최소 소수 가중치를 가진 경로 : 모든 모서리 가중치가 양의 정수라고 가정하면 가중치가 소수 가되도록 s−t

$s-t$

$s-t$ 경로를 찾으십시오 . 그러한 경로가 있다면, 가능한 가장 작은 무게를 가진 경로를 찾으십시오.

질문 : 이러한 경로 문제에 대해 알려진 것은 무엇입니까? (그리고 비슷한 정신으로 생각할 수있는 다른 것들이 가중치의 다른 기능을 적용합니다.) 일반적으로, 다항식 시간에서 에지 가중치의 기능을 최소화 할 수 있고 NP-hard 인 지침이 있습니까?

s

$s$t

$t$s−t

$s-t$

답변