1
두 부분으로 이루어진 그래프를 비순환으로 만드는 알고리즘 설계와 관련하여 질문이있었습니다. 누군가가 나를 도울 수 있기를 바랍니다.트리/포리스트로 이분 그래프를 줄이기위한 알고리즘 설계 (제약 조건 포함)
U = {u_1, u_2, ... u_M}가 M 개의 노드로 구성된 무차별 2 진 그래프 G = (v_1, w)를 생각해 보자. , v_2, ..., v_N}는 N 개의 노드들의 집합이고, E는 U의 노드들을 V의 노드들에 연결하는 에지들의 집합이다. 간략화를 위해, 그래프는 연결되고 순환한다.
목표는주기를 제거하고 그래프를 트리 또는 포리스트로 축소하는 알고리즘을 설계하는 것입니다. 알고리즘은 라운드에서 진행됩니다. 라운드는 U의 각 노드 u_i, i = 1, 2, ..., M을 선택하고 그것에 연결된 에지를 제거하는 것으로 설명됩니다. 노드 u_i가 분리되어있는 경우 (즉, 연결된 에지가없는 경우), 우리는이를 무시하고 계속 진행한다. 대부분의 M 가장자리에서이 방법은 각 라운드에서 제거됩니다. 알고리즘은 그래프가 일부 라운드가 끝날 때 트리 또는 포리스트로 축소 될 때 중지됩니다.
(그래프를 트리/포리스트로 줄이기 위해) 라운드 수를 최소화하도록 라운드를 설계하기위한 다항식 시간 알고리즘 (M, N)이 가능한지 알고 싶습니다.
'원형 설계'란 무엇을 의미합니까? –
@BenjaminGruenbaum 그는 라운드의 총 수가 최소가되도록 각 라운드에서 제거 할 가장자리를 선택하는 방법을 묻습니다. –
@ChrisPitman _round는 각 노드를 선택하는 것으로 설명됩니다. _ 그래서 문제의 의미를 생각하면 "라운드는 ** 노드를 선택하는 것으로 묘사됩니다." –