图论绘图软件教程

图论绘图软件基本功能的简单描述：

本次设计所要解决和研究的是利用java语言编程实现web页面上图论中图的绘制。用户界面具备图论中基本的作图功能。通过创造鼠标事件，使用户在选择绘制某种类型的图之后，可以直接用鼠标在规定的界面上进行绘图。如果用户想完成加权图的绘制，系统可以做出相应的反应来方便用户对某一条边进行加权，从而绘制出用户想要的加权图。对于用户完成的图，可以查看它对应的矩阵。同时，可以直接输入矩阵，来让系统自动生成图。

图论绘图软件设计思想：

一、图

图由一个顶点集合一个边集组成，其中边将一对不同顶点连接在一起（而且至多只能有一条连接了某一对顶点的边）。在一个有V个顶点的图中，用0到V-1作为各顶点的名字。在V个任意顶点的名字与从0到V-1的V个整数之间建立起一对一的映射。在此约定，一个给定图的顶点总数表示为V，而边数则表示为E。

我们将图的这一定义作为标准，不过需要说明：首先，在此不允许出现多重边的情况：其次，此定义不允许出现顶点连至顶点自身的边，这种边称为自环。无平行边或自环的图有时称为简单图。我们在正式定义中使用的是简单图，其原因是这更易于表现其基本属性，而且在许多应用中都不需要平行边和自环。

若一条边连接了两个顶点，则称这两个顶点相互邻接，而该边则依附于两个顶点。顶点的度即为依附于该顶点的边的个数。我们用V-W的记法来表示一条连接顶点V和W的边；也可以采用另一种记法，即W-V，来表示同一条边。通过将顶点标记为点，并将点间连线来表示边，以此可以画出一个图。绘图能够使我们对图的结构有直观的认识。将一个给定图的顶点放在平面上并画出这些点和将其连接的边，这就称为绘图。放置顶点的可能方式、边的绘制样式以及绘制中的美学约束可谓不计其数。与不同自然约束相关的绘图算法得到了深入的研究，而且也有了许多成功的应用。例如，最简单的约束就是边不能交叉。平面图是可以在平面上绘制，而且不出现任何边交叉的图。

到此为止所定义的图为无向图。在有向图中，边都是单向的。可以将定义每条边的一对顶点考虑为一个序偶，他指定了一个单向的邻接关系，对此我们可以由第一个顶点到达第二个顶点，但无法从第二个顶点到达第一个顶点。我们将有向图的边称为有向边。将有向边绘制为由原点指向终点的箭头，并通常称之为边指向终点。在有向图中使用V-W的记法时，表示这是一条由V指向W的边，它与W-V有所区别，后者表示一条由W指向V的边。对于顶点还要谈及出度和入度（分别为以其作为终点的边的个数和以其作为源点的边的个数）。

二、邻接矩阵

图的邻接矩阵表示是一个元素为布尔值的矩阵，若在图中存在一条连接顶点V和W的边，则将V行、W列的元素定义为1，否则定义为0。如果有一条连接顶点V和顶点W的边则在V行、W列上有一个1（true）。如果没有一个这样的边，则V行、W列上有一个0（false）。此矩阵式关于对角线对称的。图初始化时，接口要求用户知道顶点的个数。如果需要，还允许插入和删除顶点。JAVA通过将矩阵的所有元素均置为false来自动初始化矩阵。

三、有向图

对于图中的每条边若强调其两个顶点的重要性我们就得到了一个完全不同的组合对象，称为有向图。在有向图中，S-T的记法表示一条从S到T的边，但是对于是否存在一条从S到T的边则没有提供任何信息。在一个有向图中，两个顶点可能的关联方式有4种：不存在边；存在一条从S到T的边S-T；存在一条从T到S的边T-S；或者存在两条边，分别为S-T和T-S，这表示在两个方向上都有连接。

有向图是由一个顶点集和一个有向边集组成，其中有向边连接一对有序顶点（无重复边）。我们称一条边从其第一个顶点指向其第二个顶点。与无向图定义类似，在此定义中不允许出现重复边。有向图中一条有向路经为一个顶点序列，其中由一条（有向的）有向图边将此序列中的每一个顶点与其后续相连接。如果有一条从S到T的有向路经，我们则称顶点T由顶点S可达。

用于有向图的表示与无向图所用的表示基本上是相同的，实际上，由于对每条边只表示一次，在此则更为直接。在邻接矩阵表示中，我们需要维护一个完全的矩阵，并且将边S-T表示为S行、T列上的一个true位。除非还存在一条边T-S，否则不会在T行、S列上也设置一个true位。一般而言，有向图的邻接矩阵并不关于对角线对称。

图论绘图软件使用说明：

一、手动绘图功能：

点击“画图”，会出现一个下拉菜单；

点击“画图”菜单下的“简单图”，即可在下方的界面上进行鼠标绘图；

※画图的方式是这样的：

首先用户单击一个按钮，并将鼠标移动到要画图的起始位置，按下鼠标，然后开始拖动鼠标，一直拖到图形的结束点，然后释放鼠标，鼠标弹起后，图形就绘制好了。需要注意的是，在没有释放鼠标时图形并没有被真正绘出，只有当鼠标被释放后才显示出的图形。（鼠标停在某个结点上时，会变成＋）

点击“画图”菜单下的“加权图”，即可在下方的界面上进行鼠标绘制加权图；

※对于有权图，会自动跳出权值输入窗口，加权图的画图方式与简单图相同，通过拖动鼠标完成点和边绘制，在每绘制一条边（即鼠标释放后）自动弹出的窗口内输入权数；

点击“画图”菜单下的“修改”，即可删除一条边（双击你所要删除的边）；

图形绘制完成后，点击“画图”菜单下的“获取矩阵”，可在弹出窗口中看到该图对应的矩阵；

二、输入矩阵自动绘图功能：

点击“矩阵”菜单，在弹出窗口中输入顶点个数，然后再下方的矩阵表中输入你所想要的边的链接（简单图输入0或1），

点击“生成图”，系统即可自动绘制图。