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

有向图和无向图

什么是图表?

一个图表是一个集合节点和边缘代表关系:

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

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

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

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

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

$显示无向图和无向边的图。$
指示图有方向的边。这些边表示单向关系，因为每条边只能沿着一个方向穿过。这个图显示了一个简单的有向图，有三个节点和两条边。

$表示具有单向边的有向图的绘图。$

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

Self-loops和油印

图使用图和有向图可以有一个或多个self-loops，这些边连接着一个节点和它自己。此外，图可以具有具有相同源节点和目标节点的多条边，然后将图称为a油印．多图可能包含也可能不包含自循环。

为了在MATLAB中实现图算法函数，一个包含单自循环节点的图不是一个多图。但是，如果图中包含一个节点多个自循环，这是一个多重图。

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

节点A有三个自循环。
节点A和节点B之间有五条边。
结点A和C之间有两条边。

$显示多重图的图。节点A与节点B之间有多条边连接，节点A也有几个自环。$

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

创建图表

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

邻接矩阵

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

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

例如，考虑这个无向图。

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

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

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

在MATLAB中构造图形，输入:

A = [0 1 2;1 0 3;2 3 0];node_name = {“一个”，“B”，“C”};图G = (node_name)

G = graph with properties: Edges: [3×2 table] Nodes: [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;1 0 1 0;1 1 0 1;0 0 1 0];图G = (A, {“一个”，“b”，“c”，' d '}）;p = shortestpath (G, 1, 4)

P = 1 3 4

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

p1 = shortestpath (G,“一个”，' d '）

P1 = 1×3 cell array {'a'} {'c'} {'d'}

使用findnode查找给定节点名的数字节点ID。相反，对于给定的数字节点ID，索引intoG.Nodes.Name以确定相应的节点名。

修改或查询已存在的图形

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

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