Uma divisão d independente

Question

Eu adoraria ter uma orientação para o seguinte exercício (o material para este exercício são algoritmos gananciosos):

Deixar $G = (V,E)$ um gráfico não direcionado cujos vértices $V = \{v_1,\pontos,v_n\}$ aparecem nesta ordem na linha real (ou seja, para todos $1 \leq i < j \leq n$, $v_i$ aparece antes $v_j$).

A $d$-divisão de $G$os vértices de é uma divisão em $d$ intervalos diferentes, ou seja, a escolha de $d-1$ índices $1 \leq i_1 < i_2 < \dots < i_{d-1} < n$ que definem os intervalos:$$ [v_1,\dots,v_{i_1}], [v_{i_1+1},\dots,v_{i_2}],\dots,[v_{i_{d-1}+1},\dots, v_n].$$

A $d$-divisão é chamada independente se não houver dois vértices vizinhos no mesmo intervalo.Ou seja, a divisão é independente se fortodos $0 \leq r <d$ e para todos $i_r < j_1 < j_2 \leq i_{r+1}$ Nós temos $\{v_{j_1},v_{j_2}\} otin E$, onde $i_0 = 0$ e $i_d = n$.

Ofereça um algoritmo com complexidade de tempo $O(V+E)$ que encontra um independente $d$-divisão de $G$ de tal modo que $d$ é mínimo.Prove a correção do algoritmo.

Perceber:A divisão neste exercício é “contínua”.Por exemplo, se $v_1$ e $v_3$ estão no mesmo intervalo, então $v_2$ está no mesmo intervalo com eles.Além disso, não há arestas entre quaisquer dois vértices no mesmo intervalo.Por exemplo, se o primeiro intervalo da divisão for $[v_1,v_2,v_3]$, então $\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_1\} otin E$.

Muito obrigado,

Answer 1

Pense no que acontece quando você consegue encontrar o primeiro intervalo, digamos que é $[v_1,...,v_k]$ para alguns $k$.Então o que você poderia dizer sobre a divisão mínima de $v_{k+1},...,v_n?$

Pense também em como você poderia encontrar o primeiro intervalo.Começar com um intervalo vazio e expandi-lo (como?) deve resolver.