📄 9.4.5.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<BODY>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.4.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.5_2.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.4.5 归约流图</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
对可归约流图，已提出了好几种定义。这里首先采用的是能显示出可归约流图最重要性质之一的定义，<font class = "emphasize2">即不存在从循环外向循环内的转移，进入循环只有通过它的首结点</font>。
</p>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
<font class = "definition2">可归约流图</font>定义：一个流图是可归约的，当且仅当可以把边分成两个不相交的组，其中一组的边叫做进边；另一组的边叫做回边，并且有如下性质：
</p>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
1、所有进边形成无环有向图，在这个图中，每个结点可以从G的初始结点到达。
</p>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
2、回边组仅由前面所讲的回边组成。
</p>
</td>
</tr>
</table>
<table>
<tr>
<td> </td>
<td class="content">
<font class="example">例9.9</font>
图9.22中左边流图是可归约的。通常，如果知道了流图的dom关系，就可以找出和去掉所有的回边。如果流图可归约，那么剩下的边必定是进边，所以检查流图是否可归约，只要检查所有进边是否构成无环有向图便可以了。对于此流图，如果拿开五条回边４→３，７→４，８→３，９→１和１０→７，很容易看出剩下的图（图9.22中右边）是无环的。<br>
</td>
</tr>
</table>
<p align="center">
<img border="0" src="images/9_20.gif"></p>
<br>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.4.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.5_2.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -