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

为什么图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,所以在图的双射关系中...,图G1中的e就应该对应图G2中的v5:e->v5 同理,在图G1中的6度节点a,也就应该对应图G2中的6度节点v1:a->v1 ······· 当然如果图的节点和度数规模很大的时候,这种对应关系就会变得很多...,所以就不好判断了 图同构的必要条件,也就是说两个图如果同构,会存在的特征 当图如果不满足下面的条件则这两个图肯定不同构,但是如果满足也不一定同构 图同构的必要条件举例 在图G和图G’中,图的节点数都相同...和1个2度节点© 所以图G和图G’不是同构的图 发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/125190.html原文链接:https://javaforall.cn

2.3K10

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

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

2K51
  • 图神经网络性能提升方法综述

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

    75220

    【不是画】Web应用的UI设计图不是画?

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

    1.2K50

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

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

    1.7K40

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

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

    2.1K00

    快速获取子图根节点的属性

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

    2.4K10

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

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

    27440

    「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.6K21

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

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

    1.5K20

    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.2K30

    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函数对字符串执行相同的操作。

    90150

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

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

    1.8K20

    使用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()函数用于创建复杂的子图布局。

    16510

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

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

    20200

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

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

    58220

    通过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
    领券