简单图的判定

图序列判定的三个简单方法

综合理科062班 张芳芳

摘要：图的度序列是图论研究中的一个重要课题，至今有很多学者对其性质及应用进行了一系列的研究和探索，而简单图的度序列是图论研究中的一个难点，本文具体介绍了两个图序列的判定和例题应用，并给出了图序列的另外6个判定。 关键词：图；度序列；图序列

1．引言

图论是一门应用十分广泛，内容非常丰富的数学分支，这里所讨论的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象。下面给出图的定义：

定义1 用顶点（小圆点）代表事物，用边表示各事物间的二元关系，若所讨论的事物之间有某种二元关系，我们就把相应的顶点连成一条边，这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。 定义2 度序列：

设图

G

，其顶点的集合为

123(){,,,,}

n V G v v v v =???，

i

v 的度为

(),1,2,G i d v i n =???，则称非负整数序列n ?12((),(),,())G G G n d v d v d v =???为图G 的

度序列；若图G 是简单图，则称之为图序列或可图序列。

2． 图序列问题及判定

首先不妨设,i j ?，若i j <，则()()

G i G j d v d v ≤记为条件（1），而一个边数为q 的

图G ，其各点的度数的和

12n

i

i d

q ==∑，显然是偶数。所以对给定的一个非负整数序列

n ?12(,,,)n d d d =???，若1

2,n i i d k k =≠∑为自然数，则n ?一定不是度序列，从而不是

