首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么图G2不是图G1的子图同构

图G2不是图G1的子图同构的原因是,子图同构是指一个图可以通过删除或重排节点和边的方式,变成另一个图。而G2不是G1的子图同构,意味着无法通过删除或重排G2的节点和边,使其变成G1。

可能的原因有以下几种:

  1. 节点数量不同:G2的节点数量可能多于或少于G1,导致无法通过删除或添加节点来实现子图同构。
  2. 边的连接方式不同:G2的节点之间的边的连接方式可能与G1不同,即使节点数量相同,也无法通过重排边的连接方式来实现子图同构。
  3. 节点属性不同:G2的节点可能具有不同的属性或标签,而G1没有相应的节点属性或标签。这也会导致无法通过删除或重排节点来实现子图同构。
  4. 边的属性不同:G2的边可能具有不同的属性或标签,而G1没有相应的边属性或标签。这同样会导致无法通过删除或重排边来实现子图同构。

综上所述,以上是图G2不是图G1的子图同构的可能原因。请注意,这只是一种可能的解释,具体原因还需要根据具体的图结构和属性来分析。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

同构

同构 Abstract 同构 为什么要研究同构 满足什么条件才是同构 同构图案例 任意两个图形,如何判定同构 图同构必要条件,也就是说两个如果同构,会存在特征 图同构必要条件举例...,2度节点也肯定对应2度节点 也可以对节点邻接节点进行判断,一个节点邻接点是2度和3度节点,那么在另一个图中也应该是一样G1中只有一个一度节点e,G2中也只有一个一度节点v5,所以在双射关系中...,G1e就应该对应G2v5:e->v5 同理,在G16度节点a,也就应该对应G26度节点v1:a->v1 ······· 当然如果节点和度数规模很大时候,这种对应关系就会变得很多...,所以就不好判断了 图同构必要条件,也就是说两个如果同构,会存在特征 当如果不满足下面的条件则这两个肯定不同构,但是如果满足也不一定同构 图同构必要条件举例 在G和G’中,节点数都相同...和1个2度节点© 所以G和G’不是同构 发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/125190.html原文链接:https://javaforall.cn

2.1K10

【GNN】WL-test:GNN 性能上界

「Weisfeiler-Lehman 图同构测试是什么」? 「为什么提出 GIN 要与 Weisfeiler-Lehman 图同构测试进行比较」? 接下来,我们带着问题来阅读本篇文章。...简单来说,如果 G1G2 顶点和边数量相同,且边连接性相同,则可以称这两个图为同构。也可以认为,G1 点是由 G2点映射得到。...简单介绍下为什么要计算图同构:我们在分析社会网络、蛋白质、基因网络等通常会考虑彼此间相似度问题,比如说,具有相似结构分子可能具备相似的功能特性,因此度量相似度是学习一个核心问题。...「引理 1」:对任意两个非同构图 G1G2,如果存在一个神经网络 将 G1G2 映射到不同 Embedding 向量中,那么通过 WL-test 也可以确定 G1G2 是非同构图...,所以会一直保持一种迭代状态: ,GNN READOUT 函数对顺序不敏感,所以最终会得到 G1G2图同构,与条件出现了矛盾。

1.9K51

神经网络性能提升方法综述

2.2 图同构基础知识 图同构性是指两个在节点和边结构上完全相同,但节点和边标签可以不同。在神经网络中,图同构性是一个重要概念,因为它可以帮助我们判断两个是否相同,从而避免重复计算。...GNNs可以通过学习特征来解决图同构问题。 Weisfeiler-Lehman测试(WL测试)是一种解决图同构问题有效算法,也称为颜色细化算法。1展示了WL测试聚合和更新过程。...在第一次迭代后,G1G2具有相同颜色分布,以确定它们是否同构,并进行下一次迭代。(c)再次执行节点邻居聚合和颜色标签重新分配步骤,并获得G1G2不同颜色分布,此时可以确定它们不同构。...2展示了WL测试无法区分非同构图。k-WL也是一种用于解决图同构问题算法。... 4:GNN表达能力示意图 目前GNN表达能力研究中几种主流观点分别将表达能力描述为近似能力、分离能力和计数能力。 5为不同表达能力表示下 GNN 模型输入和输出。

52020

不是画】Web应用UI设计不是画?

