西安电子科技大学店S6.2.1路径和回路的定义软件学院最「定理！在一个具有Ⅱ个结点的图中，如果从结点vi到Vk存在一条路径，则从结点yi到结点Wis必存在一条长度小于n的基本路径。证明：设从结点V到结点V存在一条路径，该路径上结点的序列为Vi…ViVk。如果这条路径中有p条边，则该路径上必有p+1个结点。若p≥n，则结点数大于等于n+1。根据鸽巢原理，必存在结点Vs，它在序列中不止一次出现，即该路径必有结点序列vivsvsvk。从该路径中去掉从vs到vs之间出现的这些边，所得仍是从v到vk得一条路径，但此路径比原来路径的边数要少。如此重复进行下去，直到删除所有重复的结点，从而得到一条基本路径。由于基本路径的长度等于该路径上的结点数减1，又图G中共有n个结点，故基本路径长度小于等于n-1。西安电子科技大学 §6.2.1 路径和回路的定义 软件学院 证明：设从结点vj到结点vk存在一条路径，该路径上结点的序列为 vj . vi .vk。如果这条路径中有p条边，则该路径上必有p+1个结点。 若p≥n，则结点数大于等于n+1。根据鸽巢原理，必存在结点vs，它 在序列中不止一次出现，即该路径必有结点序列vj .vs .vs.vk。从 该路径中去掉从vs到vs之间出现的这些边，所得仍是从vj到vk得一条路 径，但此路径比原来路径的边数要少。 如此重复进行下去，直到删除所有重复的结点，从而得到一条基本 路径。由于基本路径的长度等于该路径上的结点数减1，又图G中共有n 个结点，故基本路径长度小于等于n-1