图序列，记为条件（2），且对于一个简单图而言，必有1}1:)(max{-≤≤≤n n i v d i G 记为条件（3），将

1

()2,n

G

i i d

v k k N ==∈∑记为条件（4）。

本文在以上条件成立的基础上进行讨论，将其称为前提条件。对于这些条件成立的图的度序列对应的图的一个实现有很多，例如，图1所示的

12G ,G 的度序列均是

(7,3,1,4,6,5)。

图1 简单图的度序列称为图序列，已知一个序列n

?12(,,,)n d d d =???，若存在简单图G ，

使得n ?是图G 的度序列，则称n ?是可图的，而图G 就是度序列n

?12(,,,)n d d d =???的

一个实现。图序列的讨论或判断要比度序列的讨论困难得多。下面定理1是Erdos 和Callai 在1960年给出的图序列的一个判别方法： 定理

1[1]

设

12()()()

G G G n d v d v d v ≥≥???≥，非负整数序列

12((),(),,())G G G n d v d v d v ???是图序列当且仅当1

()n

G i i d v =∑是偶数，且对一切整数k ，

11k n ≤≤-，有1

1

()(1)min{,()}k

n

G i G

i i i k d v k k k d

v ==+≤-+

∑∑。

例题应用：

例1 证明非负整数序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是图序列。 证：1

对序列(7,6,5,4,3,3,2)，

1

()30n

G

i i d

v ==∑，为偶数，当1k =时，1

()7k

G i i d v ==∑，

1

(1)min(,())6

n

G i i k k k d v =-+=∑，不满足

1

1

()(1)min{,()}k

n

G

i G

i i i k d

v k k k d v ==+≤-+

∑∑，所以序列(7,6,5,4,3,3,2)不是图序

列。

2

序列(6,6,5,4,3,3,1)，

1()28n

G

i i d

v ==∑为偶数，当2k =时，1

()12k

G i i d v ==∑，

1

(1)min(,())11

n

G i i k k k d v =-+=∑，不满足

1

1

()(1)min{,()}k

n

G

i G

i i i k d

v k k k d

v ==+≤-+

∑∑，所以序列(6,6,5,4,3,3,1)不是图序列。

定理2 利用分配——减点法得出的判定条件简单叙述。以下给出利用分配——减点法得出

的判定条件的过程：

定义3 对n ?进行变换，令：

1111''''''

12211110,,1,1,,1,1

n d n d n d n d n n n n d d d d d d d d d d d ---+-+--==???=-=-???=-=-记'

''''121{,,,,}n

n n d d d d ?-=???，因为'10d =，不妨记为''''

121{,,,}n n n d d d ?--=???，不妨

将'

'

'

21,,,n n d d d -???重新自小到大排列，并记为：1

111

1

21{,,,}n n n d d d ?--=???。这样由n ?变

换为1

1n ?-的方法即为分配——减点法；并且我们称1

1n ?-为n ?的一个分配——减点子列。更一般的1

i j ?+为1i

j ?+的分配——减点子列。 定义4 准简单图序列

正整数序列*

n ?满足简单图序列的前提条件，对其进行2n -次的分配——减点操作，得到*n ?的1次，2次，……3n -次，2n -次分配——减点子列，分别为*11n ?-，*2

2n ?-，……

*(3)(3)n n n ?---，*(2)(2)n n n ?---，若,12i i n ?≤≤-，i

n i ?-满足条件（1）

，（2），则称这样的正整数序列*

n ?为准简单图序列。 引理1

121{(),(),,(),()}i G G G i G i d v d v d v d v ?-?=???，

若,1,()G j j j i d v i ?≤

≤≥，则i ?一定不是图序列。

引理2 任意正整数序列n ?与其分配——减点子列1

1n ?-有相同的简单图化性质，即：n ?是图序列的充要条件为1

1n ?-是图序列。

由引理1与引理2易知一个推论：设1i

n ?-是n ?的i 次分配——减点子列，则n ?是图序列的充要条件为1i

n ?-是图序列。

证明：分别对n ?进行1次，2次……1i -次，i 次分配——减点操作，则分别得其1次，2次……1i -次，i 次分配——减点子列1

1n ?-，2

2n ?-，……，11i n i ?--+，i

n i ?-。由引理2知：

11n ?-是图序列?22n ?-是图序列?33n ?-是图序列，……，?11i n i ?--+是图序列?i n i

?-是图序列，根据等价的传递性知：n ?是图序列?

1

i

n ?-是图序列。 设n

?12(,,,)n d d d =???是一正整数序列，且满足条件（3）

，（4），n ?是图序列的充要条件是n ?是准简单图序列，且其2n -次的分配——减点子列2

22

212{,}n n n d d ?---= 满

足：2

2

1

21n n d d --=≤。

证明：1

需证准简单图正整数序列*

n ?是图序列的充要条件为*

n ?的其2n -次的分配——减点子列*(2)

*(2)22(2)

212{,}n n n n n n d d ??------==满足22

121n n d d --=≤。

由引理的推论知：*n ?是图序列的充要条件为*n ?的分配——减点子列*(2)

2n ?-是图序列。

而*(2)

222

12{,}n n n d d ?---=满足：22121n n d d --=≤。若22121n n d d --==，则*(2)

2

n ?-对应着2阶完全图；若2

21

20n n d d --==，

则*(2)

2n ?-对应着2阶空图，显然*(2)

2

n ?-均是图序列。

因此，*

n ?是图序列。

2 进行定理证明。 n ?是准简单图序列，且2n -次的分配——减点子列

222212{,}n n n d d ?---=满足：22

121n n d d --=≤，则由上面的证明可知n ?是图序列。

例题应用：任意一正整数序列10{1,2,3,4,5,6,6,7,8,8}?=，判断其是否为图序列。

解：1

10?满足图序列的前提条件，

2 对其进行8次分配——减点操作，其各次分配——减点子列如下：

1

9{2,3,4,5,6,6,7

,7,8}?= 28{3,4,5,6,6,6,7,7}

?= 3

7{4,5,5,6,6,6,6}

?= 46{5,5,5,5,5,5}?=

55{4,4,4,4,4}?=

64{3,3,3,3}?=

73{2,2,2}?=

82{1,1}?=

3 由以上操作可知：10?是准简单图序列且82{1,1}?=满足判定的条件，所以10?是图

序列。

如下图为10?对应的一个简单图

图2

对定理2有一个更简单直接的判定方法即： 定理3 非负整数序列

12((),(),,())G G G n d v d v d v ???，且

1

()

n

G

i i d

v =∑是偶数，

121()()()

G G G n n d v d v d v -≥≥≥???≥，它是图序列的充要条件为

231(()1,()1,()1,())G G G n G n d v d v d v d v ---???-是图序列。

例题应用：任然用方法一中的例题的第二个序列，对序列(6,6,5,4,3,3,1)，

231(()1,()1,()1,())(5,4,3,2,2,1)

G G G n G n d v d v d v d v ---???-=，对原序列有

1

()28n

G

i i d

v ==∑，为偶数，且121()()()G G G n n d v d v d v -≥≥≥???≥，新产生的序列

(5,4,3,2,2,1)，对其求和为17，是奇数，不是图序列，所以序列(6,6,5,4,3,3,1)不是

图序列。

下面给出图序列的另外几个判定： 1） 基本定义：

（1） 设12(,,,)n x x x x =???，12(,,,)n y y y y =???是两个非负整数序列，若x 与y

经重排为12n x x x ≥≥???≥与12n y y y ≥≥???≥，有1

1

,1,2,3,,k k

i i i i x y k n ==≤=???∑∑，

其中当

k n

=时取等号，则称

x

优超

y

，记作

x y

。同理，

x y

表示

1

1

,1,2,3,,k

k

i i

i i x y k n ==≥=???∑∑，当k n =时等号成立。

（2） 对非负整数序列

12(,,,)n x x x x =???，记*{:1}j i x i i n x j =≤≤≥且，

{:111}{:1}

j i i x i i j x j i j i n x j -

=≤≤-≥-++≤≤≥且且，

1

j j x x -

=+当

1j m ≤≤时，且j j x x -

=当1m j n +≤≤，其中max{:1}i m i i n x i =≤≤≥且，则

*

*

**12(,,,)n

x x x x =???与12(,,,)n x x x x ----

=???分别是x 的共轭序列与约束共轭序列。

（3） 设G 是简单二部图，其顶点集合()V G 具有独立集划分[,]X Y ，其中

12(,,,)m X v v v =???，

12(,,,)

n Y u u u =???，

i

v 和

j

u 的度分别是

i

r 和j

s ，1,1i m j n

≤≤≤≤，

设

121

,m n r r r s s s ≥≥???≥≥???≥。

记

121(,,),(,,,)m n R r r r S s s s =???=???，则[,]R S 是G 的度序列偶。对非增的非负整数序列1212(,,),(,,,)m n R r r r S

s s s =???=???，

若[,]R S 是某二部图G 的度序列偶，则[,]

R S 称为二部可图的，G 称为[,]R S 的一个实现。

2） 图序列的另外6个判定 设n

?12(,,,)n d d d =???是非增的非负整数序列，1

n

i i d =∑为偶数，则下列条件均等价于

n ?是图序列：

（1）

[3]

Ryser 判准

：[,]n n ??--

是二部可图的；

（2）[4]

Berge 判定

：n

n ??-

，即对1,2,,k n =???，

'

1

1

1

1

min{1,}min{,}k

k

k

n

i i

i

i

i i i i k d d k d k d ====+≤=-+∑∑∑∑；

（3）Ruch Gutman Hassclbarth --判定：对1,2,,k f

=???，

*

1

1

(1)k k

i i i i d d ==≤-∑∑； （4）

[5]ker Ful son Hoffman McAndrew --判定：对1,2,,k n =???

，和0,1,,m n k =???-，1

1

(1)k

n

i i

i i n m d k n m d ==-+≤--+

∑∑

；

（5）[6]

Bollobas 判定：对1,2,,k

n =???，

1

1

1

min{1,}k

k

n

i i

i

i i i k d k d d ===+≤-+∑∑∑

（6）[7]

Grunbaum 判定

：对1,2,,k n =???，

1

1

max{1,}(1)k

n

i

i

i i k k d k k d

==+-≤-+∑∑

Erdos 和Callai 的判别方法在进行具体判别时需要较大的计算量，需要计算

1,2,,n ???的每个k 值时的1

()k

G i i d v =∑和1

(1)min{,()}n

G

i i k k k k d

v =+-+

∑，看其是否满足

条件，特别随着n 的增大，计算量会变得复杂；方法二只需判别是否同时满足原序列的和

1

()n

G

i i d

v =∑为偶数，121()()()G G G n n d v d v d v -≥≥≥???≥，变换后的序列是否是图

序列。对方法二进行修正和补充后可知按相同的方法变换得到的序列是否是图序列与后一个

序列是否是图序列等价，所以，若作一系列的变换后得到一个不是图序列的序列，就可判断原来的序列不是图序列。另外，本文随后给出的6个判定是对本文内容的一个补充。

参考文献：

[1]卜月华，图论及其应[M]，南京：东南大学出版社，2002.

[2] 李炯生，尹建华。极值图论与度序列[ J ]. 数学进展，2004, 33 (3) : 273 - 283.

[3] Ryser H J. Combinatorial properties of matrices of zeros and ones. Canad . Math. Bull. , 1957, 9:371—377.

[4]Berge C. Graphs and hyper graphs . North —Holland Publishing Co.,Amsterdam, 1973.

[5] Fulkerson D R,Hoffman A J,McAndrew M H. Some properties of with multiple edges.Canad J.Math,1965,17:166-177. [6] Bollobas B. External Graph Theory. Academic Press, New York, 1978.

[7] Grunbaun B.graphs and complexes. Report of the University of Washington, Seattle Math.,572B,1969

图同构问题综述

图同构问题综述 数据科学与计算机学院 黄**1******3 2016.05.26

1概述 芝加哥大学计算机科学教授LászlóBabai在2015年11月宣布了一个能在拟多项式时间内解决图同构问题的新算法，该算法还有待进一步审查以确定其正确性.如果最终被证明是正确的，那么这将是计算机理论领域的一项非常重要的成果. 图的同构问题可以分为四类：精确图同构问题、精确子图同构问题、不精确图同构问题和不精确子图同构问题.其中后三个问题已经被证明是NP完全问题，而对于精确图同构问题的复杂性问题，目前还没有明确的结果，即尚不清楚它是P问题还是NP完全问题，但至少知道它是NP问题. 本文是图同构问题的一个综述，首先给出图同构问题的定义，接着介绍了图同构问题判定算法的研究现状和应用，最后介绍一些具体的判定算法. 2图同构的概念 一个图可以存在多种不同的形式，这些不同形式的图都具有相同数目的顶点、边，而且边还具有相同的连接性.这些不同形式的图就是同构. 直观上地说，如果两个图G1和G2有相同数目的顶点和边，并且边的连接性也相同，那么就说这两个图是同构的.我们可以把一个图看做是另一个图经过扭曲得到的.下面给出图同构的严格定义. 给定两个无向简单图G和H，如果存在一个双射f:V(G)→V(H)，使得对于任意的u,v∈V(G)，有?u,v?∈E(G)当且仅当?f(u),f(v)?∈E(V)，则称图G和H是同构的，记为G?H. 如果G1?G2，那么： (1)|V(G1)|=|V(G2)|. (2)|E(G1)|=|E(G2)|. (3)G1和G2的度序列相同. (4)如果{v1,v2,...,v k}是G1的长度为k的圈，那么{f(v1),f(v2),...,f(v k)}是G2长 度为k的圈. 上述的条件是两个图G1和G2同构的必要条件，下面给出几个充分条件： (1)G1?G2当且仅当G1?G2，其中G1和G2都是简单图. (2)G1?G2如果它们有相同的邻接矩阵. (3)G1?G2当且仅当它们相应的子图也同构.

因果图判定表

第五讲因果图和判定表 1、因果图适用场合 在一个界面里有多个控件，如果控件之间有组合或者限制关系，不同控件组合会产生不同的输出结果，为了弄清楚不同的输入组合会产生怎样的输出结果，就可以使用因果图（适合测试组合量少的一般情况少于20种，如果超过20种组合，一般就考虑正交排列法） 2、因果图核心概念： 因（原因）：指的是输入条件 果（结果）：指的是输出结果 因果图法：通过画图的方式表达输入条件和输出条件之间的关系3、图形符号 1）基本的图形符号 说明：输入和输出之间的关系用基本图形符号表示 A=1那么B=1，如果A=0那么B=0，恒等就是

B、与：若几个输入条件都满足，结果才出现 C、或 复习：全0位0，有1出1。 理解：输入条件中有一个条件满足结果就出现，只有所有输入条件都不满足，结果不出现 D非（用的少，了解） 例如A=1，那么B=0 2）限制（约束）图形符号。

说明：要么限制的是同为输出条件，要么限制的都是输出条件，互斥（E-exclude） 说明：如果选只能选1个，但可以不选 2）唯一（o-only） 说明：必须要选，只能选一个 唯一和互斥的区别：相似之处，必须选一个，不同之处互斥可以不用选， 3）包含（I—include）

说明：至少有一个被选中（支持多选） 4）要求（R-required） 说明：如果A=1，那么要求B=1，反之如果A=0,B就无所谓了（结合自动登录的案例） 5）屏蔽（M-masked） 说明：当A=1时，b必须是0，反之A=0时，b的值就不一定 二、因果图的操作步骤 1、找出所有的输入条件（因） 投币50元 投币100元

5种图同构算法的比较

A Performance Comparison of Five Algorithms for Graph Isomorphism P. Foggia, C.Sansone, M. Vento Dipartimento di Informatica e Sistemistica Via Claudio, 21 - I 80125 - Napoli, Italy {foggiapa, carlosan, vento}@unina.it Abstract Despite the significant number of isomorphism algorithms presented in the literature, till now no efforts have been done for characterizing their performance. Consequently, it is not clear how the behavior of those algorithms varies as the type and the size of the graphs to be matched varies in case of real applications. In this paper we present a benchmarking activity for characterizing the performance of a bunch of algorithms for exact graph isomorphism. To this purpose we use a large database containing 10,000 couples of isomorphic graphs with different topologies (regular graphs, randomly connected graphs, bounded valence graph), enriched with suitably modified versions of them for simulating distortions occurring in real cases. The size of the considered graphs ranges from a few nodes to about 1000 nodes. 1. Introduction The exact graph matching problem is of interest in a variety of different pattern recognition contexts. In fact, graphs are used to support structural descriptions as well as for low level image representations. As it is well known, among the different types of graph matching algorithms, subgraph isomorphism is a NP-complete problem [10], while it is still an open question if also graph isomorphism is a NP-complete problem. So, time requirements of brute force matching algorithms (either in case of isomorphism or subgraph isomorphism) increase exponentially with the size of the input graphs, restricting the applicability of graph based techniques to problems implying graphs with a small number of nodes and edges. During the last decades significant research efforts have been devoted to improve performances of the matching algorithms, both in terms of computational time and memory requirements. Some algorithms reduce the computational complexity of the matching process by imposing topological restrictions on the graphs [1, 11, 14, 22] An alternative approach for reducing the matching complexity is that of using an adequate representation of the searching process and pruning unprofitable paths in the search space. In this way, no restrictions must be imposed on the structure of the

[黑盒测试基本方法]之因果图与判定表

测试用例设计方法 之因果图法与判定表 1.因果图法 1.1.前言 从用自然语言书写的程序规格说明的描述中找出因（输入条件）和果（输出或程序状态的改变），可以通过因果图转换为判定表。 因果图法即因果分析图，又叫特性要因图、石川图或鱼翅图，它是由日本东京大学教授石川馨提出的一种通过带箭头的线，将质量问题与原因之间的关系表示出来，是分析影响产品质量的诸因素之间关系的一种工具。 1.2.定义 因果图法是一种适合于描述对于多种输入条件组合的测试方法，根据输入条件的组合、约束关系和输出条件的因果关系，分析输入条件的各种组合情况，从而设计测试用例的方法，它适合于检查程序输入条件涉及的各种组合情况。因果图法一般和判定表结合使用，通过映射同时发生相互影响的多个输入来确定判定条件。因果图法最终生成的就是判定表，它适合于检查程序输入条件的各种组合情况。采用因果图法能帮助我们按照一定的步骤选择一组高效的测试用例，同时，还能指出程序规范中存在什么问题，鉴别和制作因果图。 因果图法着重分析输入条件的各种组合，每种组合条件就是“因”，它必然有一个输出的结果，这就是“果”。 1.3.因果关系 因果图的表示中输入与输出间的因果关系有四种： 1）恒等关系：当输入条件发生，会产生对应输出，当输入条件不发生时，不会产生都会应输出。 2）非关系：与恒等关系相反。 3）或关系：多个输入条件中，只要有一个发生，则会产生对应输出。

4）与关系：多个输入条件中，只有所有输入项发生时，才会产生对应输出。 特定的符号标明因果关系如下（图1.3.1）: 图1.3.1 因果图的表示中输入与输入间的约束关系有四种： 1）异(E)：所有输入中至多一个输入条件发生。 2）或(I)：所有输入中至少一个输入条件发生。 3）唯一(O)：所有输入中有且只有一个输入条件发生。 4）要求(R)：所有输入中只有一个输入条件发生，则其它输入也会发生。 特定的符号标明输入与输入间约束关系如下（图1.3.2）: 图1.3.2 因果图的表示中输出条件约束类型（见图1.3.2）： 1）输出条件的约束只有M约束(强制)：若结果a是1，则结果b强制为0。1.4.方法应用 利用因果图导出测试用例一般要经过以下几个步骤： 1）画出因果图。 2）因果图上用一些记号表明约束条件或限制条件。 3）对需求加以分析并把它们表示为因果图之间的关系图。

测试用例设计方法之因果图法

测试用例设计方法之因果图法 (一)因果图法的来源 ?大家熟悉的等价类划分法和边界值分析法，都是着重考虑输入条件，但未考虑输入条件之间的联系、相互组合等； ?但是，如考虑所输入条件之间的相互组合，会由于组合情况数目相当大，需要大量的测试用例； ?因果图法，是一种帮助人们系统地选择一组高效率测试用例的方法。(二)因果图法的特点 ?考虑输入条件间的组合关系； ?考虑输出条件对输入条件的信赖关系，即因果关系； ?测试用例发现错误的效率高； ?能检查出功能说明中的某些不一致或遗漏； ?因果图方法最终生产的就是判定表，它适合于检查程序输入条件和各种组合情况。 (三)因果图法基本步骤 1.分割功能说明书 对于规模比较大的程序来说，由于输入条件的组合数太大，所以很难整体上使用一个因果图。我们可以把它划分为若干部分，然后分别对每个部分使用因果图。例如，测试编译程序时，可以把每个语句作为一个部分。 2.识别出“原因”和“结果”，并加以编号 所谓原因，是指输入条件或输入条件的等价类；而结果则是指输出条件或输出条件的等价类。每个原因或结果都对应于因果图中的一个节点。当原因或结果成立（或出现）时，相应的节点取值为1，否则为0。 例如，有一个饮料自动售货机（处理单价为5角钱）的控制处理软件，它的软件规格说明如下： 若投入5角钱的硬币，按下“橙汁”或“啤酒”的按钮，则相应的饮料就送出来。若投入1元钱的硬币，同样也是按“橙汁”或“啤酒”的按钮，则自动售货机在送出相应饮料的同时退回5角钱的硬币。 分析这一段说明，我们可以列出原因和结果。

原因如下： ?投入1元硬币； ?投入5角硬币； ?按下“橙汁”按钮； ?按下“啤酒”按钮 结果 ?退还5角钱； ?送出“橙汁”饮料； ?送出“啤酒”饮料 3.根据功能说明书中规定的原因和结果之间的关系画出因果图 因果图的基本符号如图1所示： 1.因果图的基本符号 图中左边的节点表示原因，右边的节点表示结果。恒等、非、或、与的含义： ?恒等：若a=1，则b=1；若a=0，则b=0； ?非：若a=1，则b=0，若a=0，则b=1； ?或：若a=1或b=1或c=1，则d=1；若a= b= c=0，则d=0； ?与：若a= b= c=1，则d=1；若a=0或b=0或c=0，则d=0。 画因果图时，原因在左，结果在右，由上而下排列，并根据功能说明书中规定的原因和结果之间的关系，用上述基本符号连接起来。在因果图中还可以引入一些中间节点。 利用上面的例子，根据原因和结果，可以画出相对应的因果图，如下图所示：

测试用例设计方法2——因果图判定表

测试用例设计方法2——因果图判定表 判定表法 判定表是分析和表达多种输入情况下执行不同动作的工具，判定表方法主要用于处理程序输入条件的不同组合，但是要求条件的组合必须是bool类型，而且条件和预期的结果都是可以分析出来的。判定表能够有效地弥补等价类和边界值方法的不足，使得输入条件之间的组合和相互影响得到充分的测试。 使用判定表的一般思路是： 1、需求分析，分析出条件和结果之间的各种组合 2、将条件和结果分别填入判定表 3、讲条件和结果进行二进制排列 4、针对每一项组合，分析出结果，并去除无效项，是判定表得到简化。在合并判定表时，如果条件之中只有一个不同，则可以合并。如果判定表的组合不够多，建议不要进行合并，这样可以测试的充分一些。 5、每一列生成一个测试用例 以阅读指南的例子来设计一个判定表：从例子中可以看到，不同的条件组合 使用判定表方法可以充分弥补等价类边界值得不足，但是当输入条件过多时，使用判定表会产生大量测试用例。而其无效用例不易发现，更不能覆盖条件之间的先后关系。因此，在一定情况下，使用判定表还需要因果图的帮忙。 -------------------------------------------------------------------------------- 因果图

因果图用于描述系统之间的输入输出，输入输出之间的约束关系和因果关系。因果图与判定表往往结合使用，使用因果图可以得到判定表。 使用因果图的方法： 1、分析输入输出并进行标识 2、分析输入和输入、输入和输出之间的关系 3、将得到的关系使用因果图的方法表示出来 4、根据因果图得到判定表 5、依据判定表生成测试用例 这里分析一个自动售货机的因果图分析方法： 条件：有一个处理单价为5角的自动售货机，当投入5角或1元硬币时，选择橙汁或啤酒，饮料出来；若自动售货机没有零钱，则显示零钱照完，亮红灯，这时候投入的1元被退出来，饮料不送出来。如果有零钱，则出饮料并找5角钱。 分析： 1、选择橙汁和啤酒是同一类型，可以进行归类 2、选择5角和1元看似是同一类，但是他们所触发的操作是不同的，不能归类 3、橙汁和啤酒、5角和1元是相异的关系 4、分析不同的组合并得到最终结果 总结：因果图的使用和分析比较复杂，使用因果图可能会消耗很多的时间，因此正确的策略是先考虑其他的测试用例设计方法，最后再使用因果如，可以尽量的减少工作的时间并提高效率。

因果图分析法实例讲解

因果图分析法： 前面介绍的等价类划分方法和边界值分析方法，都是着重考虑输入条件，但未考虑 输入条件之间的联系, 相互组合等。考虑输入条件之间的相互组合，可能会产生一些新的情况。但要检查输入条件的组合不是一件容易的事情，即使把所有输入条件划分成等价类，他们之间的组合情况也相当多。因此必须考虑采用一种适合于描述对于多种条件的组合，相应产生多个动作的形式来考虑设计测试用例。这就需要利用因果图（逻辑模型）。 因果图方法最终生成的就是判定表，它适合于检查程序输入条件的各种组合情况。 因果图中使用了简单的逻辑符号，以直线联接左右结点。左结点表示输入状态（或 称原因），右结点表示输出状态（或称结果）。 ci 表示原因，通常置于图的左部；ei 表示结果，通常在图的右部。ci 和ei 均可取值 0或1，0表示某状态不出现，1表示某状态出现。 4种符号分别表示了规格说明中向4种因果关系。如上图所示。 ①恒等：若ci 是1，则ei 也是1；否则ei 为0。 ②非：若ci 是1，则ei 是0；否则ei 是1。 ③或：若c1或c2或c3是1，则ei 是1；否则ei 为0。“或”可有任意个输入。 ④与：若c1和c2都是1，则ei 为1；否则ei 为0。“与”也可有任意个输入。 因果图概念--约束 输入状态相互之间还可能存在某些依赖关系，称为约束。例如, 某些输入条件本身不可能同时出现。输出状态之间也往往存在约束。在因果图中,用特定的符号标明这些约束。 A.输入条件的约束有以下4类： ① E 约束（异）：a 和b 中至多有一个可能为1，即a 和b 不能同时为1。 ② I 约束（或）：a 、b 和c 中至少有一个必须是1，即 a 、b 和c 不能同时为0。 ③ O 约束（唯一）；a 和b 必须有一个，且仅有1个为1。 ④R 约束（要求）：a 是1时，b 必须是1，即不可能a 是1时b 是0。 B.输出条件约束类型 （d ）与

因果图实例讲解

1.引言 等价类划分方法和边界值分析方法，都是着重考虑输入条件，但未考虑输入条件之间的联系、相互组合等。考虑输入条件之间的相互组合，可能会产生一些新的情况。但要检查输入条件的组合不是一件容易的事情，即使把所有输入条件划分成等价类，他们之间的组合情况也相当多。因此必须考虑采用一种适合于描述对于多种条件的组合，相应产生多个动作的形式来考虑设计测试用例。这就需要利用因果图（逻辑模型）。 因果图（Cause-EffectGraphing）提供了一个把规格转化为判定表的系统化方法，从该图中可以产生测试数据。其中原因是表示输入条件，结果是对输入执行的一系列计算后得到的输出。 因果图方法最终生成的就是判定表，它适合于检查程序输入条件的各种组合情况。 2.因果图介绍 2.1图例说明 1、4种符号分别表示了规格说明中向4种因果关系。如图2-1所示。 图2-1 因果图关系 2、因果图中使用了简单的逻辑符号，以直线联接左右结点。左结点表示输入状态（或称原因），右结点表示输出状态（或称结果）。

3、ci表示原因，通常置于图的左部；ei表示结果，通常在图的右部。ci和ei均可取值0或1，0表示某状态不出现，1表示某状态出现。 2.2因果图概念 1、关系（图2-1 因果图关系） ①恒等：若ci是1，则ei也是1；否则ei为0。 ②非：若ci是1，则ei是0；否则ei是1。 ③或：若c1或c2或c3是1，则ei是1；否则ei为0。“或”可有任意个输入。 ④与：若c1和c2都是1，则ei为1；否则ei为0。“与”也可有任意个输入。 2、约束 输入状态相互之间还可能存在某些依赖关系，称为约束。例如，某些输入条件本身不可能同时出现。输出状态之间也往往存在约束。在因果图中，用特定的符号标明这些约束。如图2-2所示。 图2-2因果图约束 A.输入条件的约束有以下4类： ①E约束（异）：a和b中至多有一个可能为1，即a和b不能同时为1。

决策表与因果图练习题

决策表练习题： 一、假设xx某航空公司规定： 中国去欧美的航线所有座位都有食物供应。每个座位都可以播放电影。 中国去非欧美的国外航线都有食物供应，只有商务仓可以播放电影。 中国国内的航班的商务仓有食物供应，但是不可以播放电影。 中国国内的航班的经济仓除非飞行时间大于2小时就有食物供应，但是不可以播放电影。 要求： 使用决策表法设计测试用例。 二、某商场促销活动期间，对持商场会员卡的顾客，实行 8.5折优惠，满1000元实行7折优惠；对其他顾客消费满1000元的，实行9折优惠，并免费办理会员卡。 要求： 请给出相应的决策表和测试用例。 因果图练习题 一、有一个处理单价为5角钱的饮料的自动售货机软件测试用例的设计。其规格说明如下： 若投入5角钱或1元钱的硬币，押下〖橙汁〗或〖啤酒〗的按钮，则相应的饮料就送出来。若售货机没有零钱找，则一个显示〖零钱找完〗的红灯亮，这时在投入1元硬币并押下按钮后，饮料不送出来而且1元硬币也退出来；若有零钱找，则显示〖零钱找完〗的红灯灭，在送出饮料的同时退还5角硬币。 要求：1）列出原因和结果，画出因果图 2）根据因果图，建立判定表

3）根据判定表设计测试用例数据 二、用因果图法测试以下程序。 程序的规格说明要求： 输入的第一个字符必须是#或*，第二个字符必须是一个数字，此情况下进行文件的修改；如果第一个字符不是#或*，则给出信息N，如果第二个字符不是数字，则给出信息M。 要求： （1）分析程序的规格说明，列出原因和结果。 （2）找出原因与结果之间的因果关系、原因与原因之间的约束关系，画出因果图。 （3）将因果图转换成决策表。 （4）根据 （3）中的决策表，设计测试用例的输入数据和预期输出。 三、分析中国象棋中走马的实际情况（下面未注明的均指的是对马的说明）（选做） 1.如果落点在棋盘外,则不移动棋子； 2.如果落点与起点不构成日字型,则不移动棋子； 3.如果在落点方向的邻近交叉点有棋子(绊马腿),则不移动棋子； 4.落点处有己方棋子,则不移动棋子; 5.如果不属于1-3条,落点处无棋子,则移动棋子； 6.如果不属于1-3条,落点处为对方棋子(非老将),则移动棋子并除去对方棋子；

判定表因果图

修改Notes账户密码，首先输入原密码，原密码输入正确后输入两次新密码，要求两次输入的新密码一致，且新密码达到复杂度要求（8～15位，包含大、小字母、数字、字符），密码修改成功后提示用户修改成功，否则提示用户操作失败。 原密码 1 1 1 0 0 新密码 1 - 0 1 0 确认密码 1 0 1 - - 修改成功Y 修改失败N N N N 原密码：正确1、不正确0 新密码：符合1、不符合0 确认密码：一致1、不一致0 不符合复杂度：<8、>15 、不包含大写、不包含小写、不包含数字、不包含字符 用例1：原密码正确、新密码Ab123！@# 确认密码Ab123！@# 用例2 原密码正确、新密码Ab123！@# 确认密码Ab123 用例3-1 原密码正确、新密码Ab1！@# 确认密码Ab1！@# 用例3-2 原密码正确、新密码Ab123456789012！@# 确认密码Ab123456789012！@# 用例3-3 原密码正确、新密码ab123！@# 确认密码ab123！@# 。。。。。3-6 用例4 用例5 函数NextDate能够根据当前输入的日期计算出下一天日期。比如今天是2008年5月3日，程序计算出的结果就是2008年5月4日。利用判定表设计测试用例对该程序进行验证。（假设已有其它函数保证输入的Y、M、D值是有效正整数，1<=M<=12，1<=D<=31，这里重点关注Y、M、D是否会有逻辑错误） 条件桩：年Y：平年Y1、闰年Y2 月M ：大月（除12月)M1、小月M2、2月M3、12月M4 日D ：28D2、29D3、30D4、31D5、1-27D1 动作桩：Y+1、M+1、D+1、无效 2*4*5=M1*（D1- 4+D5）+M2*（D1-3+D4+D5）+M3*A1(D1+D2+D3-5)+M3*A2*(D1-2+D3+D4-5)+M4*(D1-4+D5)=13 M3*2*5=M3*A1(D1+D2+D3-5)+M3*A2*(D1-2+D3+D4-5)=6 Y Y1 Y1 Y1 Y2 Y2 Y2 M M1,M1 M2 M2 M2 M3 M3 M3 M3 M3 M3 M4 M4

因果图判定表工程方法

因果图判定表工程方法

目录 1.概述 (4) 2.适用范围 (4) 3.工程方法定义 (5) 3.1.因果图 (5) 3.2.判定表 (6) 4.接口描述 (6) 4.1.工程方法使用环境 (6) 4.2.输入 (7) 4.3.输出 (7) 5.应用分析及指导 (7) 5.1.应用分析 (7) 5.2.应用指导 (7) 6.测试分部的应用及案例 (9) 6.1.无线测试分部简化实例 (9) 6.1.1.工程方法的输入 (9) 6.1.2.标识输入与输出 (9) 6.1.3.画出因果图 (9) 6.1.4.转换为判定表 (9) 6.1.5.判定表简化 (10) 6.1.6.生成测试项目 (10) 7.相关表格 (10) 8.工具需求 (10) 9.附录 (11) 10.参考文档 (11)

因果图、判定表工程方法 关键词：阶段、活动、工程方法、SDV/SIT、因果图、判定表 摘要：本文详细描述了测试设计过程中因果图、判定表工程方法 缩略语清单：

1. 概述 因果图、判定表是一种充分考虑系统输入之间的组合、约束以及和输出因果关系的用例设计方法。因果图用于描述系统的输入、输出，以及输入和输出之间的因果关系，输入和输入之间的约束关系，因果图的绘制过程是对被测试系统外部特征的建模过程。判定表可以由因果图转换得到，它用于对所有输入进行组合和筛选，并得到对应的输出。 因果图和判定表两种方法在实际使用中结合紧密，往往同时使用，此时可以理解因果图为判定表的前置过程。此外，对于一些简单的系统，或输入与输出已经非常明确的系统，判定表可以单独使用。 因果图和判定表的方法在业界广泛使用，是非常成熟的两种工程方法。它们不仅应用在测试设计过程中，同时在开发设计过程中也有应用。 2. 适用范围 适用阶段： 因果图和判定表的工程方法适用于测试方案设计阶段的特性测试设计活动中使用适用业务： 因果图和判定表的方法是一种通用的测试设计方法，可以适用于所有类型的业务 以下情况下不适宜使用本工程方法： 1.输入和输出不明确，或输入与输出因果关系不明确的情况下。例如从开发的相关文档 中，无法确定输入的有效范围，输入和输出的对应关系时 2.被分析的特性或功能点过于复杂，输入项目很多的情况下。输入项过多会造成因果图和 判定表非常庞大，没有工具辅助的情况下难以操作 3.系统输入之间相互约束少，不需要做大范围的组合测试时不宜使用本工程方法，不然会 产生大量用例冗余 4.系统输入之间存在顺序先后上的可变性，例如两个输入可以交互顺序，并且交互顺序后

判定表+因果图法测试用例设计

第三部分任务3-3附2因果图法 单元名称 3 测试分析设计 任务名称3-3附2因果图法测试用例设计方法 任务描述学习判定表+因果图法设计测试用例的方法，完成测试用例设计学习目标 1. 因果图法测试用例设计方法。 关键词1.判定表 2.因果图。。。。。。 技能点因果图的画法 具体工作任务任务1 自学判定表+因果图法测试用例设计方法 任务-2 完成作业“象棋规则”中关于棋子“马”的落子规则的用例设计(参见作业“因果图法测试作业”) 任务3（附加题）完成“自动售货机”的用例设计 成果提交成果展示： 展示完成的测试用例（可用Excell实现）提交内容： 完成的测试用例 附2作业：因果图法测试作业. 1、象棋游戏规则（针对棋子“馬”）：

1) 如果落点在棋盘外，则不移动棋子 2) 如果落点与起点不构成日字型，则不移动棋子。 3) 如果落点处有自己方棋子，则不移动棋子。 4) 如果落点方向的临近交叉点有棋子（绊马腿），则不移动棋子。 5) 如果不属于1-4条，且落点处无棋子，则移动棋子。 6) 如果不属于1-4条，且落点处为对方棋子（非老将），则移动棋 子并除去对方棋子。 7) 如果不属于1-4条，且落点处为对方老将，则移动棋子，并提示 战胜对方，游戏结束。

（1）使用因果图法列出原因和结果 （2）画出因果图，修改为最简洁的图。注意分析原因之间、结果之间是否有约束关系。 （3）根据因果图列出判定表 （4）根据判定表的中得出的输入数据，写出规范的。 参考步骤： （1）分析数据

测试用例编号棋子落点预期输出备注 原因： 1———— 2———— 。。。。。。 结果： A———— B———— 。。。。。。 （2） 因果图 （3） 判定表 （4） 测试用例 测试用例格式可参照下表 2（附加）、有一个处理单价为5角钱的饮料的自动售货机，相应规格说明如下： 若投入5角钱或1元钱的硬币，按下〖橙汁〗或〖啤酒〗的按 钮，则相应的饮料就送出来。（每次只投入一个硬币，只押下 一种饮料的按钮） 如投入5角的硬币，按下按钮后，总有饮料送出。 若售货机没有零钱找，则一个显示〖零钱找完〗的红灯会亮， 这时再投入1元硬币并按下按钮后，饮料不送出来而且1元硬币 也退出来。 若有零钱找，则显示〖零钱找完〗的红灯不会亮，若投入 1元 硬币及按饮料按钮，则送出饮料的同时找回5角硬币。 （1）使用因果图法列出原因和结果