您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (12): 127-133.doi: 10.6040/j.issn.1671-9352.0.2022.324

•   • 上一篇    下一篇

定向图的燃烧连通度

夏龙苗(),魏宗田,丁丽萍   

  1. 西安建筑科技大学理学院, 陕西 西安 710055
  • 收稿日期:2022-05-30 出版日期:2023-12-20 发布日期:2023-12-19
  • 作者简介:夏龙苗(1996—)，女，硕士研究生，研究方向为图论、组合优化及其应用. E-mail: xlmiao0808@163.com
  • 基金资助:
    国家自然科学基金资助项目(61902304)

Burning connectivity of oriented graphs

Longmiao XIA(),Zongtian WEI,Liping DING   

  1. Department of Mathematics, Xi'an University of Architecture and Technology, Xi'an 710055, Shaanxi, China
  • Received:2022-05-30 Online:2023-12-20 Published:2023-12-19

RichHTML

1

PDF (PC)

225

摘要：

将图的燃烧数与连通度相结合, 提出定向图的燃烧连通度的概念。在给出一些特殊定向图(如树、圈、轮的定向图等)的燃烧连通度和循环定向图、给定直径的定向图的燃烧连通度上界的基础上, 设计一般定向图的燃烧连通度算法并分析其复杂性。

关键词: 定向图, 网络抗毁性, 燃烧连通度, 燃烧连通度算法

Abstract:

The burning number of the graph is combined with the connectivity to propose the concept of burning connectivity of the oriented graphs. Based on the burning connectivity of some special oriented graphs (such as oriented graphs of trees, circles, wheel, etc.), and upper bounds of burning connectivity of cyclic oriented graphs, oriented graphs with a given diameter. An algorithm for computing the burning connectivity of the general oriented graphs is designed, and the complexity of the algorithm is analyzed.

Key words: oriented graph, network invulnerability, burning connectivity, algorithm of burning connectivity

中图分类号: 

  • O157.5

图1

循环无向图C(8, ±{1, 2, 3})及其定向图$\vec{C}$ (8, ±{1, 2, 3})"

图2

算法流程图"

图3

定向图$\vec{G}$"

1 魏宗田, 刘勇, 杨威, 等. 网络抗毁性[M]. 西安: 西安交通大学出版社, 2015.
WEI Zongtian , LIU Yong , YANG Wei , et al. Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015.
2 BONATO A, JANSSEN J, ROSHANBIN E. Burning a graph as a model of social contagion[C]//International Workshop on Algorithms and Models for the Web-Graph, Cham, Switzerland: Springer, 2014: 13-22.
3 BONATO A , JANSSEN J , ROSHANBIN E . How to burn a graph[J]. Internet Mathematics, 2016, 12 (1): 85- 100.
4 JANSSEN R . The burning number of directed graphs: bounds and computational complexity[J]. Theory and Application of Graphs, 2020, 7 (1): 1- 14.
5 BONDY J A , MURTY U S R . Graph theory[M]. London: Springer, 2008.
6 徐俊明. 图论及其应用[M]. 4版 合肥: 中国科学技术大学出版社, 2018.
XU Junming . Theory and applications of graphs[M]. 4th ed Hefei: University of Science and Technology of China Press, 2018.
7 BOESCH F T , TINDELL A . Circulants and their connectivities[J]. Journal of Graph Theory, 2010, 8, 487- 499.
8 刘振宏, 蔡茂诚. 组合最优化算法和复杂性[M]. 北京: 清华大学出版社, 1988.
LIU Zhenhong , CAI Maocheng . Combinatorial optimization algorithms and complexity[M]. Beijing: Tsinghua University Press, 1988.
[1] 翁婷婷,魏宗田. 图的赋权邻域坚韧度[J]. 《山东大学学报(理学版)》, 2022, 57(6): 36-43.
[2] 崔晨,魏宗田. 图的广义p-邻域完整度[J]. 《山东大学学报(理学版)》, 2022, 57(10): 72-78.
[3] 师铭,魏宗田,刘勇,翁婷婷. 图的顶点赋权邻域粘连度[J]. 《山东大学学报(理学版)》, 2021, 56(5): 26-32.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 杨军. 金属基纳米材料表征和纳米结构调控[J]. 山东大学学报（理学版）, 2013, 48(1): 1 -22 .
[2] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
[3] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[4] 孙小婷1,靳岚2*. DOSY在寡糖混合物分析中的应用[J]. J4, 2013, 48(1): 43 -45 .
[5] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[6] 杨伦，徐正刚，王慧*，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[7] 冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
[8] 杨莹,江龙*,索新丽. 容度空间上保费泛函的Choquet积分表示及相关性质[J]. J4, 2013, 48(1): 78 -82 .
[9] 李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[10] 董伟伟. 一种具有独立子系统的决策单元DEA排序新方法[J]. J4, 2013, 48(1): 89 -92 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发