图是集合节点和边缘代表关系:
节点是与对象对应的顶点。
边缘是对象之间的连接。
图的边有时有权重,它表示节点之间的每个连接的强度(或其他属性)。
这些定义是通用的,因为图中节点和边的确切含义取决于具体的应用程序。例如,您可以使用图表对社交网络中的友谊进行建模。图中的节点是人,边代表友谊。图与物理对象和情况的自然对应意味着您可以使用图来建模各种各样的系统。例如:
网页链接——图形节点是网页,边缘表示网页之间的超链接。
机场——图形节点是机场,边缘表示机场之间的航班。
在matlab.®,图
和dig
函数构造表示无向图和有向图的对象。
无向图有没有方向的边。边表示双向关系,因为可以在两个方向上遍历每个边缘。该图显示了一个简单的无向图,具有三个节点和三个边。
指示图有方向的边缘。边表示单向关系,因为每个边缘只能遍历一个方向。该图显示了一个简单的有向图,其中三个节点和两个边。
图形插图中边缘的确切位置、长度或方向通常没有意义。换句话说,只要底层结构不发生变化,相同的图形可以通过重新安排节点和/或扭曲边缘以几种不同的方式进行可视化。
图使用图
和dig
可以有一个或多个自我环,这是将节点连接到自身的边缘。另外,图形可以具有具有相同源和目标节点的多个边缘,然后将图形称为a多金属.多重图可能包含也可能不包含自循环。
出于MATLAB中的图形算法函数的目的,包含具有单个自循环的节点的图形不是多重素。但是,如果图表包含一个节点多自循环,这是一个多重图。
例如,下图显示了具有自循环的无向多角形。节点A有三个自循环,而节点C具有一个。该图包含这三种条件,其中任何一个都使其成为多层游文。
节点A有三个自环。
节点A和B在它们之间有五个边缘。
节点A和节点C之间有两条边。
要确定给定的图是否是多重图,请使用ismultigraph
函数。
创建图的主要方法包括使用邻接矩阵或边表。
在图中表示信息的一种方法是使用正方形邻接矩阵.邻接矩阵中的非零项表示两个节点之间的一条边,该项的值表示该边的权值。邻接矩阵的对角元素通常为零,但非零对角元素表示a自循环,或者一个通过边与自身连接的节点。
当你使用图
要创建一个无向图,邻接矩阵必须是对称的。在实践中,矩阵通常是三角形的,以避免重复。要只用邻接矩阵的上三角形或下三角形构造无向图,使用图(一个“上”)
或图(一个“低”)
.
当你使用dig
为了创建一个有向图,邻接矩阵不需要是对称的。
对于大型图,邻接矩阵包含许多零,通常是一个稀疏矩阵。
不能用邻接矩阵创建多重图。
例如,考虑这个无向图。
你可以用这个邻接矩阵来表示这个图:
在MATLAB中构造图形,输入:
A = [0 1 2;1 0 3;2 3 0];node_name = {“一个”,“B”,“C”};图G = (node_name)
g =带有属性的图形:边缘:[3×2表]节点:[3×1表]
你可以使用图
或dig
函数用邻接矩阵来创建图,也可以用邻接
用于找到预先存在的图表的加权或未加权稀疏邻接矩阵的功能。
代表图中信息的另一种方法是通过列出所有边缘。
例如,考虑同一个无向图。
现在用边列表表示这个图
从边表很容易得出结论,图有三个唯一的节点,一个
,B
, 和C
,由三个列出的边缘连接。如果图表具有断开连接节点,则不会在边缘列表中找到它们,并且必须单独指定。
在MATLAB中,边的列表是按列分割成的源节点和目标节点。对于有向图,边缘方向(从源到目标)很重要,但对于无向图,源和目标节点是可互换的。使用边列表构造此图的一种方法是使用源节点、目标节点和边权值的单独输入:
source_nodes = {“一个”,“一个”,“B”};target_nodes = {“B”,“C”,“C”};Edge_weights = [1 2 3];g = graph(source_nodes,target_nodes,Edge_weights);
这两个图
和dig
允许从边表构造一个简单图或多重图。在构造一个图之后,G
,您可以使用命令查看边缘(及其属性)G.Edges.
.边缘的顺序G.Edges.
按源节点(第一列)排序,并由目标节点(第二列)分组。对于无向图形,具有较小索引的节点被列为源节点,并且具有较大索引的节点被列为目标节点。
自潜在实施以来图
和dig
依赖于稀疏矩阵,许多相同的索引成本适用。使用前面的一种方法从三联体一次构造一个图(来源、目标、重量)
比创建空图形更快,并迭代地添加更多节点和边。为了获得最佳性能,最大限度地减少呼叫数量图
,dig
,addedge
,addnode
,rmedge.
, 和rmnode
.
默认情况下,图中的所有节点使用图
或dig
编号。因此,您始终可以通过它们的数字引用它们节点索引.
如果图有节点名(即,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,索引到g.nodes.name.
确定相应的节点名称。
在构造一个图
或dig
对象,您可以使用各种功能来修改图形结构或确定图表具有多少节点或边缘。此表列出了用于修改或查询的一些可用功能图
和dig
对象。
addedge |
将一个或多个边缘添加到图形 |
rmedge. |
从图中删除一个或多个边缘 |
addnode |
将一个或多个节点添加到图形 |
rmnode |
从图中删除一个或多个节点 |
findnode |
在图中找到特定的节点 |
查找结识 |
在图中找到特定边缘 |
numnodes. |
找出图中节点的数量 |
numedges. |
求图中的边数 |
edgecount. |
指定节点之间的边数 |
flipedge |
反转有向图边的方向 |
reordernodes. |
排列图中节点的顺序 |
sub |
提取子图 |
看到修改现有图的节点和边缘对于一些常见的图形修改例子。