如标题,UI设计不是画?什么意思?意思是说UI设计,是经过美化需求点视觉呈现。首先它是有“功能”,然后在满足功能同时满足“美观”要求。 满足美观要求,这不还是一张画嘛?...依然不是,Web应用虽然在视觉呈现方向也要求美观得体大方,但它与印刷品最大区别在于,它是可以被操作,它是有交互,是有功能。这就注定满足功能方向要求是第一性。...而一个web产品在最初立项时候,最开始时候一定是先列出它所有功能,及面向用户。然后产品经理写出需求文档,然后UI设计师根据需求文档及用户画像,设计产品粗原型、细原型、最终精细原型。...一般是在开产品需求讲解会议上先说,然后发邮件给你们; 二、就是UI设计,这东西是设计师给你。 当你看到这二样东西时候,这个web应用功能和视觉设计都已经基本确定了。...这个时候UI设计是否好看,你个人主观看它是否美观,这都与你无关,也不应该是web前端关注点。 所以我在标题中说,web前端开发所关注,应该是这些UI设计图上,所体现出来功能点。

1.1K50

北大邹磊:数据库中匹配算法

分享嘉宾:邹磊 北京大学 教授 编辑整理:xiaomei 出品平台:DataFunTalk 导读:本次讲座从数据库中核心查询算子——匹配入题,介绍了数据库基本概念、匹配算法,以及在数据库环境下匹配查询优化等内容...E-R是概念模型,更像类(class),定义是类之间逻辑关系,不是数据实例(Instance)之间关联;而数据库模型是物理实现数据模型,数据库中每个点和边表示实例(也称为实体)属性与实例之间关联...例如,语义网特点是比较容易支持后期推理,而且其标准化做得比较好。而目前数据库也正在做标准化事情。评判两个模型优劣也不应该仅从技术角度做评判,因此认为还不是评判时候。...RDF数据模型 RDF特点是主、谓、宾表示方式,无论是表示实体、属性还是实体与实体关系,都用主谓宾表示。 那为什么形式呢?...因为主语和宾语就是两个点,它们之间关系就是一条边,因此是RDF Graph;不是把RDF数据看成Graph,而是它本身就是Graph,只是它不仅可以表示成三列表形式,也可以表示成Graph形式

1.5K40

北大邹磊:数据库中匹配算法

以及在数据库环境下匹配查询优化等内容。...E-R是概念模型,更像类(class),定义是类之间逻辑关系,不是数据实例(Instance)之间关联;而数据库模型是物理实现数据模型,数据库中每个点和边表示实例(也称为实体)属性与实例之间关联...例如,语义网特点是比较容易支持后期推理,而且其标准化做得比较好。而目前数据库也正在做标准化事情。评判两个模型优劣也不应该仅从技术角度做评判,因此认为还不是评判时候。...RDF数据模型 RDF特点是主、谓、宾表示方式,无论是表示实体、属性还是实体与实体关系,都用主谓宾表示。 那为什么形式呢?...因为主语和宾语就是两个点,它们之间关系就是一条边,因此是RDF Graph;不是把RDF数据看成Graph,而是它本身就是Graph,只是它不仅可以表示成三列表形式,也可以表示成Graph形式

1.9K00

快速获取根节点属性

@TOC[1] Here's the table of contents: •一、问题背景•二、构建样例多子数据•三、实现根节点属性查找•四、将查找GQL封装为一个函数•五、总结 快速获取根节点属性...查找匹配是一个非常复杂问题,主要有确定模式匹配和不确定模式匹配【例如:通过模式相似性进行查找】。...本文主要讲述一个确定模式查询方式,对于存在很多子数据模型也可以使用本文截图中社区成员提问方式去建模数据可以达到节省资源空间目的;不过具体建模场景需要结合业务场景才可行。...已知查找问题可以使用APOC中过程来实现,apoc.path相关输入输出查询[2];指定节点之后获取节点所属,然后从子图中提取出ROOT节点属性。...其中指定a节点为ROOT节点即根节点。

2.4K10

ICML2023 | 分子关系学习条件信息瓶颈

其主要思想是,在给定一对情况下,基于条件信息瓶颈原理,从一个图中找到一个,该包含关于当前任务最小充分信息,并与配对相互关联。...模型主要目标是,给定一对图形G1G2,检测G1,该在决定G1G2之间交互行为方面至关重要。...然后,通过一个交互映射I对G1G2之间节点级交互进行建模。...因此,˜E1是捕捉G1中节点与G2中节点之间交互节点嵌入矩阵,˜E2也是类似的。然后,通过将E1和˜E1拼接在一起来生成G1最终节点嵌入矩阵H1,即H1 = (E1 || ˜E1)。...G2最终节点嵌入矩阵H2以类似的方式生成。最后,使用Set2Set作为读出函数,分别为每个G1G2生成级别的嵌入zG1和zG2。

22740

「NeurIPS 2020」基于局部图元学习

