系统分析师-总复习资料

系统分析员考试复习部分

PMSJJJ(潘梅森)

JavaBean组件模型特点：

① JavaBean组件模型是面向向客户端的组件模型； ② 它支持可移植和可重用的Java组件的开发；

③ JavaBean组件可以工作于任何Java程序应用开发工具中； ④ JavaBean组件总是在程序运行时被实例化； ⑤ JavaBean支持可视化及非可视化的组件模型。

Enterprise JavaBean（EJB）组件模型特点：

① EJB是面向服务端的JavaBean组件模型。它是一种特殊的、非可视化的

JavaBean，运行在服务器上；

② EJB组件模型主要包括EJB Server、EJB Container、EJB Object发及诸多相关

特性；

③ EJB Server提供EJB组件运行环境，它负责管理和协调应用程序资源的分配； ④ EJB Container是用于管理EJB Object的设备，它负责EJB对象的生命周期的

管理，实现EJB对象的安全性，协调分布式事务处理，并负责EJB对象的上下文切换；

⑤ EJB规范提供了这样的一种机制，你可以通过在运行时设置相应的属性值来定

义每一个EJB对象的运行状态；

⑥ Deployment Descriptor被用于设置EJB对象的运行状态。

JSP胜过servlet的关键的优点：

① JSP是以显示为中心的，它为Web显示开发人员提供了更加自然的开发模式； ② JSP使人们把显示和内容分隔开成为可能； ③ JSP可以帮助组织Web应用物理状况。

现代的企业计算解决方案除了企业的业务逻辑外，还需要提供对8种基本服务的支持：

① 命名/目录服务（Naming and Directory Service）； ② 数据访问服务（Data Access Service）；

③ 分布式对象服务（Distributed Object service）； ④ 企业管理服务（Enterprise Management Service）； ⑤ 事务处理服务（Transaction Processing Service）； ⑥ 消息报务（Messaging Service）； ⑦ 安全服务（Security Service）； ⑧ Web服务（Web Service）。

J2EE的重要组成部分： ① JDBC ② EJB

③ Java RMI ④ Java IDL

1

⑤ JNDI

⑥ JMAPI(JAVA Management) ⑦ JMS ⑧ JTS

⑨ JSA(IAVA Security API)

RMI和RPC的区别：

RMI是面向对象的，而RPC是基于过程调用的。由于RMI面向对象的特性，RMI调用可以直接将对象在调用的两端之间进行传递，不但可以传送数据，而且还可以传递方法，扩展了RMI的使用；另外RMI还支持两个RMI对象之间的方法回调（callback）。

XML和HTML的主要区别：

① XML是元标记语言，用户可以自己定义所需要的标记； ② XML描述的是结构和语义；

XML技术和JSP技术集成的方案：

① 以XML技术为前端显示层或者是后端数据层，JSP/JMS/Servlet/EJB等J2EE技

术为中间处理层；JSP等J2EE技术接受客户端的请求，从后端数据层中获得数据，经过加工处理之后，以XML/XSL/XSLT/的形式返回客户端。在这个模型，JSP技术充当了逻辑控制、计算处理的角色，而XML充当了显示数据、存储数据、传递信息流的功能；

② Tag Libraries在JSP程序中的大规模应用。

XML与JSP技术联合的优越性： ① 简单性 ② 可扩展性 ③ 便携性 ④ 多样性

JDBC执行步骤（在JSP中）

<%@ page import=\ contentType=\

ASP加ODBC执行步骤（在ASP中） <%@ Language=VBScript %> <%

