Igraph入门指南 6

3、make_系列:igraph的建图工具

按照定义,正则图是指各顶点的度均相同的无向简单图,因为我目前没有找到描述度相等的有向(或自环图)的标准名称,所以在本文中借用一下这个概念,并加上定语有向无向,用以描述那些图中所有顶点度相同的有向图或无向图,包括简单图和多重图。

3-1 弦环图:make_chordal_ring(),返回无向正则图,d=4

我不是学数学的,平时用不上这个概念。百度半天,没有满意的解答。在igraph官网中找到这样一句话:

A graph is chordal if and only if any two neighbors of a vertex which are higher in rank than it are connected to each other.翻译过来,是图是弦图,当且仅当比一个顶点的秩高的任意两个邻居会彼此连接。

这里顶点的秩(rank)似乎指数按照顶点ID排序得到的顺序数。这种图的创建方法,首先创建一个环图,然后按照参数w的值,为图添加边,从而创建一个正则图(图中各个顶点的度相同)。因为得到的是一个正则图,所以各个顶点的度都相同,也就是参数矩阵的元素个数。而矩阵中的元素值,则规定了对应的顶点具体和图中哪些顶点连接而生成边。

igraph包帮助文档翻译过来大致是:

创建一个扩展弦环。扩展弦环是正则图,每个节点都有相同的度。它可以通过添加矩阵指定的一些额外边从简单环中获得。设p表示“W”矩阵中的列数。顶点i的额外边是根据“W”中的列i mod p添加的。额外边的数量是“W”中的行数:对于每一行j,如果i+W[ij]小于总节点的数量,则添加一条边i->i+W[ij]

虽然里面说了怎样计算,但我水平太低,没整明白,主要是平时用不上。
在这里插入图片描述

3-2 德布鲁因图:make_de_bruijn_graph,返回有向正则图(d=2m)

德布鲁因图可以百度出很多链接,据说是目前二代测序组装基因组的工具的核心基础,但对我这种小白而言太高大上了,用不上。

igraph帮助文档说:德布鲁因图表示字符串之间的关系。使用m个字母的字母表,并考虑长度为n的字符串。一个顶点对应于每一个可能的字符串,如果v的字符串可以通过删除其第一个字母并在其上附加一个字母来转换为w的字符串,则从顶点v到顶点w有一条有向边。请注意,该图将有m到n次方的顶点,甚至有更多的边,所以你可能不想为m和n提供太大的数字。

> g <- make_de_bruijn_graph(3,3)
> table(degree(g))
6 
27 

在这里插入图片描述

德布鲁因图是正则图,每个顶点的度是make_de_bruijn_graph(m, n)中参数m的两倍(2m),顶点总数是m的n次方。

3-3 完全图: make_full_graph返回无向正则图,d=gorder(g)

假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。
在这里插入图片描述

3-4 完全引文图:make_full_citation_graph,返回有向正则图(d=gorder(g)-1)

在这里插入图片描述

> g <- make_full_citation_graph(10)
> print_all(g)
IGRAPH f03e9bf D--- 10 45 -- Full citation graph
+ attr: name (g/c)
+ edges:
 1 ->                      2 -> 1                
 3 -> 1 2                  4 -> 1 2 3            
 5 -> 1 2 3 4              6 -> 1 2 3 4 5        
 7 -> 1 2 3 4 5 6          8 -> 1 2 3 4 5 6 7    
 9 -> 1 2 3 4 5 6 7 8     10 -> 1 2 3 4 5 6 7 8 9
3-5 空图:make_empty_graph

igraph中,空图是不含边的图,所以,本函数可以设置顶点数、是否有向。
在这里插入图片描述

3-6 Prufer序列:make_from_prufer

根据知乎:Prufer序列,又称Prufer code。

对于一棵n(n>=2) 个节点的标定树(节点带编号),其Prufer序列是一个长度为 n-2 ,值域为[1,n] 的整数序列。

每棵树必定存在Prufer序列且唯一,每个Prufer序列对应的树也必定存在且唯一,即二者为双射关系。

将树转化为Prufer序列:

①从树上选择编号最小的叶子节点,序列的下一位为其父节点的编号。

