Построить k-ребро связного подграфа

Question

Предположим, у меня есть граф сетки с размером mx n.Количество вершин равно mn, а количество ребер - 2mn-mn.Как построить связанный подграф с k-ребром?Я знаю, так как k - это число ребер, то mn-1 <= k <= 2mn-mn.Если k = mn-1, то подграф является остовным деревом.Если k = 2mn-mn, то подграф является самим графом сетки. </p>

Мой подход состоит в том, чтобы сначала построить остовное дерево, используя алгоритм Крускала (чтобы убедиться, что оно соединено), и добавить ребро k в это остовное дерево.,Мне интересно, есть ли другой способ сделать это?

Answer 1

Существует множество охватывающих подграфов типа графа решетчатой ​​сетки, который вас интересует. Если вам нужен только один из них, вы можете подключить каждую вершину к ее горизонтальному соседу (соседям) и подключить крайний левый столбец (таким образом, это выглядело бы как гребень. Например,

*-*-*-*-*
|
*-*-*-*-*
|
*-*-*-*-*
|
*-*-*-*-*

Это только один из многих возможных охватывающих подграфов.

Завершите, добавив необходимые ребра, чтобы добраться до к. Ребронабор может быть описан без генерации, как объяснено в комментариях.