MathLabs

第3题

一个社交网络有 20192019 名用户，其中一些用户成对为朋友（朋友关系是对称的）。以下事件可以反复发生，每次一个：三名用户 AA、BB、CC 满足 AA 同时与 BB 和 CC 是朋友，但 BB 与 CC 不是朋友；改变他们的朋友关系，使得 BB 与 CC 现在成为朋友，但 AA 不再与 BB 是朋友，也不再与 CC 是朋友。其他所有朋友关系保持不变。最初，10101010 名用户各有 10091009 个朋友，10091009 名用户各有 10101010 个朋友。证明存在一系列这样的事件，使得之后每名用户至多与另一名用户是朋友。
第 1/6 步：把朋友关系建模为图
上一步下一步
G=(V,E),∣V∣=2019,toggle(A,B,C): AB,AC∈E, BC∉E ⟼ E′=(E∖{AB,AC})∪{BC}G=(V,E),\quad |V|=2019,\qquad \text{toggle}(A,B,C):\ AB,AC\in E,\ BC\notin E\ \longmapsto\ E'=(E\setminus\{AB,AC\})\cup\{BC\}
详细分析

设 G=(V,E)G=(V,E) 为该图，其中 VV 是 20192019 名用户，EE 是朋友对。把所描述的变化称为在 A,B,CA,B,C 处的一次切换：它要求边 ABAB 与 ACAC 存在而 BCBC 不存在，并把 EE 替换为 E′=(E∖{AB,AC})∪{BC}E'=(E\setminus\{AB,AC\})\cup\{BC\}。目标就变成了到达每个顶点的度数至多为 11 的图。