②删去该叶子节点。

③重复①和②,直到树只剩下两个节点,此时序列的长度刚好为n-2

在这里插入图片描述

上图中,1中所有叶节点包括1、4、5、6、7,其中最小的是节点1;

2中,删除叶节点1,并把节点1的父节点编号2存入Prufer序列,序列更新为:2

3中,删除当前最小的叶节点4,并把节点4的父节点编号2存入Prufer序列:2,序列更新为:2,2

4中,删除当前最小的叶节点5,并把节点5的父节点编号3存入Prufer序列:3,序列更新为:2,2,3

5中,删除当前最小的叶节点6,并把节点5的父节点编号3存入Prufer序列:3,序列更新为:2,2,3,3

6中,删除当前最小的叶节点3,并把节点3的父节点编号2存入Prufer序列:3,序列更新为:2,2,3,3,2,至此,树只剩下两个节点,算法结束。

Prufer序列的性质:

1)构造完后剩下的两个节点里,一定有一个是编号最大的节点。

2)对于一个 n度的节点,其必定在序列中出现 n-1次,因为每次删去其子节点它都会出现一次,最后一次则是删除其本身。一次都未出现的是原树的叶子节点。

igraph是这样做的:

如果图有两个以上的顶点,请找到一个阶度为1的顶点(等同叶节点),将其从树中移除,并将其连接到的顶点的标签添加到序列中。重复此操作,直到剩余图形中只有两个顶点为止。

> g <- make_tree(13,3)
> plot(g,layout=layout_as_tree)
> to_prufer(g)
 [1] 2 2 2 1 3 3 3 1 4 4 4

在这里插入图片描述

3-7 二部图:make_full_bipartite_graph
g <- make_full_bipartite_graph(2, 3)
plot(g,layout=layout.bipartite)

在这里插入图片描述

本函数默认参数有from_type\to_type,用于设置边的方向

> g <- make_full_bipartite_graph(2, 3,directed = TRUE,mode = 'in')
> plot(g,layout=layout.bipartite)
> igraph::as_long_data_frame(g)
  from to from_type to_type
1    3  1      TRUE   FALSE
2    4  1      TRUE   FALSE
3    5  1      TRUE   FALSE
4    3  2      TRUE   FALSE
5    4  2      TRUE   FALSE
6    5  2      TRUE   FALSE
3-7 特殊结构图:make_graph
  • Bull:公牛图有5个顶点和5条边,如果绘制得当,它类似于公牛的头部
    在这里插入图片描述

Chvatal:这是最小的无三角形图,既是4色图,也是4-正则图。根据Grunbaum猜想,对于每m>1和n>2,存在一个具有n个顶点的m-正则m-色图。Chvatal图是m=4和n=12的一个例子。它有24条边。
在这里插入图片描述

  • Coxeter:具有28个顶点和42条边的非Hamilton三次对称图
    在这里插入图片描述

  • Cubical:立方体的柏拉图图形。一种有8个顶点和12条边的凸正多面体。
    在这里插入图片描述

  • Diamond:一个有4个顶点和5条边的图,如果正确绘制,则类似于示意图中的菱形
    在这里插入图片描述

  • Dodecahedron:具有20个顶点和30条边的另一个柏拉图式实体。
    在这里插入图片描述

  • Folkman:具有最小顶点数、20和40条边的半对称图。半对称图是正则的,边可传递的,而不是顶点可传递的

