有向和无向图- MATLAB & Simulink - MathWorks Espa金宝appña - 金宝app,下载188bet金宝搏,金宝搏官方网站

有向图和无向图

什么是图?

图是的集合节点而且边缘表示关系的:

节点是对应于对象的顶点。
边缘是对象之间的连接。
图边有时是这样权重，表示节点之间每个连接的强度(或其他属性)。

这些定义是通用的，因为图中节点和边的确切含义取决于具体的应用程序。例如，您可以使用图表来模拟社交网络中的友谊。图中的节点代表人，边缘代表友谊。图与物理对象和情况的自然对应关系意味着您可以使用图来为各种各样的系统建模。例如:

网页链接-图节点是网页，边表示页面之间的超链接。
机场——图中的节点是机场，边缘代表机场之间的航班。

在MATLAB^®,图而且有向图函数构造表示无向图和有向图的对象。

无向图有没有方向的边。这些边表示双向关系，因为每条边都可以在两个方向上遍历。该图显示了一个简单的无向图，有三个节点和三条边。

$显示具有无向边的无向图的图形。$
指示图有方向的边。这些边表示单向关系，因为每条边只能在一个方向上遍历。该图显示了一个具有三个节点和两条边的简单有向图。

$显示具有单向边的有向图的图形。$

图形插图中边缘的确切位置、长度或方向通常没有意义。换句话说，只要底层结构不改变，通过重新排列节点和/或扭曲边缘，可以以几种不同的方式来可视化相同的图形。

自循环和多重图

使用图而且有向图可以吃一个或多个吗self-loops，它们是连接节点与其自身的边。此外，图可以有多条边，具有相同的源节点和目标节点，然后该图被称为油印．多重图可能包含也可能不包含自循环。

对于MATLAB中的图算法函数，包含一个具有单个自循环的节点的图不是多重图。但是，如果图中包含节点多个自循环，它是一个多重图。

例如，下图显示了一个具有自循环的无向多重图。节点A有三个自环，节点C有一个自环。这个图包含这三个条件，其中任何一个都使它成为一个多重图。

节点A有3个自环。
节点A和B之间有5条边。
节点A和节点C之间有两条边。

$显示多重图的图形。节点A和节点B之间有多条边相连，节点A也有多条自环。$

要确定给定的图是否为多重图，请使用ismultigraph函数。

创建图表

创建图的主要方法包括使用邻接矩阵或边列表。

邻接矩阵

在图中表示信息的一种方法是用正方形邻接矩阵．邻接矩阵中的非零项表示两个节点之间的边，该项的值表示边的权值。邻接矩阵的对角线元素通常为零，但非零对角线元素表示a自身环，或者是一个通过边与自身相连的节点。

当你使用图为了创建一个无向图，邻接矩阵必须是对称的。在实践中，矩阵通常是三角形的，以避免重复。若要仅使用邻接矩阵的上三角形或下三角形构造无向图，请使用图(一个“上”)或图(一个“低”)．
当你使用有向图为了创建一个有向图，邻接矩阵不需要是对称的。
对于大图，邻接矩阵包含许多零，通常是一个稀疏矩阵。
不能从邻接矩阵创建多重图。

例如，考虑这个无向图。

$显示具有三个节点和三条边的无向图的图形。边AB的权值为1，边AC的权值为2，边BC的权值为3。$

你可以用这个邻接矩阵来表示这个图:

$（ \begin{matrix} 0 & 1 & 2 \\ 1 & 0 & 3. \\ 2 & 3. & 0 \end{matrix} ）．$

在MATLAB中构建图，输入:

A = [0 1 2;10 0 3;2 3 0];Node_names = {“一个”，“B”，“C”};G = graph(A,node_names)

G =具有属性的图:边:[3×2 table]节点:[3×1 table]

您可以使用图或有向图函数使用邻接矩阵创建图形，或者可以使用邻接函数来查找先前存在的图的加权或非加权稀疏邻接矩阵。

边列表

在图中表示信息的另一种方法是列出所有边。

例如，考虑相同的无向图。

