离散数学第图的基本概念.pptx

离散数学第图的基本概念;4。边得重数 具有相同始点和终点得边称为平行边,平行边得 条数称为边得重数。 5。n 阶图 具有n个结点得图称为n阶图,具有n个结点和m 条边得图称为(n,m)图 6。结点得度数 图中与某结点v相关联得边数(自回路算两条边), 称为该结点得度数,记作deg(v)。其中以v为始点得边 数称为出度deg+(v),以v为终点得边数成为入度deg-(v) 因此有 图G中结点得最大、最小度数记做Δ(G)、δ(G);二、图得基本概念与握手定理 1。握手定理 图G中所有结点得度数之和等于边数得二倍。 [推论1] 在任何图中,度数为奇数得结点数必为偶数。 [推论2] 在有向图中,所有结点得入度之和等于所有结点得出度之和。 例题1: 已知图G中有1个1度结点,2个2度结点,3个3度结 点,4个4度结点,则G得边数就是 。 解: ;例题2: 设图G=V,E,则下列结论成立得就是 。 A) B) C) D) 例题3: 设简单连通无向图G有12条边,G中有2个1度结点, 2个2度结点,3个4度结点,其余结点度数为3,求G中 有多少个结点。试作一个满足该条件得简单无向图。 解:设G中有x个结点,则3度得结点有x-7。 根据握手定理有,;解得 ,故G中有9个结点。 满足条件得图如下: 2。简单图 不含平行边和环(自回路)得图称为简单图。 在简单图中,任何结点得度数都小于等于n-1。这 就是判断一个度数序列能否构成简单图得主要依据。 3。二部图 若将无向图G得结点集分为两部分,而每一部分中 任何两个结点之间都没有边相连,则G称为二部图。;4。完全图 每一对结点之间都有边相连得无向简单图称为无 向完全图,每一对结点之间都有方向相反得两条边相 连得有向简单图称为有向完全图。 具有n个结点得无向完全图Kn得边数为: 例题4: 设图G就是有n个结点得无向完全图,则G得边数为 。 A) n(n-1) B) n(n+1) C) D);5。正则图 若无向简单图G中每个结点得度数都为k,则G称 为k-正则图。 6。赋权图 若图G中得每一条边都有一个表示长度得实数, 则图G称为赋权图或网络。图G为无向图称为无向赋权 图,图G为有向图称为有向赋权图。 7。补图 由图G中得所有结点和构成完全图需添加得边所组成得图称为G得补图,记作 。;例题5: 已知图得结点集 以及图G和图D得 边集合分别为: 试作图G和图D,写出各结点得度数,回答图G、图D 就是简单图还就是多重图？ ?解:a d a d ? ? ? b c b c 图G 图D;图G: 图D: 图G不就是简单无向图,图D就是简单有向图。 8、子图 1。已知图G=V,E,如果 则G’=V’,E’称为G得子图。 2。如果 ,则称G’为G得真子图。 3。如果 ,则称G’为G得生成子图。;三、图得同构 如果图G中得结点集V与图G’中得结点集V’具有 一一对应得关系,并且对应得边都具有相同得重数, 则称G与G’同构,记作 。 因此,两图同构必须满足下列条件: ⑴结点数相同, ⑵边数相同, ⑶度数相同得结点数相同。 上述条件就是两图同构得必要条件,但不就是充分条 件,也就就是说,两个图即使满足上述条件也不一定同