在这里插入图片描述

  • Franklin:这是一个嵌入到克莱因瓶上的图,它可以用六种颜色来着色,它是对克莱因瓶Heawood猜想必要性的反例。它有12个顶点和18条边。
    在这里插入图片描述

  • Frucht:Frucht图是最小的三次图,其自同构群仅由单位元素组成。它有12个顶点和18条边
    在这里插入图片描述

  • Grotzsch:是一个无三角形图,有11个顶点,20条边,色数为4。它是以德国数学家Herbert Groetzsch的名字命名的,它的存在证明了平面性的假设在Groetzsh定理中是必要的,即每个无三角形平面图都是3-色的
    在这里插入图片描述

  • Heawood:是一个有14个顶点和21条边的无向图。图是三次图,图中的所有循环都有六条或更多条边。每一个较小的三次图都有较短的循环,所以这个图是6笼,周长为6的最小三次图
    在这里插入图片描述

  • Herschel:是最小的非哈密尔顿多面体图。它是11个节点上唯一的此类图,具有18条边
    在这里插入图片描述

  • House:是一个5顶点、6边的图,如果直接绘制,基本上是正方形顶部的三角形
    在这里插入图片描述

  • HouseX:House图的正方形中带有X。5个顶点和8条边。
    在这里插入图片描述

  • Icosahedron:二十面体,具有12个顶点和30条边的柏拉图式实体
    在这里插入图片描述

  • Krackhardt kite:一个有10个顶点和18条边的社交网络
    在这里插入图片描述

  • Levi:该图是一个4弧传递三次图,它有30个顶点和45条边
    在这里插入图片描述

  • McGee:麦基图是唯一的3-正则7-笼图,它有24个顶点和36条边。
    在这里插入图片描述

  • Meredith:是一个在70个节点和140条边上的四次图,这是对每个4-正则4-连通图都是Hamilton图的猜想的反证。
    在这里插入图片描述

  • Noperfectmatching:一个有16个顶点和27条边的连通图,不包含完全匹配。图中的匹配是一组成对的不相邻边;也就是说,没有两条边共享一个公共顶点。完美匹配是覆盖图的所有顶点的匹配
    在这里插入图片描述

  • Nonline:一个图的连通分量是图中作为顶点诱导子图存在的9个图,它构成了一个非线性图。它有50个顶点和72条边。
    在这里插入图片描述

  • Octahedron:具有6个顶点和12条边的八面体柏拉图立体
    在这里插入图片描述

  • Petersen:一个有10个顶点和15条边的3-正则图。它是最小的次哈密尔顿图,即它是非哈密尔顿的,但从中去掉任何一个顶点都使它成为哈密尔顿的

在这里插入图片描述

  • Robertson:唯一的(4,5)-笼图,即周长为5的4-正则图。它有19个顶点和38条边。

在这里插入图片描述

  • Smallestcyclicgroup:一个最小的非平凡图,其自同构群是循环的。它有9个顶点和15条边
    在这里插入图片描述

  • Tetrahedron:具有4个顶点和6条边的柏拉图立体
    在这里插入图片描述

  • Thomassen:最小的可形图,在34个顶点和52条边上。可形图不包含哈密顿路径,但在从图中移除任何单个顶点后,剩余的图总是包含哈密顿路径。包含哈密顿路径的图称为可追踪图。

在这里插入图片描述

  • Tutte:Tait的哈密尔顿图猜想指出,每一个3-连通的3-正则平面图都是哈密尔顿图。这张图是一个反例。它有46个顶点和69条边
    在这里插入图片描述

  • Uniquely3colorable:返回一个12顶点的无三角形图,其色数为3,唯一为3色

在这里插入图片描述

  • Walther:一个有25个顶点和31条边的恒等图。一个恒等图有一个单图自同构,平凡图

在这里插入图片描述

  • Zachary:20世纪70年代,美国一所大学的空手道俱乐部34名成员之间的友谊社交网络。
    在这里插入图片描述

手工输入建图的语法:

make_graph 也可以手动输入边来创建图。此时,函数的参数是一个定义边的向量,第一个边从第一个元素指向第二个元素,第二个边从第三个指向第四个元素,以此类推。对于数字向量,这些被解释为内部顶点id。对于字符向量,它们被解释为顶点名称。

从igraph 0.8.0开始,您还可以通过igraph的formula表示法在此处包含文字(请参见graph_from_literal())。在这种情况下,公式的第一项必须以“~”字符开头,就像R中的正则公式一样。参见以下示例

make_graph(
  ~ A - B - C - D - A, E - A:B:C:D,
  F - G - H - I - F, J - F:G:H:I,
  K - L - M - N - K, O - K:L:M:N,
  P - Q - R - S - P, T - P:Q:R:S,
  B - F, E - J, C - I, L - T, O - T, M - S,
  C - P, C - L, I - L, I - P
)

