离散数学英文DMAv7-11.345.ppt

[定义]生成树：无向简单图Ｇ＝（Ｖ，Ｅ）的生成子图Ｔ是树，则称Ｔ为Ｇ的生成树/spanning tree。 Ｔ＝（Ｖ，Ｅ’）, Ｅ’?Ｅ [定理一]： 无向简单图Ｇ＝（Ｖ，Ｅ）存在生成树的充要条件是Ｇ是连通的。 证明: 必要性：Ｔ是生成子图，包含Ｇ的所有顶点，Ｔ是树，Ｔ连通，则Ｇ连通。 充分性：若Ｇ是连通的, (1）若G无回路，则Ｇ本身是树，即生成树。 (2) 若存在回路，去掉回路中任一边，不影响连通性，也不减少顶点. 所有回路都移去一条边，剩下的子图包含所有顶点，又是无回路的连通图，即为生成树。 注： ① 移去边时可随意，故生成树不唯一。 ② 生成树是Ｇ的最小连通生成子图，若将Ｇ＝（Ｖ，Ｅ）看成是各顶点间的通讯联络图，则生成树Ｔ＝（Ｖ，Ｅ’）即为各顶点间直接或间接联络的最小通讯联络图。 IP Multicasting 目前，使用得最为广泛的组播技术是IP Multicast。IP组播技术是一种为优化使用网络资源而产生的技术，通常用于多点工作方式下的应用程序中，它是标准IP网络层协议技术的一个扩展。　　从Steve Deering于1989年提出的IETF的RFC1112Host Extension for IP Multicast中的定义我们可以得知：IP组播的核心思想是--通过一个IP地址向一组主机发送数据（UDP包）。发送者仅仅向一个组地址发送信息，接收者只需加入到这个分组就可以接收信息，所有的接收者接收的是同一个数据流，组中成员是动态的，可以根据自己的意愿随时随意加入或退出。每一台主机都可以同时加入到多个组中，每一个组播地址可以在不同的端口或者不同的套接字（Socket）上有多个数据流，同时许多实际应用可以共享一个组地址。IP组播技术可以有效地避免重复发送可能引起的广播风暴，并且能够突破路由器的限制，将数据包传送到其它网段。 Depth-first search深度优先 Build a spanning tree for a connected simple graph using a depth-first search. Depth-first search深度优先 Tree edges back edges a b c e d f g h k j i Breadth-first search广度优先 Produce a spanning tree of a simple graph by the use of a breadth-first search. Breadth-first search广度优先 a b c e d f g h k j i l m Backtracking 回溯法 Graph Colorings The n-Queens Problem In directed graphs Web spiders What is a Spider or Search Engine Spider? Description: A Spider or Search Engine Spider is a program that automatically traverses the Web and requests documents from URLs. A spider usually starts from a historical list of URLs and retrieves referenced documents. As it visits new Internet websites it checks to see if the site is already listed in its database. If the site is already listed it usually updates any changes it finds. Spiders are also commonly known as Robots or Crawlers. Other names sometimes used: Webwalkers, Wanderers, or *Worms 11.5 Minimal Spanning Trees （最小生成树） Weighted graph（加权图） Definition:a weighted graph is a graph for which each edge is labeled with a numerical value called its weight（权值） . Example 1 Example 2 E 4