两类图的带宽和上界

设Ｇ是有ｎ个顶点的简单图．ｆ：Ｖ（Ｇ）→｛１，２，…，ｎ｝是双射。定义Ｓ（Ｇ）＝ｍｉｎＳｆ（Ｇ），其中Ｓｆ（Ｇ）＝∑／∈Ｅ｜ｆ（ｕ）－ｆ（ｖ）｜，称Ｓ（Ｇ）为Ｇ的带宽和，得到了树及无三角形图的带宽和上界。