直接的和间接的图
图是什么?
一个图的集合节点和边缘代表关系:
节点是对应于对象的顶点。
边缘是对象之间的关系。
图像边缘有时权重,这表明强度(或其他属性)之间的每个连接节点。
这些定义一般,图中的节点和边的确切含义取决于特定的应用程序。例如,你可以在一个社交网络模型的友谊用图。图节点是人,边代表友谊。图的自然对应物理对象和情况下意味着您可以使用图形模式各种各样的系统。例如:
网页链接——图节点网页,和之间的边表示超链接页面。
机场——图节点是机场,边代表机场之间飞行。
在MATLAB®,图和有向图代表无向和定向图的函数构造对象。
无向图边,没有方向。边缘显示双向关系,可以在两个方向遍历每条边。这个图显示了一个简单的无向图三个节点和三条边。
指示图有边缘的方向。边缘显示单向关系,每条边只能在一个方向遍历。这个图显示了一个简单的有向图有三个节点和两条边。
确切的位置、长度或取向的边缘图说明通常没有意义。换句话说,同一图可以可视化以几种不同的方式重新排列节点和/或扭曲的边缘,只要底层结构不会改变。
Self-loops和油印
图使用图和有向图可以有一个或多个self-loops边连接节点本身。此外,图可以有多个相同的源和目标边缘节点,然后图为称为油印。油印可能会或可能不会包含self-loops。
为了图算法在MATLAB函数,一个图,其中包含一个节点用一个自身环不是油印。但是,如果图包含一个节点多个self-loops,油印。
例如,下图显示了一个无向和self-loops油印。节点有三个self-loops,而C有一个节点。图包含这三个条件,任何一个使油印。
节点有三个self-loops。
他们之间节点A和B有五边。
节点A和C之间的两条边。
确定是否一个给定的图是油印,使用ismultigraph函数。
创建图表
创建一个图的主要方法包括使用邻接矩阵或列表的优势。
邻接矩阵
代表一个图表中的信息的一种方法是用一个正方形邻接矩阵。邻接矩阵中的非零项表示两个节点之间的边,和条目的值表示边缘的重量。邻接矩阵的对角元素通常是零,但非零对角元素表示自身环,或者一个节点连接到本身的优势。
当你使用
图创建一个无向图的邻接矩阵必须是对称的。在实践中,避免重复的矩阵通常是三角形的。构建一个无向图只使用邻接的上或下三角矩阵,使用图(一个“上”)或图(一个“低”)。当你使用
有向图创建一个有向图的邻接矩阵不需要对称的。对于大的图,邻接矩阵包含了许多0和通常是一个稀疏矩阵。
您不能创建一个多重图的邻接矩阵。
例如,考虑这样的无向图。
你可以代表这个邻接矩阵的图:
在MATLAB构造图,输入:
一个= [0 1 2;1 0 3;2 3 0];node_name = {“一个”,“B”,“C”};图G = (node_name)
图G =属性:边缘:[3×2表]节点:(3×1表)
您可以使用图或有向图使用邻接矩阵函数来创建一个图形,或者您可以使用邻接函数来找到加权或未加权的稀疏的既存图的邻接矩阵。
边列表
代表一个图表中的信息的另一种方法是通过列出所有的边缘。
例如,考虑相同的无向图。
现在代表边缘图的列表
从边缘列表图很容易得出这样的结论:有三个独特的节点,一个,B,C,它被列出的三个边缘连接。如果图断开连接的节点,他们不会发现在边缘列表中,并分别必须被指定。
在MATLAB中,边缘由列分隔的列表源节点和目标节点。为有向图的边缘方向(从源到目标)是很重要的,但对于无向图源和目标节点是可以互换的。使用边缘列表构造这个图的一个方法是使用单独的源节点,输入目标节点和边的权值:
source_nodes = {“一个”,“一个”,“B”};target_nodes = {“B”,“C”,“C”};edge_weights = (1 2 3);图G = (source_nodes target_nodes edge_weights);
这两个图和有向图允许一个简单的图形或建设油印的边缘列表。构建一个图后,G,你可以看看边缘(及其属性)命令G.Edges。边的顺序G.Edges由源节点排序(第一列)和次要目标节点(第二列)。对于无向图,较小的节点索引被列为源节点,节点和更大的指数列为目标节点。
从底层实现图和有向图取决于稀疏矩阵,许多相同的索引应用成本。使用前面的方法构建一个图形从三联体双一次(来源、目标、重量)比创建一个空的快图和迭代添加更多的节点和边。为获得最佳性能,减少调用的数量图,有向图,addedge,addnode,rmedge,rmnode。
图节点id
默认情况下,所有的节点在使用创建图表图或有向图已经屈指可数了。因此,你总是可以参考他们的数值节点索引。
如果图节点名(即G.Nodes包含一个变量的名字),然后你也可以参考图中的节点使用他们的名字。因此,命名为图中的节点可以被他们的节点指标或节点的名称。例如,节点1可以被称为“一个”。
这个词节点ID包括节点识别的这两个方面。节点ID是指索引节点和节点名。
为了方便起见,MATLAB记得哪种类型的节点ID使用当你叫大多数图的功能。如果你指的是图中的节点的节点指标,大多数图形函数返回一个数字回答这个指标还指的是节点。
一个= [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单元阵列{a} {' c '} {' d '}
使用findnode找到数字节点ID对于一个给定的节点名称。相反,对于一个给定的数字节点ID,指数G.Nodes.Name确定相应的节点名称。
修改或查询现有的图
在您构建一个图或有向图对象,您可以使用多种功能来修改图形结构来确定有多少个节点或边缘图。此表列出了一些可用的函数修改或查询图和有向图对象。
addedge |
添加一个或多个边缘图 |
rmedge |
删除一个或多个边缘图 |
addnode |
添加一个或多个节点图 |
rmnode |
删除一个或多个节点图 |
findnode |
定位一个特定的节点图 |
findedge |
在一个图形定位一个特定的优势 |
numnodes |
找到一个图中节点的数目 |
numedges |
找到图的边的数量 |
edgecount |
指定的节点之间的边数 |
flipedge |
相反的方向有向图边缘 |
reordernodes |
交换节点的顺序图 |
子图 |
提取子图 |
看到修改现有图的节点和边对一些常见的图修改的例子。
