一些可交换图的刻画.pdf
《一些可交换图的刻画.pdf》由会员分享,可在线阅读,更多相关《一些可交换图的刻画.pdf(6页珍藏版)》请在咨信网上搜索。
1、Operations Research and Fuzziology 运筹与模糊学运筹与模糊学,2024,14(1),1015-1020 Published Online February 2024 in Hans.https:/www.hanspub.org/journal/orf https:/doi.org/10.12677/orf.2024.141094 文章引用文章引用:申悦,苏柯.一些可交换图的刻画J.运筹与模糊学,2024,14(1):1015-1020.DOI:10.12677/orf.2024.141094 一些可交换图的刻画一些可交换图的刻画 申申 悦悦,苏苏 柯柯 长安大
2、学理学院,陕西 西安 收稿日期:2023年12月15日;录用日期:2024年1月5日;发布日期:2024年2月29日 摘摘 要要 两个图称为可交换的,如果存在一种顶点标号使得它们在该顶点标号下的邻接矩阵可交换两个图称为可交换的,如果存在一种顶点标号使得它们在该顶点标号下的邻接矩阵可交换。本。本文文通过利通过利用已知可交换图的性质及矩阵克罗内克积积运算、图联运算的性质,从已知可交换图出发构造出新的可用已知可交换图的性质及矩阵克罗内克积积运算、图联运算的性质,从已知可交换图出发构造出新的可交换图,对研究可交换图问题有重要促进作用。交换图,对研究可交换图问题有重要促进作用。关键词关键词 图,邻接矩阵
3、,克罗内克积,可交换图,邻接矩阵,克罗内克积,可交换 Characterization of Some Commutative Graphs Yue Shen,Ke Su School of Sciences,Changan University,Xian Shaanxi Received:Dec.15th,2023;accepted:Jan.5th,2024;published:Feb.29th,2024 Abstract Two graphs are called commuting if there exists a labelling of the vertices such that
4、 their adjacen-cy matrix commute.In this paper,new commuting graphs are constructed from the known ones by using the properties of the commuting matrices,the Kronecker product operation of matrix and the joint operation of a graph,which promotes the study of commuting graphs.Keywords Graph,Adjacency
5、 Matrix,Kronecker Product,Commutativity 申悦,苏柯 DOI:10.12677/orf.2024.141094 1016 运筹与模糊学 Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 设n阶无向简单图G的顶点集为()1,n
6、V Gvv=,边集为()E G。其邻接矩阵定义为()ijn nAa=,其中1,0,ijijvva=若 和 相邻其它。顶点的邻点个数记为顶点的度,若G每个顶点的度均为k,则称G是k-正 则图。设1G,2G是两个图,并设()111,GV E=,()222,GV E=,则1G与2G的并是指图()1212,VV EE,记为12GG。特别的,若12VV为空集,则12GG称为1G与2G的不交并,不交并有时也称为和,记为12GG+。两个无公共顶点的图1G,2G的不交并12GG+再添加边集()()()12,x y xV GyV G后得到的图称为1G与2G的联,记为12GG。图G的分裂图()SG是通过在G的每个
7、顶点v上添加一个新的顶点 v得到的,v与G中v的每一个邻点相连。连通图G的阴影图()2DG是通过G的两个复制G和G得到的,G中的顶点 v需与其G中对应点v的邻点连接。图G的 CDC 图是G与2K的直积,即()2CDC GGK=1。矩阵的可交换性问题是 Cayley 首先在文献2中讨论的一个经典问题。我们研究图的可交换性即为讨论它们的邻接矩阵的可交换。两个图称为可交换的,如果存在一种顶点标号使得它们的邻接矩阵可交换。然而,关于图邻接矩阵的可交换性问题研究结果并不多。对于距离正则图G来说,其邻接矩阵()A G与其距离图iG的邻接矩阵()iA G可交换3;Beezer 4刻画了所有与路nP可交换的图
8、的性质;Akbari 5找到了所有使得完全二部图,n nK可以分解成可交换的完美匹配或哈密顿圈的整数。2.预备知识预备知识 定义定义 2.1 6矩阵的克罗内克积定义如下:设A是一个mn的矩阵,而B是一个pq的矩阵,则矩阵,A B的克罗内克积AB则是如下的一个mpnq的分块矩阵:1111nmmna Ba BABa BaB=。定理定理 2.1 7设A,C均为m阶方阵;B,D均为n阶方阵。若ACCA=,BDDB=则()()()()ABCDCDAB=。定理定理 2.2 8正则图的邻接矩阵与J可交换。3.从可交换图出发构造新的可交换图从可交换图出发构造新的可交换图 定理定理 3.1 图1G与图2G可交换
9、,即()()()()1221A GA GA GA G=。则有:1)图1G的分裂图与图2G的分裂图可交换;2)图1G的阴影图与图2G的阴影图可交换;3)图1G的 CDC 图与图2G的 CDC 图可交换。证明:证明:1)由分裂图的定义知,图1G的分裂图与图2G的分裂图的邻接矩阵分别为()()()()()()1111111010A GA GA SGA GA G=Open AccessOpen Access申悦,苏柯 DOI:10.12677/orf.2024.141094 1017 运筹与模糊学 ()()()()()()2222211010A GA GA SGA GA G=因为,图1G与图2G可交换
10、,即()()()()1221A GA GA GA G=,所以由定理 2.1 易得()()()()()()()()1221A SGA SGA SGA SG=。2)由阴影图的定义知,图1G的阴影图与图2G的阴影图的邻接矩阵分别为()()()()()()()11211111 11 1A GA GA DGA GA GA G=()()()()()()()22222221 11 1A GA GA DGA GA GA G=因为图1G与图2G可交换,即()()()()1221A GA GA GA G=,所以由定理 2.1 易得()()()()()()()()21222221A DGA DGA DGA DG=。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一些 可交换 刻画
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。