有向图

来自计算思维百科
跳转至: 导航搜索
有向图1.png

在一幅图中如果所有边都是有方向的,这幅图就称为有向图。

基本概念

有向图是一个二元组<V,E>,其中

1.V是非空集合,称为顶点集。V中元素称为顶点或结点。

2.E是V×V的子集,称为弧集。其元素称为有向边。

直观来说,若图中的每条边都是有方向的,则称为有向图。有向图中的边是由两个顶点组成的有序对,有序对通常用尖括号表示,如<vi,vj>表示一条有向边,其中vi是边的始点,vj是边的终点。<vi,vj>和<vj,vi>代表两条不同的有向边。

如果n个顶点的有向图有n(n-1)条边,则此图称为完全有向图。在有 n个顶点的有向图中,每个顶点的度最大可达 2(n-1)

应用范围

有向图是描述一项工程或系统的进行过程的有效工具。几乎所有的工程(project)都可分为若干个称作活动(activity)的子工程,而这些子工程之间,通常受着一定条件的约束。对整个工程和系统,人们关心的是两个方面的问题:一是工程能否顺利进行:二是估算整个工程完成所必须的最短时间。具体可用于计划、施工过程、生产流程、程序流程等。

使用方法及步骤

用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系。

应用案例

应用1-排课表

案例:

某校计算机学院要给本院学生安排大学期间的课表,由于课程之间有着一定的联系,现在请你设计出开课计划。

解决步骤:

先用表格列出该计算机学院的所有必修课程,并确定它们之间的关系。列表如下:

课程代号

课程名称

先修课

A

程序设计基础

B

计算机导论

A

C

数据结构

A、B

D

Java程序设计

A

E

语言的设计与分析

C、D

F

计算机原理

K

G

编译原理

C、E

H

操作系统

C、F

I

高等数学

J

线性代数

I

K

大学物理

I

L

数值分析

A、I、J

把表格转换成有向图:

有向图2.png

于是,可以清晰地得出这几门课的开课顺序:A课程和I课程可以同时先开, B、D、K、J这四门课程紧接,随后是C、L、F课程,再到E、H,最后是G课程。这样用图来表示之后,大概的安排情况就呈现出雏形了。

应用2-房子装修工程安排

案例:

小明初次购买了一套房子,现在需要对它进行装修,可是太多的工序让他觉得心力交瘁,希望你来帮助他理一下思路,避免工序步骤出错并尽量减少装修的时间。

解决步骤:

我们知道,装修大致是按照以下工序来完成的:

主体拆改→水电改造→木工→贴砖→刷墙面漆→热水器安装→厨卫吊顶→橱柜安装→木门安装→地板安装→开关插座安装→灯具安装→五金洁具安装→窗帘杆安装→家具进场→家电安装→家具配饰。

但是,以上工序中有一些事可以同时进行的,而某些工序之间是有必然的联系的,所以他们之间可能会有先后关系。我们可以按照专业知识来根据实际情况像以上案例一样列表,然后把它转化为有向图,那么整个工程都会变得清晰有条理了。

可以体现的计算思维

用有向图来解决问题体现了计算思维的抽象思想,把整个工程抽象成图,从而使整个过程都清晰易懂,对解决工程的问题有很大的帮助。