论文部分内容阅读
在像Facebook或者Twitter这样的社会复杂网络中常常想要实现信息或者病毒等的传播,而由于现实的需要,通常想要尽可能快的实现信息或者病毒的全覆盖,那么要将信息全覆盖的时间尽可能的最小化应该如何实现呢?在解决这一类问题的背景下,2014年Bonato等人提出图的燃烧这样一个新的概念.用图的燃烧过程来刻画信息或病毒的传播过程,用燃烧数来刻画传播速度,燃烧数越小则说明传播速度越快.2014年Bonato等人提出这个概念的时候解决了路和单圈图的燃烧数的求解,并且对于任意一个连通图给出猜想2.2.这个概念提出来之后,国内外纷纷有学者开始研究,但是一直没有得到比较好的结果,在2017年的时候Bessy等人证明了对于一些结构十分简单的图类,想要求解具体的燃烧数也是NP完全的.所以说如果可以求出一些特殊图类燃烧数的准确值就是十分有意义的.本文利用燃烧的性质和θ-图的结构特点,算出任意一个θ-图的准确的燃烧数.