第七章图与网络(1) 第七章:图与网络(1) 环:一条边两个端点相同 1.引例(P256) 多重边:两个点之间多于一条边 1.图与网络的基本概念: 简单图:无环,无多重边 边:两点间没有箭头的连线两点间有箭头的连线称为弧小多重图:无环,有多重边 无向图:由点和边构成的,无向图简称为图 次:端点的边的数目 有向图:由点和弧构成的 孤立点:次为0的点 端点:一条边vV2,V,V2称为边的端点 悬挂点:次为1的点 相邻:一条边V1V2,V1,V称为相鄰 悬挂边:与悬挂点关联边 关联边:一条边vv,称为端点V,V2的关联边 链 联通图:图中任意两个点至少 链的中间点 有一条链 初等链:链中的点都不相同 联通分图:不联通图,每个联通部分 圈:一条链首尾相同 图的支承?子图:包括图的全部顶点 初等圈:圈中的点都不相同 并且包括图的部分边 简单圈:链中的边都不相同 运学 熊中描教运筹学 熊中楷教授 第七章 图与网络（1） 第七章：图与网络（1） 1．引例（P256） 1. 图与网络的基本概念： 边：两点间没有箭头的连线，两点间有箭头的连线称为弧。 无向图：由点和边构成的，无向图简称为图。 有向图：由点和弧构成的 端点：一条边V1V2, V1,V2 称为边的端点 相邻：一条边V1V2, V1,V2 称为相鄰 关联边：一条边V1V2, 称为端点V1,V2的关联边 环：一条边两个端点相同 多重边：两个点之间多于一条边 简单图：无环，无多重边 多重图：无环，有多重边 次：端点的边的数目 孤立点：次为0的点 悬挂点：次为1的点 悬挂边：与悬挂点关联边 链： 链的中间点： 初等链：链中的点都不相同 圈：一条链首尾相同 初等圈：圈中的点都不相同 简单圈：链中的边都不相同 联通图：图中任意两个点至少 有一条链 联通分图：不联通图，每个联通部分 图的支承?子图：包括图的全部顶点 并且包括图的部分边