set conn1 = Server.CreateObject(\?建立连接 conn1.open \ ?打开连接

set rsCheck1 = Server.CreateObject(\?建立记录 rsCheck1.CursorType = adOpenStatic rscheck1.activeconnection = conn1 if Request(\ da=Request(\ dim nd,nj,bj,xm,bh,pj,jj nd=cstr(year(date))+\年度\ if month(date)<7 then nd=nd+\第一学期\ else

nd=nd+\第二学期\ end if

nj=session(\ bj=session(\ xm=session(\ bh=session(\ pj=false

rsCheck1.Source=\from result where 班号='\& bh & \and 班级='\& bj & \姓名='\ rsCheck1.open

rsCheck1.Source=\into result(年度,年级,班级,姓名,班号,答案,评卷) values('\ & \

3

& \

rsCheck1.open end if

Response.write \align='center'>

重用一组对象常常称为对象池化。 SAX（Simple API for XML）：是事件驱动模型。 DOM（Document Object Model）：是文档对象模型。 LDAP（Lightweight Directory Access Protocol）：轻量目录访问协议。

DOM要装入整个文档并对该文档进行解析会很慢且占用大量内存。SAX是工作在数据流之上，在数据流经过时对其进行处理。它消除了在内存中构建数据树的需要，但不允许开发者实际更改原始文档中的数据。

OOA的主要优点：

① 加强了对问题域和系统责任和理解；

② 改进与分析有关的各类人员之间的交流； ③ 对需求的变化具有较强的适应性； ④ 支持软件复用；

⑤ 贯穿软件生命周期全过程的一致性； ⑥ 实用性；

⑦ 有有利于用户的参与。

OOA过程包括以下主要活动： ① 发现对象，定义它们的类；

② 识别对象的内部特征，定义属性，定义服务； ③ 识别对象的外部关系； ④ 划分主题，建立主题图； ⑤ 定义use case，建立交互图； ⑥ 建立详细说明； ⑦ 原型开发。

把建立原型系统做为一种可能采取的策略的主要理由如下：

① 由于人类的认识能力的局限，不能预先指定所有要求； ② 在用户和系统分析员之间存在固有的通信鸿沟；

③ 用户需要一个“活的”系统模型，以便获得实践经验； ④ 在开发过程中重复和反复是必要的和不可避免的； ⑤ 目前有快速建立原型系统的工具可供选用。

原型法的主要优点：

系统开发人员与用户的交流直接，消除了开发人员与用户之间的通信障碍，

4

可以尽早地获得正确而完整的需求。开发过程简单，在一定程度上能适应需求的变化，设计与编程更快速、更准确，开发效率也显著提高，而且提高了软件质量，总开发费用也会减少。

面向对象方法的优点：

① 按照人类的自然思维方式，面对客观世界建立软件系统模型； ② 对需求变化的适应性； ③ 支持软件复用； ④ 可维护性好。

一个可复用构件应具备的条件是： ① 独立性； ② 完整性； ③ 可标识性； ④ 一般性； ⑤ 适应性； ⑥ 可靠性； ⑦ 标准化。

XML和CORBA、DCOM这些技术并不冲突：XML可以为它们做传递信息、资料桥梁；XML使用方便；XML是纯文本形式，阅读方便，可用编辑器直接编写，可以直接透过HTTP或SMTP等通信协议传送，开放式标准，对数据的描述，有有进行数据挖掘，编排的便利。但是处理速度较慢。

SAX (Simple API for XML) 和 DOM (Document Object Model) 都是为了让程序员不用写一个解析器就可以访问他们的资料信息。通过利用XML 1.0格式保存信息,以及使用SAX或者DOM APIs你的程序可以使用任何解析器。这是因为使用他们所喜爱的语言开发解析器的开发者必须实现SAX和DOM APIs。 SAX和DOM APIs 对多种语言中都可以实现(Java, C++, Perl, Python, 其它...)。 所以SAX 和 DOM都是为了同样的目的而存在,这就是使用户可以利用任何编程语言访问存入XML文档中的信息(要有一个那种编程语言的解析器)。虽然他们在提供给你访问信息的方法上大不相同。

什么是DOM?

DOM 可以让你以分层次对象模型来访问储存在XML文档中的信息。DOM生成一棵节点树(以XML文档的结构和信息为基础)你可以通过这棵树来访问你的信息。

5

全关系EA?{?a,b?a,b?A}?A?A

恒等关系IA?{?a,a?a?A}，MI是单位矩阵. 3. 关系的运算

?关系的集合运算，有并、交、补、差和对称差. ?复合关系

R?R1?R2?{?a,c??b使?a,b??R1??b,c??R2}，有

复合关系矩阵： ?逆关系R?1MR?MR1?MR2(布尔运算)，有结合律：(R?S)?T＝R?(S?T)

R?1?{?y,x??x,y??R}，M?MTR，(R?S)=S?R.

－1－1－1

4. 关系的性质

?自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为1；关系图的每个结点

都有自回路.

?反自反性 ?x?A,?x,x??R；矩阵M都没有自回路.

?对称性 若?x,y??R，则?y,x??R；矩阵M图中有向弧成对出现,方向相反.

?

反对称性 若?x,y??R且?y,x??R，则x=y或若?x,y??R,x?y，则

RRR的主对角线元素全为0；关系图的每个结点

是对称矩阵，即

rij?rji；关系

?y,x??R；矩阵M不出现对称元素.

?传递性 若?a,b??R且?b,c??R，则?a,c??R；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难. 可以证明：R是集合A上的二元关系，

(1)(1)R是自反的?IA?R; (2)R是反自反的?IA?R＝?; (3)R是对称的 ?R＝R－1； (4)R是反对称的?R?R－1?IA； (5)R是传递的?R?R?R.

关系的性质所具有的运算见表4－1.

表4－1 二元运算的并、交、补、差、逆、复合具有的性质表

运算 关系性质 自反性 反自反性 ? ? ? ? ? ? 对称性 ? ? ? ? ? ? ? 反对称性 传递性 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16

R R1?R2 R1?R2 R1－R2 R1?R2 IA ?

－1 ? ? ? ? ? ? 由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.?具有反自反性、对称性、反对称性和传递性。?是偏序关系.

关系性质的判定，可以用定义、关系矩阵或关系图.

传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；

5. 关系的闭包

设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R?表

示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。闭包的求法：

n 定理12：r(R)?R?IA；定理13：s(R)?R?R

?1t(R)?；定理14的推论：

?Ri?1i

6. 等价关系和偏序关系 极大(小)元、最大(小)元问题 ?等价关系和偏序关系是具有不同性质的两个关系.

??等价关系?对称性?自反性????传递性??反对称性???偏序关系

?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双

向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。

?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b?b?A?aRb}.

?偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若,?,则?R，此时，a到c的有向弧不画出.

确定任一子集的最大(小)元，极大(小)元. 极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 7. 函数 ?函数, 设f是集合A到B的二元关系，?a?A,?b?B,且?f，且Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系.

集合A×B的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.

二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. ?函数的类型

单射 若a1?a2?f(a1)?f(a2)

满射 f(A)=B. 即?y?B,?x?A,使得y?f(x) 双射 单射且满射. ?

复合函数f:A?B,g:B?C,则f?g:A?C,即f?g(x)?g(f(x)). 复合成立的条

件是：Ran(f)?Dom(g)

17

一般f?g?g?f，但(f?g)?h?f?(g?h)

复合函数的性质：

如果f,g都是单射的，则f?g是单射的； 如果f,g都是满射的，则f?g是满射的； 如果f,g都是双射的，则f?g是双射的； 如果f,g是单射的，则f是单射的； 如果f,g是满射的，则g是满射的；

如果f?,g是双射的，则f是单射的，g是满射的. ?反函数 若f：A?B是双射，则有反函数f－1：B?A

f?1?{?b,a?b?B,f(a)?b,a?A}，(f?g)?1?g?1?f?1,(f?1)?1?f

二、实例

例4.1 设集合A＝{a,b},R是P(A)上的包含关系，写出R的表达式和关系矩阵. 解 用描述法表示；

R?{?x,y?x,y?P(A)?x?y}

用列举法表示：因为P(A)?{?,{a},{b},A}，所以

R?{??,??,??,{a}?,??,{b}?,??,A?,?{a},{a}?, ?{a},A?,?{b},{b}?,?{b},A?,?A,A?}MR关系矩阵：

?1??0??0??0?110010101??1?1??1??，关系图如图4－1

? ? {a}? ?{b} A ? 图4－1

例4.2 设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系

LA?{?x,y?x,y?A?x?y}

及其逆关系和关系矩阵.

解 IA?{?1,1?,?2,2?,?3,3?}

EA?{?1,2?,?1,3?,?2,1?,?2,3?,?3,1?,?3,2?,}?IA

?1LL?{?1,2?,?1,3?,?2,3?}A , LA的逆关系A?{?2,1?,?3,1?,?3,2?}

MLA

?0???0?0?1001??1?M0??

LA?1?0???1?1?0010??0?M0??. 有

LA?MTLA?1

例4.3 设集合A＝{2,3,4},B={4,6,7},C={8,9,12,14}. R1是由A到B的二元关系，R2是由B

到C的二元关系，定义如下：

R1?{?a,b?a是素数且a整除b}R2?{?b,c?b整除c},

求复合关系R1?R2，并用关系矩阵表示.

18

解 R1?{?2,4?,?2,6?,?3,6?},R2?{?4,8?,?4,12?,?6,12?,?7,14?}

因此 R1?R2＝{<2,8>,<2,12>,<3,12>}

42?1??3?04??0611070??0?M0??

84?1??6?07??0900012110140??0?1??

8900012110140??0?0??

MR1R2

MR?MR1?MR2?1???0?0?1100??1??0??0?0????00001100?2?1??3?00??1??(布尔运算)＝4?0例4.4 试判断图4－2中关系的性质：

? 1

? 1 ? 1

2?

? 3 2 ? ? 3 2 ? 3 ? (a) (b) (c) 图4－2 例4.4图

解 图4－2中(a)的关系在集合{1,2,3}上是对称的，因为结点1与2，1与3之间的有向

弧是成对出现且方向相反.

图4－2中(b)是反自反的，因为每个结点都没有自回路. 它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出R＝{<2,1>,<3,1>}, 满足R?R=??R.

图4－2中(c)的关系自反的，反对称的、但不是传递的. 因为2到1有边，1到3有边，但2到3没有边.

例4.5 设集合A＝{1,2,3,4,5},R是A上的关系，定义为

R＝{<1,2>,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}?IA

试判断R是 (1) A上的自反关系； (2) A上的对称关系；

(3) A上的反对称关系； (4) A上的传递关系. 1 ? 解 写出关系矩阵MR，作关系图，如图4－3.

5 ?11111?? ? ??01111??2 ??MR?00111 ???00011? 3 ? ? 4 ?? ?00001?,

图4－3 (1) (1) 因为?x?A,(x,x)?R(或MR的

19

主对角线元素皆为1，或关系图中每个结点都有自回路)，故R是自反关系.

(2) 因为(1,2)?R,而(2,1)?R(或MR不是对称矩阵，或关系图中每对结点都没有成对出

现的方向相反的弧)，故R不是对称关系.

(3) 因为(1,3)?R,且1?3,则(3,1)?R(或MR中当i?j时, mij=0, 则mji=1，或关系图中每

对结点没有成对的有向弧)，故R是反对称关系.

(4) 因为不难验证?a,b,c?A,(a,b)?R,(b,c)?R,有(a,c)?R(或关系图中

?a,b,c?A,a到b有有向弧,b到c有有向弧,a到c就有有向弧), 故R是传递关系.

例4.6 设集合A＝{a,b,c,d},定义R＝{,,,},求r(R),s(R),t(R). 解 求自反闭包，R不具有自反性，由自反性的定义，只需在R上添加IA，于是 r(R)=R?IA={,,,,,,，} 其中下画线者为添加元素.

s(R)=R?R?1=R?{,}={ ,,,,,} t(R)=R?R2?R3?R4=R?{,,,,}

={, ,,,,,,,} 例4.7 设集合A＝{a,b,c,d,e}，定义A上的二元关系 R1?{?a,b?,?b,a?,?d,e?,?e,d?}?IA

R2?{?a,b?,?b,a?,?b,b?,?c,c?,?d,d?,?d,e?} 判断R1，R2是否为等价关系？ 分析 判断等价关系，就是验证是否具有自反性、对称性和传递性.

解 写出R1的关系矩阵，

?1??1??0??0??01100001000010??0?0??1??1?

a ? b ? ? e c ? ? d MR1

001

图4－4

由关系矩阵可知，R1具有自反性和对称性. 由关系图(图4－4)可知它具有传递性，故R1是等价关系.

R2不是等价关系，因为(a,a)?R2(或(e,e)?R2)，故R不具有自反性. 注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上?d,e??R2,但?e,d??R2，故R2不具有对称性；?b,a??R2，

20

?无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.

?简单图，不含平行边和自回路的图.

?在无向图G＝中，与结点v(?V)关联的边数，即为结点度数deg(v)或d(v).；在有向图中，结点v的出度和入度之和为度数.

?在有向图D＝中，以v(?V)为起点的边之条数为出度deg＋(v)；以v(?V)为终点的边之条数为入度deg(v)..

?最大度数，?(G)＝max{d(v)?v?V}；最小度数，?(G)=min{d(v)?v?V}

?有n个结点的且每对结点都有边相连无向简单图，无向完全图Kn. 此时有

E?12n(n?1)－

；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为

有向完全图，.此时有E?n(n?1)

?设G＝, V，E的子集V?,E?构成的图G?=是图G的子图；若G??G且G??G，(V??V或E??E)，G?是G的真子图.

?生成子图，设图G＝, 若E??E, 则图<.V,E?>是的生成子图. 即结点与原图G相同的子图，为生成子图.

?补图?G=，设G＝, 以V为结点集，以使G成为完全图所添加的边为边集E?的图，就是图G的补图G?,.，即是完全图, 其中E?E?＝?.

?图的同构，设G1=和G2=, 存在双射f：V1?V2，?(vi,vj)?E1, 当且仅当 (f(vi),f(vj))?E2，且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2.

同构充分条件：建立两个图的对应关系，这个关系是双射函数.

同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同.

?握手定理 设G=，有v?V?deg(v)?2E?deg?,

v?V?在图D＝中，v?V

握手定理推论：奇数度结点的个数为偶数个. 度数序列.

?deg?(v)?(v)2 通路、回路、图的连通性

?通路与通路的长度，设图G＝，V＝{v0,v1,…,vn},E={e1,e2,…,em},结点与边的交替序列v0e1v1e2…vi－1eivi,为结点v0到结点vi的通路. v0,vi是通路的起点和终点. 通路中边的数目就是通路的长度.

?回路，起点和终点重合的通路.

?边不重复的通路(回路)称简单通路(回路)；结点不重复的通路(回路)，称初级通路(回路)；边有重复的通路(回路)，称复杂通路(回路).

?连通与连通图，无向图G中，结点u,v存在通路，则u,v是连通的，G中任意结点u,v都是连通的，G是连通图.

?连通分支P(G)，设G＝，V的连通等价类V1，V2，…,Vm,子图G(V1),G(V2),…,G(Vm)称为连通分支.

?点割集与割点，设无向图G＝，存在结点集V??V，使得P(G－V?)>P(G)，而任意V??V?，有P（G－V?）＝P(G)，V[FT1]?称为图G的点割集. 若V?是单元集{v}，v叫做割点.

26

?边割集与割边，设无向图G＝，存在边集E??E，使得P(G－V?)>P(G)，而任意E??E?，有P（G－E?）＝P(G)，E[FT2]?称为图G的边割集. 若E?是单元集{e}，e叫做割边(桥).

注意：点割集和边割集的两个条件.

?有向图的连通，有向图中，任意一对结点之间至少有一个结点可达另一结点是单侧连通；任何一对结点都相互可达是强连通；略去有向图D边的方向成为无向连通图是弱连通.

??单侧连通????弱连通. 由定义可知：强连通??必是必是3. 图的矩阵表示

? (无向图)关联矩阵 设G=, M(G)=

mV?n,E?m，关联矩阵

?m?ijn?m,其中mij=vi与ej的关联次数(行为结点，列为边). 具有性质：

m①

?mi?1nmij?2(列元素之和为2)；②

?2m?j?1mij?deg(vi)m,若

?mj?1ij?0,表明vi是孤立点;

③

??mi?1j?1ij,即所有元素之和等于边数的2倍;④平行边的列的元素完全对应相同.

V?n,E?m? (无向图)相邻矩阵 设G＝, A(G)=

，相邻矩阵

?a?ijn，其中aij=vi与vj相关联的边的条数(行、列均为结点).具有性质:

mnijmij ① A(G)是对称矩阵；②

?aj?1(??ai?1)?deg(vi)若?aj?1ij?0；

，表明vi是孤立点;

? (有向图)关联矩阵 设D＝, V?n,E?m，关联矩阵

?1????0????1vi为始点,vj为终点vi与vj不关联vi为终点，vj为始点mijM(D)=

?m?ijmijn?m，其中

?0(结点为行，边为列). 具有性质：

n ①

?mi?1nm(列元素之和为 0〕； ②

nijm?j?1mij?deg(vi);

③

??(mi?1j?1?1)???i?1?(mj?1ij??1)?m

V?n,E?m? (有向图)邻接矩阵 设D=, A(D)=

，邻接矩阵

?a?ijn,其中aij=邻接vi与vj的边的条数 (与A(G)类似)( 以行和列均为结点)

nmij具有性质：

??ai?1j?1?m

27

? (有向图)可达矩阵 设D=，V?n,E?m，可达矩阵

P(D)=

?p?ijn，其中

?1pij???0vi可达vj否则

n?1

P(D)?Bn?1(D)?E?A(D)?A(D)?..?A2(D)?E

二、实例

例5.1 设G＝(V,E)是一个无向图，V?{v1,v2,...,v8},

E?{(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v3,v4),(v7,v8)}

(1) G＝的?V?，?E?各是多少？ (2) 画出G的图解； (3) 指出与v3邻接的结点，以及与v3关联的边； (4) 指出与e1关联的结点； (5) 该图是否有孤立结点和孤立边？ (6) 求出各结点的度数； 解(1) G=中，有?V?=8个结点，?E?=7条边的图，故又称是8阶图. (2) 所给图G的一个图解，如图5－1. (3) 结点v1, v2, v4与v3邻接，v3关联 的边为e1, e2, e3.

(4)与边e1关联的结点为v2, v3. (5) 结点v6是孤立点；e5是孤立边.

(6) deg(v1)=3，deg(v2)=2，deg(v3)=3， deg(v4)=2＝deg(v5)，deg(v6)=0， deg(v7)=1=deg(v8).

例5.2 设图G是具有3个结点的完全图，试问

? v2 e4 e1 v1 ? e2 ? v3 ? v7 e7 ? v6 e5 e3 v5 ? e6 ? v4 ? v8 图5－1 (1) G有多少个子图？ (2) G有多少个生成子图？

(3) 如果没有任何两个子图是同构的，则G的子图个数是多少？将它们构造出来.

?3???1???3个结点的子图有??个(平凡子图)；

解 (1) 因为只有1

2

?3???2???2?6个结点的子图有??个；

3

?3?8??3???2?8个结点的子图有??个；

所以，G共有3＋6＋8＝17个子图.

(2) G的生成子图，含有G的所有结点，G有3条边，构成子图时，每条边有选中或不选

中两种可能，所以G的生成子图的个数是23＝8个.

(3) G的所有不同构的子图有7个，如图5－2所示.

? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ?

G1 G2 G3 G4 G5 G6 G7

v1? 图5－2

v4?

例5.3 给定图G=,如图5－3，

? v5

v8 ?

v3? ? ? ? v2 v7 v6 图5－3

28

(1) (1)在G中找出一条长度为7的通路； (2) 在G中找出一条长度为4的简单通路; (3)在G中找出一条长度为5的初级通路;

(4) 在G中找出一条长度为8的复杂通路; (5)在G中找出一条长度为7的回路；

(6) 在G中找出一条长度为4的简单回路; (7) 在G中找出一条长度为5的初级回路 解 所选通(回)路都不一定是唯一的. (1) 长度为7的通路：v1 v4 v3 v7 v8 v6v5v2

(2) 长度为4的简单通路：(v1, v4),( v4, v3),( v3 ,v7),( v7, v4) (边不重复的通路) (3) 长度为5的初级通路：v1 v5 v2 v6 v8 v4(结点不重复的通路) (4) 长度为8的复杂通路：(v1, v5),( v5, v8),( v8, v7),( v7, v6),( v6, v8), ( v8, v5),( v5, v4),( v4, v3)(边有重复的通路) (5) 长度为7的回路：v1 v4 v3 v7 v8 v6v5v1

(6)长度为4的简单回路： ( v1, v4),( v4, v8),( v8 ,v5),( v5, v1)(边不重复的通路) (7)长度为5的初级回路：v1 v5 v6 v7 v4 v1(除起点和终点外，结点不重复的通路) 例5.4设图5－4，V={a,b,c,d,e}

G1＝,E1={(a,b）,(b,c),(c,d),(a,e)}; G2＝,E2={(a,b),(b,e),(e,b),(a,e),(d,e)};

G3＝,E3={(a,b),(b,e),(e,d),(c,c)};

G4＝,E4={,,,,,}; G5＝,E5={,,,,,};

G6＝,E6={,,,,}.

a? a ? a ? a ? a ? a ?

b? ?e b? ?e b? ? e b ? ? e b ? ? e b? ? e

c? ?d c? ?d c? ? d c? ?d c? ?d c? ?d

(G1) (G2) (G3) (G4) (G5) (G6)

图5－4 试问：

(1) 哪些图是有向图？哪些图是无向图？ (2) 哪些是简单图？ (3) 哪些是强连通图？哪些是单侧连通图？哪些是弱连通图？ 解 (1) G1, G2, G3是无向图；G4, G5, G6是有向图.

(2) G1, G4, G5中既无平行边，也无自回路，是简单图.

(3) G5是强连通图(必是单侧连通图和弱连通图)；G4是单侧连通图(为什么？)(也是弱连通图)；G6只是弱连通图.

例5.5 求例5.4中图(1)G2的关联矩阵，(2)图G3的相邻矩阵，(3)图G5的关联矩阵、(4)图G5邻接矩阵以及从b到c,d长度为3的通路条数，从b到b长度为2的回路的条数以及长度为3的通路共有多少条，长度不超过3的通路条数和回路的条数；(5)图G5的可达矩阵.

解 (1)已知图G2的结点集V2={a,b,c,d,e},边集

? E2={(a,b),(b,e),(e,b),(a,e),(d,e)}?{e1,e2,e3,e4,e5}，n=5,m=5. G2是无向图，由关联矩阵的定义，

M(G2)??mij?n?m，其中mij=vi与ej关联的次数.于是有

29

e1a?1?b?1M(G2)?c?0?d?0?e?0e201001e301001e4e5

10??00?00??01??11?

(2) 因为G3为V3={a,b,c,d,e}, E3={(a,b),(b,e),(e,d),(c,c)}，是无向图，由相邻矩阵的定义，

A(G3)?aij??n，其中aij=vi与vj关联的边的次数. n=5,故相邻矩阵为

ab10001c00200d00001e0??1?0??1??0?

a?0?b?1A(G3)?c?0?d?0?e?0

(3) 有向图G5，V5={a,b,c,d,e}, E5={,,,,,}，由关联矩阵的定义

M(G5)??mij?n，其中当vi为ej的始点时，mij=1；当vi为ej的终点时，mij=－1；当vI

与ej不关联时，mij=0. 于是所求关联矩阵为

e1a?1?b??1M(G5)?c?0?d?0?e?0

e2?11000e301?100e4001?10e50e6?1??00?00??10???11?

(4) 图G5的邻接矩阵为

1000001000001000??1??00???00???1??1?0??. A2(G5)=?00100110000010000??0??01???11???0??0?0??，A3(G5)=?11001001001100000??1?0??0?0??

?0?1??0??0?A(G5)=?1从A3(G5)可知，从结点b到结点c,d各有1条、0条长度为3的通路. 从b到b长度为2的回

55(3)ij路有1条；长度为3的通路共i?12条.

??aj?1=9条；长度不超过3的通路共有22条，其中回路是

30

本文来源：https://www.bwwdw.com/article/49tf.html