Graph Protection and Domination

图保护和统治

• 批准号: RGPIN-2015-05442
• 负责人: Mynhardt, Christina
• 金额: $ 1.02万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675406
• 关键词: Graph; Protection; Domination

Graph protection and domination involves the placement of guards (or surveillance or broadcast equipment, emergency services, military units, etc.) at strategic positions in a network. Interestingly, it has its historical roots in the time of the Roman Empire when Emperor Constantine devised a military strategy, called a defense in depth strategy. He deployed mobile field armies, units of forces powerful enough to secure the regions of the Roman Empire, to stop the intruding enemy, or to suppress insurrection. A field army was considered capable of deploying to an adjacent region only if it moved from a region where there was at least one other army to help launch it.***Positions in a network are modelled by nodes of a graph, two nodes being joined by a line if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems, called attacks, in situ or at nodes adjacent to their positions. Depending on the model the guards either remain stationary or move across lines to repel an attack; every vertex of the graph must have access to a guard in this way. There is a conflict between cost and efficiency, both of which are proportional to the number of guards and the type of guard movements, and it is a challenge to balance the opposing forces.***My research focuses on the abstract mathematical theory of these protection strategies. The theory involves aspects such as the smallest number of guards required for a successful defense, algorithms to find these numbers, the most efficient strategies, types of networks that allow efficient defense strategies, the stability and vulnerability of specific types of networks, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, therefore relating the protection parameters to other, more easily determined parameters, such as the number of nodes or lines, the diameter or radius of the graph, forms part of my work. This is important in order to place them within the context of well-studied concepts.***Although the protection models described above arose from Constantine's military strategy, as models of modern military strategy they are oversimplified. Nevertheless, models are tools for reasoning about problems and provide ways to formalize concepts such as the effect of different defense strategies on the cost and quality of the defense, and of the destruction of links in a network on its efficiency. The ideas developed here are of interest as mathematical concepts and problems, and also have other potential applications, such as to voting strategies and the spread of diseases.***My goal is to develop a comprehensive theory of these protection strategies, and to encourage other researchers to participate in the process. The training and mentoring of undergraduate and graduate research students forms an integral part of my proposal.**

图形保护和控制包括设置警卫(或监视或广播设备、紧急服务、军事单位等)。在网络中的战略位置。有趣的是，它的历史起源于罗马帝国时期，当时君士坦丁皇帝设计了一种军事战略，称为纵深防御战略。他部署了机动野战军，这是一种强大的部队，足以保卫罗马帝国的各个地区，阻止入侵的敌人，或镇压叛乱。野战军只有从至少有一支其他军队帮助发射的地区移动时，才被认为有能力部署到邻近地区。*网络中的位置由图的节点建模，如果网络中的相应位置在某种适当意义上彼此可达，则两个节点由一条线连接。警卫在原地或在他们位置附近的节点处理被称为攻击的问题。根据模型的不同，守卫要么保持不动，要么跨线移动以击退攻击；图中的每个顶点都必须以这种方式访问守卫。成本和效率之间存在冲突，两者都与警卫的数量和警卫的移动类型成正比，平衡对立的力量是一个挑战。*我的研究集中在这些保护策略的抽象数学理论上。该理论涉及多个方面，如成功防御所需的最小守卫数量、找到这些数量的算法、最有效的策略、允许有效防御策略的网络类型、特定类型网络的稳定性和脆弱性等。通常很难确定特定类型的防御所需的最小保护数量，因此将保护参数与其他更容易确定的参数相关联，如节点或线的数量、图形的直径或半径，构成了我的工作的一部分。这一点很重要，以便将它们置于经过充分研究的概念的背景下。*尽管上述保护模式源于君士坦丁的军事战略，但作为现代军事战略的模式，它们过于简单化了。然而，模型是对问题进行推理的工具，并提供了将各种概念形式化的方法，例如不同防御策略对防御成本和质量的影响，以及网络中链路的破坏对其效率的影响。这里提出的想法是令人感兴趣的数学概念和问题，也有其他潜在的应用，如投票策略和疾病传播。*我的目标是开发这些保护策略的全面理论，并鼓励其他研究人员参与这一过程。对本科生和研究生的培训和指导是我建议的一个组成部分。