在这里插入图片描述

注意: 参数必须以~开头,:不再是向量中序列的用法,1:4不再表示1,2,3,4四个元素的向量,而是表示拥有{1,4}两个元素的集合。

3-8 make_kautz_graph,与德布鲁因图相似,返回有向正则图(d=2m)

Kautz图是表示字符串重叠的定标图(Labeled graph)

Kautz图是一个定标图(Labeled graph),顶点由长度为n+1的字符串标记,字符串位于m+1个字母的字母表之上,限制条件是字符串中的每两个连续字母必须不同。如果可以通过移除第一个字母并在其上附加一个字母将v的字符串转换为w的字符串,则存在从顶点v到另一个顶点w的有向边

在这里插入图片描述

3-9 栅格图:make_lattice

在这里插入图片描述

3-10 图的线图:make_line_graph

G无向图的线图L(G)定义如下。L(G)对于G中的每条边都有一个顶点,并且如果它们的对应边共享一个端点,则L(G)中的两个顶点通过一条边连接。G有向图的线图L(G)略有不同,如果第一个顶点的对应边的目标与第二个顶点的相应边的源相同,则L(G)。

注意:本函数的参数是图(graph类),不是顶点或边。

3-11 环图:make_ring

在这里插入图片描述

3-12 星形图:make_star

在这里插入图片描述

3-13 树图:make_tree

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/451711.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Android studio SDK Manager显示不全的问题解决

发现SDK Manager中只显示已下载的SDK版本&#xff0c;想下载其他版本下载不到&#xff0c;尝试翻墙也没用&#xff0c;修改host文件成功 在多个地点Ping服务器,网站测速 - 站长工具 输入dl.google.com&#xff0c;进行ping检测。 选择一个地址&#xff0c;比如180.163.150.1…

【深度学习笔记】5_12稠密连接网络(DenseNet)

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 5.12 稠密连接网络&#xff08;DenseNet&#xff09; ResNet中的跨层连接设计引申出了数个后续工作。本节我们介绍其中的一个&#xf…

Python学习:基础语法

版本查看 python --version编码 默认情况下&#xff0c;Python 3 源码文件以 UTF-8 编码&#xff0c;所有字符串都是 unicode 字符串。 特殊情况下&#xff0c;也可以为源码文件指定不同的编码&#xff1a; # -*- coding: cp-1252 -*-标识符 第一个字符必须是字母表中字母或…

Java学习笔记------常用API

Math类 常用方法&#xff1a; 1. publicb static int abs(int a) 获取参数绝对值 2. publicb static double ceil(double a) 向上取整 3. publicb static floor(double a) 向下取整 4.public static int round(float a) 四舍五入 5. publicb static int max…

Vue3全家桶 - VueRouter - 【2】重定向路由

重定向路由 在路由规则数组中&#xff0c;可采用 redirect 来重定向到另一个地址&#xff1a; 通常是将 / 重定向到 某个页面&#xff1b; 示例展示&#xff1a; router/index.js&#xff1a;import { createRouter, createWebHashHistory, createWebHistory } from vue-route…

云桥通SDWAN企业组网的15大应用场景

云桥通SD-WAN企业组网技术在企业网络中有多样化的应用场景&#xff0c;在技术不断迭代升级中&#xff0c;已经越来越匹配现在的互联网环境&#xff0c;其中在这15中常见的应用场景中&#xff0c;使用云桥通SDWAN企业组网可以很好的帮到企业&#xff1a; 分支机构连接优化&#…

蓝桥杯之【01背包模版】牛客例题展示

牛客链接 #include <bits/stdc.h> using namespace std; int n,V; const int N1010; int v[N],w[N]; int dp[N][N]; int main() {cin>>n>>V;for(int i1;i<n;i){cin>>v[i]>>w[i];}for(int i1;i<n;i){for(int j1;j<V;j){dp[i][j]dp[i-1][…

力扣刷题Days16(js)-67二进制求和