$显示具有三个节点和三条边的无向图的图形。边AB的权值为1，边AC的权值为2，边BC的权值为3。$

现在用边表表示这个图

$\begin{array}{l} 边缘的重量 \\ \begin{matrix} \begin{matrix} （一个， B ） \\ （一个， C ） \end{matrix} & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} 1 \end{matrix} \end{matrix} \end{matrix} \\ \begin{matrix} \begin{matrix} \begin{matrix} 2 \end{matrix} \end{matrix} \end{matrix} \end{matrix} \\ （ B ， C ） & \begin{matrix} \begin{matrix} \begin{matrix} 3. \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{array}$

从边表中很容易得出结论，图有三个唯一的节点，一个，B,C，它们由列出的三条边连接。如果图中有断开连接的节点，它们将不会在边缘列表中找到，并且必须单独指定。

在MATLAB中，边的列表是按列分割成的源节点和目标节点。对于有向图，边缘的方向(从源到目标)是重要的，但对于无向图，源节点和目标节点是可互换的。使用边列表构造这个图的一种方法是对源节点、目标节点和边权值使用单独的输入:

Source_nodes = {“一个”，“一个”，“B”};Target_nodes = {“B”，“C”，“C”};Edge_weights = [1 2 3];G = graph(source_nodes, target_nodes, edge_weights);

这两个图而且有向图允许从边表构造简单图或多重图。在构造一个图之后，G，您可以使用命令查看边缘(及其属性)G.Edges．边的顺序G.Edges按源节点(第一列)排序，其次按目标节点(第二列)排序。对于无向图，索引较小的节点被列为源节点，索引较大的节点被列为目标节点。

自底层实现图而且有向图取决于稀疏矩阵，许多相同的索引成本适用。使用前面的方法之一从三联体对一次构造一个图(来源、目标、重量)比创建一个空图并迭代添加更多的节点和边更快。为了获得最佳性能，尽量减少调用的次数图，有向图，addedge，addnode，rmedge,rmnode．

节点id

默认情况下，图中的所有节点都是使用图或有向图已经屈指可数了。因此，您总是可以通过它们的数字来引用它们节点索引．

如果图有节点名(即，G.Nodes包含一个变量的名字)，然后您也可以使用它们的名称来引用图中的节点。因此，图中的已命名节点可以通过它们的节点索引或节点名来引用。例如，节点1可以被称为，“一个”．

这个词节点ID包含节点标识的两个方面。节点ID包括节点索引和节点名称。

为了方便起见，MATLAB记得在调用大多数图函数时使用哪种类型的节点ID。因此，如果您通过节点索引引用图中的节点，大多数图函数将返回一个数字答案，该答案也通过节点索引引用节点。

A = [0 1 1 0;10 0 10 0;1 1 0 1;0 0 10 0];G =图(A，{“一个”，“b”，“c”，' d '});p = shortestpath(G,1,4)

P = 1 3 4

但是，如果按节点名称引用节点，则大多数图函数返回的答案也按节点名称引用节点(包含在字符向量或字符串数组的单元格数组中)。

p1 =最短路径(G，“一个”，' d '）

P1 = 1×3单元格数组{'a'} {'c'} {'d'}

使用findnode查找给定节点名称的数字节点ID。相反，对于给定的数值节点ID，索引到G.Nodes.Name来确定相应的节点名称。

修改或查询已有图

在你构建了图或有向图对象时，您可以使用各种函数来修改图的结构或确定图有多少个节点或边。该表列出了一些可供修改或查询的函数图而且有向图对象。

`addedge`	向图形中添加一条或多条边
`rmedge`	从图形中删除一条或多条边
`addnode`	向图中添加一个或多个节点
`rmnode`	从图中删除一个或多个节点
`findnode`	定位图中的特定节点
`findedge`	定位图中的特定边
`numnodes`	找出图中的节点数
`numedges`	求图中的边数
`edgecount`	指定节点之间的边数
`flipedge`	反转有向图边的方向
`reordernodes`	打乱图中节点的顺序
`子图`	提取子图

看到修改现有图的节点和边对于一些常见的图修改示例。

另请参阅

图|有向图