Usando um algoritmo ganancioso para encontrar um corte s que pelo menos metade das bordas cortadas

Question

Deixe $ g $ ser um gráfico não direcionado.

Encontre um algoritmo ganancioso que encontre um corte $ s $ que pelo menos metade das bordas cortadas.

Eu tentei pensar em algo como escolher o vértice com o mais alto grau, adicioná-lo para $ s $ , removê-lo do gráfico e, em seguida, repita este processo até Eu terminei.

No entanto, isso nada mais é do que um palpite e eu não poderia provar isso.

Eu tentei pensar no problema de outra maneira - removendo não mais da metade das bordas no gráfico até obter um gráfico bipartido, mas encontrar os ciclos leva muito tempo.

Soluções on-line para este problema incluídas usando algoritmos aleatórios - algo que não aprendemos no curso onde recebi essa pergunta. Outras soluções não estavam claras para mim (incluindo uma que foi postada neste site), ou parecia muito complicada para o nível do curso.

Alguém poderia fornecer orientação por favor?

Answer 1

Liste os vértices em alguma ordem, $ v_1, \ lDOTs, v_n $ .Coloque $ v_1 $ em um lado arbitrário do corte.Para cada um dos vértices $ v_2, \ ldots, v_n $ , coloque-o na lateral do corte que maximizou o número de bordas cortadas (contando apenas bordas envolvendo vértices quejá foram processados).Como há apenas dois lados, cada vez que você corta pelo menos metade das bordas.