什么是赋权图？

Question

如题所述

Answer 1

每一个连通分支都是一个单独的图，而图的奇度顶点是偶数个，所以图G中的两个奇度顶点必在同一连通分支内，所以这两个奇度顶点必然连通。

设G=(V，E)为二分图，V=XUY，且X中的任一顶点与Y中每一个顶点均有且仅有唯一的一条边相连，则称G为完全二分图或完全偶图。直观地讲，对于平面上的n个点，把其中的一些点对用曲线或直线连接起来，不考虑点的位置与连线曲直长短，这样形成的一个关系结构就是一个图。记成G=(V，E)，V是以上述点为元素的顶点集，E是以上述连线为元素的边集。赋权图是指每条边都有一个(或多个)实数对应的图，这个(些)实数称为这条边的权(每条边可以具有多个权)。

赋权图在实际问题中非常有用。根据不同的实际情况，权数的含义可以各不相同。例如，可用权数代表两地之间的实际距离或行车时间，也可用权数代表某工序所需的加工时间等。