来自离散数学-图论

Question

描述一个图模型，该模型表示派对中的每个人是否知道该派对中每个其他人的姓名。边应该是有向的还是无向的？应该允许多个边吗？应该允许循环吗？

Answer 1

边缘应该是定向的，因为约翰可能知道玛丽的名字，但玛丽不知道约翰的名字。如果约翰是一个小镇的普通公民，而玛丽是那个小镇的镇长，就可能发生这种情况。

不应该允许从一个人到另一个人的多个边，因为一个人要么认识另一个人，要么不认识。弧线的存在或不存在足以表示这一或或现实。这也表明该图不需要加权。

应该允许任何长度的循环，包括长度1。据推测，大多数人都知道自己的名字，尽管这并不一定能保证(假设一个参加派对的人患有完全的逆行性健忘症)。因此，许多人都会有自我循环。此外，成对的人很可能知道彼此的名字，所以成对的人之间可能会出现循环。更大的周期也是可能的。