定义87 多重边/多重图 若图G=(v,E)中,连接两个顶点之间的边不止一条 (这些边称为多重边),则图G称为多重图 图 无自环的非多重图。 零图 边集为空集的图 平风图 只有一个顶点的图。 完全图 若G中每两个顶点之间恰有一条边。n个顶点完全图 记为Kn
定义8.7 多重边 / 多重图： 若图G=(V, E)中，连接两个顶点之间的边不止一条 （这些边称为多重边），则图 G称为多重图。 简单图： 无自环的非多重图。 零图： 边集为空集的图。 平凡图： 只有一个顶点的图。 完全图： 若 G中每两个顶点之间恰有一条边。 n个顶点完全图 记为 Kn
>3)例题 下列各组数中,哪些能构成无向图的度数列? 哪些能构成无向简单图的度数列? (1)1,1,1,2,3 (2)2,2,2,2,2 (3)3,3,3,3 (4)1,2,3,4,5 (5)1,3,3,3
3）例题 下列各组数中，哪些能构成无向图的度数列？ 哪些能构成无向简单图的度数列？ （1）1，1，1，2，3 （2）2，2，2，2，2 （3）3，3，3，3 （4）1，2，3，4，5 （5）1，3，3，3
>解答:(1),(2),(3)和(5)能构成无向 图的度数列,除(5)外又都能构成无向简单图的 度数列 分析 >1)数列能构成无向图台∑=d(v)=为偶数; 2)假设(5)能构成无向简单图的度数列。 d)=1,c(v2)=c)=v4=3,则v只能与v2, v4之一相邻,设v与v2相邻,这样除v2能达到 3度外,和v都不能达到3度,导致矛盾
解答：（ 1），（ 2），（ 3）和（ 5）能构成无向 图的度数列，除（ 5）外又都能构成无向简单图的 度数列。 分析： 1）数列能构成无向图 i=1n d(vi)=为偶数； 2）假设（ 5）能构成无向简单图的度数列。 d(v 1)=1 ， d(v2)= d(v3)= d(v4)=3 ， 则 v 1只能与 v2 ， v3 ， v4之一相邻，设 v 1 与 v2相邻，这样除 v2能达到 3度外， v3 和 v4都不能达到 3度，导致矛盾
>4)可图化与可简单图化 >无向图G=,E,V={v,v2……,vn},称(d, ,d(v))为G的度数烈。 >给出非负整数列d=(dl,d2……,dn),若存在以 n}为顶点集的图,以d为度数列, 则称是可图化的。 >若存在以V={vnv ,vn}为顶点集的简单图, 以d为度数列,则称d是可单图化的。 题 2…,d)在什么条件下是可图化 在什么 下是可筒单图化的?
4）可图化与可简单图化 无向图G=(V, E), V={ v1, v2, ……, vn }，称（ d(v1), d(v2), ……, d(vn) ）为G的度数列。 给出非负整数列d= ( d1, d2, ……, dn ), 若存在以 V={ v1, v2, ……, vn }为顶点集的图，以d为度数列， 则称d是可图化的。 若存在以V={ v1, v2, ……, vn }为顶点集的简单图， 以d为度数列，则称d是可简单图化的。 问题：d=(d1, d2, ……, dn)在什么条件下是可图化， 在什么条件下是可简单图化的？
>定理A (d1,d2……,adn)(10,i=1,2,…,n)是可 图化的当且仅当 ∑d1=0(mod2)
定理A d= ( d1, d2, ……, dn )（di0, i=1, 2, ……, n）是可 图化的当且仅当 1 0(m od 2) n i i d