图与网络模型及方法l图与子图 l图的连通与割集 l树与支撑树 l最小树 l最短有向路 l最大流 l最小费用流 l最大对集l 图与网络 无向图的基本概念 网络的基本概念 l 关联矩阵和邻接矩阵 关联矩阵 邻接矩阵 主要结论 l 子图 绪论 l 图论起源于18 世纪。 l 第一篇图论论文是瑞士数学家欧拉于1736 年发表 的“哥尼斯堡的七座桥”。 l 1847 年，克希霍夫为了给出电网络方程而引进了 “树”的概念。 l 1857年，凯莱在计数烷n 2n+2 C H 的同分异构物 时，也发现了“树”。 l 哈密尔顿于1859 年提 l 出“周游世界”游戏，用图论的术语，就是如何找 出一个连通图中的生成圈绪论 l近几十年来，由于计算机技术和科学的飞 速发展，大大地促进了图论研究和应用， 图论的理论和方法已经渗透到物理、化学 、通讯科学、建筑学、运筹学，生物遗传 学、心理学、经济学、社会学等学科中。绪论 l 图论中所谓的“图”是指某类具体事物和这些事物 之间的联系。 l 如果我们用点表示这些具体事物，用连接两点的 线段（直的或曲的）表示两个事物的特定的联系 ，就得到了描述这个“图”的几何形象。