目录 1,题目 2&#xff0c;代码 2.1转换进制数 2.2模拟加法 3&#xff0c;学习与总结 Math.floor() 模拟加法思路回顾 重点复习巩固 模拟加法的思路和学习位运算&#xff1b; 今天没精力了&#xff0c;先休息 1,题目 给你两个二进制字符串 a 和 b &#xff0c;以二进制…

CSS 用 flex 布局绘制骰子

<!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><style>.box {height: 100px;width: 100px;border: 2px solid grey;border-radius: 10px;display: flex;justify-content: center; // 水平居中/* alig…

桥接模式以及在JDBC源码剖析

介绍&#xff1a; 1、桥接模式是指&#xff1a;将实现和抽象放在两个不同类层次中&#xff0c;使两个层次可以独立改变 2、是一种结构型设计模式 3、Bridge模式基于类的最小设计原则&#xff0c;通过使用封装、聚合以及继承等行为让不同的类承担不同的职责。 4、特点&#xff1…

【DAY11 软考中级备考笔记】数据结构 查找和排序

数据结构 查找和排序 3月12日 – 天气&#xff1a;晴 1. 顺序查找 顺序查找就是简单的从头一个一个的进行比较&#xff0c;注意它的平均查找长度 2. 折半查找 折半查找和二叉排序树一致&#xff1a; 优点&#xff1a;查找效率很高 缺点&#xff1a;要求必须是循序存储并且表中…

LoadRunner学习:RuntimeSetting、参数化、关联、(unfinished

LoadRunner RuntimeSetting 运行时设置 在Vuser中设置Run-time Settings RunLogic&#xff1a;运行逻辑&#xff0c;决定了脚本真正执行逻辑&#xff0c; Init和End部分代码只能执行一次。决定脚本真正执行逻辑的意思是&#xff0c;在Run中的代码和Number of Iteration决定了…

马斯克放出豪言,他旗下的xAI要把Grok开源了

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

WeiPHP5.0远程代码执行漏洞

文章目录 前言声明一、漏洞描述二、影响版本三、漏洞复现四、修复建议 前言 weiphp 是一个开源&#xff0c;高效&#xff0c;简洁的微信开发平台 声明 请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后…

Learn OpenGL 08 颜色+基础光照+材质+光照贴图

我们在现实生活中看到某一物体的颜色并不是这个物体真正拥有的颜色&#xff0c;而是它所反射的(Reflected)颜色。物体的颜色为物体从一个光源反射各个颜色分量的大小。 创建光照场景 首先需要创建一个光源&#xff0c;因为我们以及有一个立方体数据&#xff0c;我们只需要进行…

04.JavaScript中的封装和函数

函数 理解函数的封装特性&#xff0c;掌握函数的语法规则 声明和调用 函数可以把具有相同或相似逻辑的代码“包裹”起来&#xff0c;通过函数调用执行这些被“包裹”的代码逻辑&#xff0c;这么做的优势是有利于精简代码方便复用。 声明&#xff08;定义&#xff09; 声明&a…

白嫖的学习资源,程序员绝对相见恨晚!

麦瑟尔夫说&#xff1a;厌学是心灵的癌症。 不学而原地踏步则会让你变成大笨蛋&#xff0c;甚至脑子瓦特......&#xff08;好吧&#xff0c;可以喷了&#xff0c;其实我在危言耸听&#xff09; 但是&#xff01;排除鸡汤的洗脑&#xff0c;学习的重要性是不可否认的&#xff…

初学者必会的Python3文件操作

文件操作的步骤&#xff1a; 打开文件 -> 操作文件 -> 关闭文件 切记&#xff1a;最后要关闭文件。 打开文件 文件句柄 open(文件路径, 模式) 指定文件编码 文件句柄 open(文件路径,模式,encodingutf-8) 为了防止忘记关闭文件&#xff0c;可以使用上下文管理器来…

大模型的整体性

大模型在人工智能领域&#xff0c;体现出一种高度的整体性特征。大模型的整体性表现在其能够跨越多种数据模态&#xff0c;统一表示&#xff0c;应用广泛的知识&#xff0c;以统一的方式处理复杂信息&#xff0c;并在多种场景下保持一致和有效的性能。这种整体性可以分为外部和…