❝「NeurIPS 2020」 接收论文《Graph Meta Learning via Local Subgraphs》,「G-META 是第一个使用局部来进行元学习模型。」...此文介绍了「G-META,一种新元学习方法:」 G-META 使用局部传递特定于信息,并通过元梯度使模型更快地学习基本知识。...G-META 在理论上是合理,因为「特定预测证据可以在目标节点或边周围局部图中找到。」 现有方法是专门为特定图元学习问题和特定任务设计专门技术。...(1)首先构造一批 个元训练任务,并为元任务中节点动态提取局部。 对于每个任务 ,(2)来自支撑集中是最小批处理,并且被馈送到由 参数化 GNN 中。...(7) 馈送到更新后 GNN 中以(8)生成查询质心嵌入。 (9)利用支撑原型和查询嵌入,计算任务 查询损失 。 对于 更新步骤重复步骤(2-9)。

1.5K21

ICLR22上47页“神仙论文” | 聚合神经网络

作者认为一个是可以看做由若干拼接出来,因此最好方法是设计一个同时能区分子,又能融合这些网络。...ESAN设计包括两个基本结构,第一个是独立处理每个子孪生网络,第二个是一个信息共享模块,用来做信息共享和聚合。其中,引出一个新问题,怎么去初始化这些被选择?...简单来说,就是选择一些可以用来表示选择边动作来模拟这个过程。这里作者记这个过程为 。m表示个数,n表示节点个数。这套动作可以映射成 ,将分割开以后,自然就要考虑如何刻画这些。...还有一个比较了当模型达到最优结果时,模型用了多少参数量: 比较有意思是PTC和IMDB两个数据集反而会用更少参数,因此,ESAN这种结构实际上并不是单纯引入参数量,把结果硬生生拉上去。...因此,在后续工作中,作者提出了几点可以继续深入方向:1)更好选择策略,用来提高分类准确率;2)更高阶图表征方法,使得结构信息能更完善地被捕捉;3)对网络更理论分析,尤其是不同选择方法和聚合函数分析

1.3K20

神奇 Animal Matting 算法,毛发抠不是事。

一、前言 抠是个体力活。 抠最难,就是处理毛发。 想没想过,有一天,算法直接帮你自动抠?细致到毛发那种! ? 毛发分割都不是问题!...二、Animal Matting 抠问题核心是精确地将图像或视频中前景估计出来,对图像编辑,影片剪辑等都有很深意义。...最新发表论文 End-to-end Animal Image Matting ,只需要一张,无需任何先验知识,即可实现端到端,效果非常惊艳。...论文提出了一个名为 GFM 模型,该模型可同时生成全局语义分割和局部 alpha mask。...最后,通过协同合作抠(CM),将上述三个不同表征域结果,进行合并,获得最终 alpha 预测。

1.6K20

Excel公式技巧:颠倒单元格区域数组

如下图1所示,我想使用公式: =SUMPRODUCT(A1:G1,G2:A2) 但是,Excel总是将其修改为从左到右单元格区域: =SUMPRODUCT(A1:G1,A2:G2) 1 如何实现自己目的呢...可以使用公式: =SUMPRODUCT(A1:G1,N(OFFSET(A2:G2,0,7-COLUMN(A2:G2),1,1))) 然而,公式使用了硬编码7,如果区域大小变了,这个数字也要手动更改。...可以将上面的公式修改为: =SUMPRODUCT(A1:G1,N(OFFSET(A2:G2,0,COLUMNS(A2:G2)-COLUMN(A2:G2),1,1))) 为什么OFFSET函数前还要加上N...OFFSET函数使用第1个、第2个或第3个参数为数组调用,返回一组单元格区域引用,当用于算术操作数或大多数函数参数时,Excel无法处理。...幸运是,N函数是一个例外,它有效地将区域引用数组转换为数字数组(注意,它将不是数字条目转换为数字零)。T函数对字符串执行相同操作。

85850

3阶有向完全所有非同构(不同钩子图个数)

大家好,又见面了,我是你们朋友全栈君。 图同构问题本质上就是一种匹配,VF2算法加了很多feasibility rules,保证了算法高效性。...这里只是实现最基本判断图同构算法: 参考文献有(其实google一把就能出来这些): http://stackoverflow.com/questions/8176298/vf2-algorithm-steps-with-example...下面给出我算法设计(这里考虑边和点除了ID之外,还有label): 边和结构: struct EDGE { int id2; int label; EDGE(int _id2, int _label...core_1 and core_2, //whose dimensions correspond to the number of nodes in G1 and G2 struct MATCH {...=dbG->vLabel[dbG_vID]) //如果两个点label不同,则【一定不】满足feasibility rules { return false; } //其次,判断是不是每次

