Обход графа, может быть, другой тип математики?

Question

Допустим, у вас есть набор / список / набор чисел: [1,3,7,13,21,19] (порядок не имеет значения). Допустим, по несущественным причинам вы запускаете их через функцию и получаете следующие пары: (1, 13), (1, 19), (1, 21), (3,19), (7, 3), (7,13), (7,19), (21, 13), (21 , 19). Опять порядок не имеет значения. Мой вопрос включает в себя следующую часть: как узнать минимальное количество чисел, которые могут быть частью пары без повторения? Для этой конкретной последовательности это все шесть. Для [1,4,2] парами являются (1,4), (1,2), (2,4). В этом случае любое из чисел может быть исключено, так как все они попарно, но каждое из них повторяется, поэтому будет 2 (что 2 не имеет значения). На первый взгляд это кажется проблемой обхода графа - числа - это узлы, ребра пар. Есть ли какая-то часть математики, которая занимается этим? У меня нет проблем с написанием алгоритма обхода, мне просто интересно, есть ли решение с меньшей сложностью по времени. Спасибо!

Answer 1

На случай, если кому-то все равно в будущем, решение называется алгоритмом цветения.

Answer 2

Если вы действительно намеревались найти минимальную сумму, ответ будет 0, потому что вам вообще не нужно использовать какое-либо число.

Полагаю, вы хотели написать "максимальное количество чисел".

Если я правильно понимаю вашу проблему, похоже, мы можем перевести ее на следующую проблему: Учитывая набор из n чисел (1, .., n), какое максимальное количество чисел я могу использовать, чтобы разделить набор на пары, где каждое число может появиться только один раз.

Ответ на этот вопрос:

• когда n = 2k f (n) = 2k для k> = 0
• когда n = 2k + 1 f (n) = 2k для k> = 0

Я объясню, используя индукцию.

1. если n = 0, то мы можем использовать не более 0 чисел для создания пар.
2. если n = 2 (набор может быть [1,2]), тогда мы можем использовать оба числа для создать одну пару (1,2)
3. Предположение: если n = 2k, давайте предположим, что мы можем использовать все 2k числа для создания 2k пар, и докажем с помощью индукции, что мы можем использовать 2k + 2 числа для n = 2k + 2.
4. Доказательство: если n = 2k + 2, [1,2, .., k, .., 2k, 2k + 1,2k + 2], мы можем создать k пар, используя 2k чисел (из нашего предположения). без ограничения общности, допустим, что парами являются (1,2), (3,4), .., (2k-1,2k). мы можем видеть, что у нас все еще есть два числа [2k + 1, 2k + 2], которые мы не использовали, и поэтому мы можем создать пару из двух из них, что означает, что мы использовали 2k + 2 числа.

Вы можете самостоятельно доказать случай, когда n нечетно.