Как бы вы решили проблему рукопожатия теории диаграмм в python?

Question

Я закончил колледж в прошлом году со степенью в области психологии, но я также принял много математики для удовольствия. Недавно я получил книгу «Теория вступительных графиков» Гэри Шартрана, чтобы освежить мою математику и повеселиться. Вот упражнение из книги, что я нахожу особенно оглупления:

Предположим, что вы и ваш муж присутствовал вечеринка с тремя другими замуж пары. Несколько рукопожатий заняли место. Никто не пожал руку самому себе (или ее) или его (или ее) супруг, и никто не пожал руку тому же человеку более одного раза. После все квитирование было завершено, Предположите, что вы спросили каждого человека, , включая вашего мужа, сколько рук он или она потрясены. Каждый человек дал другой ответ. a) Сколько рук вы встряхнули? б) Сколько рук сделал твой муж трясет?

Теперь я размышлял об этом некоторое время и пытался нарисовать примеры графов, которые могли бы проиллюстрировать решение, но я прихожу с пустыми руками. Моя логика такова: на графике есть 8 разных вершин, а 7 из них имеют разную степень. Поэтому значения для степеней должны быть равны 0, 1, 2, 3, 4, 5, 6 и x. Количество степеней для одной супружеской пары (0, 6). Поскольку все графики имеют четное число нечетных вершин, x должно быть либо 5, 3, либо 1.

Каково ваше решение этой проблемы? И, если бы вы могли решить это в python, как бы вы это сделали?

(python is fun.) 

Cheers.

Answer 1

Хорошая вещь об этой проблеме вы действительно не нужно, чтобы решить график, если вы не хочу. Вы на самом деле очень близки. Вы поняли, что одна пара имеет множественности (6,0). Остальные вершины не отличаются друг от друга по отношению к первой паре, и у вас есть те же правила для этого подграфа. Таким образом, кратности субграфа составляют 0,1,2,3,4, x и существует пара с кратностями (4,0).Эта пара имеет кратности (5,1) в полном графике. Так как вы повторяете этот процесс, вы завершите, что ваши пары имеют множественности (6,0), (5,1), (4,2), (3,3). И, конечно же, вы должны иметь множественность x = 3, чтобы ваш муж тряс 3 руки.

Answer 2

Я думаю, что этот список смежности представляет собой решение:

1 -> {} 
2 -> {3, 4, 5, 6, 7, 8} 
3 -> {2, 5, 6, 7, 8} 
4 -> {2} 
5 -> {2, 3, 7, 8} 
6 -> {2, 3} 
7 -> {2, 3, 5} 
8 -> {2, 3, 5}

Заметим, что каждая вершина даже женатый на вершине один меньше, чем он сам. Вы - 8.

Я как бы интуитивно понял решение. Подумал об этом в течение нескольких минут, а затем понял, что каждая пара должна иметь общую степень 6, чтобы это работало. Тогда просто выяснили, как это должно работать.

Что Стивен говорит, так это то, что вы указали, что должна быть пара с градусами (0,6) и всеми остальными (1, 2, 3, 4, 5, x). Теперь рассмотрим подграф, созданный удалением этой первой пары. «Муж» не тряхнул чью-либо руку, поэтому он не будет иметь никакого эффекта. «Жена» потрясла всех, поэтому вам нужно вычесть 1 из всех других степеней. Итак, у вас есть график с (0, 1, 2, 3, 4, x-1), где применяются те же правила. Отсюда вы можете использовать тот же процесс мышления, который вы использовали для определения существования пары (0,6), чтобы выяснить существование пары (1,5). Это будет фактически (0,4), но вам нужно добавить 1 в конец, потому что это подграф, не считая первую пару.

Просто продолжайте повторять до тех пор, пока вы до кого-то, а термин х, и вы должны получить х = 3.