1.1K30

使用subplot_mosaic创建复杂布局

在本文中,我将介绍matplotlib一个非常有价值用于管理函数——subplot_mosaic()。如果你想处理多个,那么subplot_mosaic()将成为最佳解决方案。...data data_size = 100 random_data = np.random.randn(data_size) 使用subplot_mosaic()定义布局 下面的代码片段中,布局指定了四个...A占据了整个顶部行,而其余(B、C和D)排列在底部行。 layout = """AAA BCD""" 利用subplot_mosaic()来定义基于指定布局。...更新后布局如下: 我们可以这样改 完整代码 那么如果想包含一个空呢? 可以使用"."...占位符,如下所示: 看看结果 可以看到Matplotlib中subplot_mosaic()函数用于创建复杂布局。

12810

通过R让你复杂网络更具艺术感

“嗯嗯”,我一边应付她,一边在脑子里飞快回忆社交关系特点,“在反映大量人群或事物之间关系时,社交网络可以清晰展示’群体’内含和外延。例如,群体规模、核心、与其他群体交叠情况。...plot(g2,layout=layout.fruchterman.reingold,vertex.label=NA) #显示网络 ?...下图是walktrap算法,step=10情况下得出结果。原本2个社区网络被分为66类。把两个大社区分成了一类,把两大社区重叠部分分成了很多类。显然这不是我们所希望看到分类结果。...五 透明化处理后网络 五、完成最终效果: 1.美化图形(以边线分类) 另一种呈现方式,是点颜色不变,将不同社区连线颜色分类。...E(g1)$color=V(g1)[name=ends(g1,E(g1))[,2]]$color #为edge颜色赋值V(g1)[grep("1", V(g1)$name)]$color=rgb(

2.2K40

生代码,生成到底是不是烂代码!

前言 在知乎上一直有一个热度很高的话题,你最见过最烂代码长啥样?最近突然又爆火起来,主要是针对,“生代码”这一新兴事务。...对于AI情商一直是备受推崇,内在逻辑清晰语言组织能力超强,为什么在“生代码”上被推为了最烂代码。由于工作关系,接触到了一款“生代码”。将试用情况以及实际代码贴出来。...在表现力和代码处理上也还是比较协调。在生代码应用中,这一部分应该是使用最多。其灵活性也非常不错。 ​...(3)图文混排 图文混排,对布局考验是非常大,对于代码整体逻辑设计也是复合度最高,这部分实例是不错用例。 ​...(2)统计 统计或者叫大屏,是图形设计中最常见一种类型。但直接生成代码类型还不多。而起数据结构也比较复杂一些。 时间关系,根据实例简单整理了一些简单示例,后续会逐渐补充,并将视频放出。

11700

用R语言作社群关系分析

在反映大量人群或事物之间关系时,社交网络可以清晰展示’群体’内含和外延。例如,群体规模、核心、与其他群体交叠情况。...<-na.omit(g) 开始绘制简单社交关系: 1.简单社交网络 library(igraph) #加载igraph包 x<-par(bg=”black”) #设置背景颜色为黑色 g2 = graph.data.frame...(d = g1,directed = F); #数据格式转换 V(g2) #查看顶点 E(g2) #查看边 #使用layout.fruchterman.reingold方式呈现图形 plot(g2,layout...下图是walktrap算法,step=10情况下得出结果。原本2个社区网络被分为66类。把两个大社区分成了一类,把两大社区重叠部分分成了很多类。显然这不是我们所希望看到分类结果。...利用R语言igraph作社群挖掘 ?

2.4K80

为什么我没写过「」相关算法?

那么,为什么有这两种存储方式呢?肯定是因为他们各有优劣。 对于邻接表,好处是占用空间少。 你看邻接矩阵里面空着那么多位置,肯定需要更多存储空间。 但是,邻接表无法快速判断两个节点是否相邻。...那你可能会问,我们这个模型仅仅是「有向无权」,不是还有什么加权,无向,等等…… 其实,这些更复杂模型都是基于这个最简单衍生出来。 有向加权怎么实现?...也很简单,所谓「无向」,是不是等同于「双向」? 如果连接无向图中节点x和y,把matrix[x][y]和matrix[y][x]都变成true不就行了;邻接表也是类似的操作。...graph.neighbors(s)) traverse(neighbor); // 离开节点 s visited[s] = false; } 好吧,看到这个框架,你是不是又想到了...为什么回溯算法框架会用后者?因为回溯算法关注不是节点,而是树枝,不信你看 回溯算法核心套路 里面的,它可以忽略根节点。

55820
领券