五千年(敝帚自珍)

主题:【原创】逐鹿蓝天(七) -- holycow

共:💬65 🌺368
全看分页树展 · 主题 跟帖
家园 提个问题

如果让这n条航线都飞同一个枢纽,你能服务[n*(n+1)/2]个城市对

是否应该是[n*(n-1)/2]个城市对。

设每一个城市为图中一个节点,对于任意两个城市x和y,枢纽城市o,那么如果由x经o到y有航线(反方向一样),我们可以认为在图中x和y节点间直接存在边,再加上由o到各城市节点的边,既每一对节点间都有边相连,这是一个完全图。完全图的边数为n*(n-1)/2。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河