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

Question

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

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

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

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

(python is fun.)

Приветствие.

Answer 1

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

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