数学代写|组合优化代写Combinatorial optimization代考|Polyhedra Associated with Open Locating-Dominating

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

数学代写|组合优化代写Combinatorial optimization代考|Locating Total-Dominating Sets in Graphs

For a graph $G$ that models a facility, detection devices can be placed at its nodes to locate an intruder (like a fire, a thief or a saboteur). Depending on the features of the detection devices (to detect an intruder only if it is present at the node where the detector is installed and/or also at any of its neighbors), different dominating sets can be used to determine the optimal distribution of the detection devices in $G$. In the following, we study three problems arising in this context which all have been actively studied during the last decade, see e.g. the bibliography maintained by Lobstein [16].

Let $G=(V, E)$ be a graph. The open neighborhood of a node $i$ is the set $N(i)$ of all nodes of $G$ adjacent to $i$, and $N[i]={i} \cup N(i)$ is the closed neighborhood of $i$. A subset $C \subseteq V$ is dominating (resp. total-dominating) if $N[i] \cap C$ (resp. $N(i) \cap C)$ are non-empty sets for all $i \in V$.

A subset $C \subseteq V$ is:

• an identifying code (ID) if it is a dominating set and $N[i] \cap C \neq N[j] \cap C$, for distinct $i, j \in V[15]$;
• an open locating-dominating set (OLD) if it is a total-dominating set and $N(i) \cap C \neq N(j) \cap C$, for distinct $i, j \in V[19]$;
• a locating total-dominating set (LTD) if it is a total-dominating set and $N(i) \cap$ $C \neq N(j) \cap C$, for distinct $i, j \in V-C[13]$.

Note that a graph $G$ admits an ID-code (or is identifiable) only if there are no true twins in $G$, i.e., there is no pair of distinct nodes $i, j \in V$ such that $N[i]=N[j]$, see [15]. Analogously, a graph $G$ without isolated nodes admits an $O L D$-set if there are no false twins in $G$, i.e., there is no pair of distinct nodes $i, j \in V$ such that $N(i)=N(j)$, see $[19]$.

Given a graph $G$, for $X \in{I D, O L D, L T D}$, the $X$-problem on $G$ is the problem of finding an $X$-set of minimum size of $G$. The size of such a set is called the $X$-number of $G$ and is denoted by $\gamma_{X}(G)$. From the definitions, the following relations hold for any graph $G$ (admitting an $X$-set):
$$\gamma_{L T D}(G) \leq \gamma_{O L D}(G)$$
whereas $\gamma_{I D}(G)$ and $\gamma_{O L D}(G)$ are not comparable in general.
Determining $\gamma_{I D}(G)$ is in general NP-hard [9] and even remains hard for several graph classes where other in general hard problems are easy to solve, including bipartite graphs $[9]$, split graphs and interval graphs [10].

Also determining $\gamma_{O L D}(G)$ is in general NP-hard [19] and remains NP-hard for perfect elimination bipartite graphs and APX-complete for chordal graphs with maximum degree $4[18]$. Concerning the LTD-problem we observe that it is as hard as the $O L D$-problem by just using the same arguments as in [19].
Typical lines of attack are to determine minimum $I D$-codes of special graphs or to provide bounds for their size. Closed formulas for the exact value of $\gamma_{I D}(G)$ have been found so far only for restricted graph families (e.g. for paths and cycles by [8], for stars by [12], and for complete multipartite graphs, some suns and split graphs by [2-5]). Closed formulas for the exact value of $\gamma_{O L D}(G)$ have been found so far only for cliques and paths [19], some algorithmic aspects are discussed in [18]. Bounds for the LTD-number of trees are given in $[13,14]$, whereas the LTD-number in special families of graphs, including cubic graphs and grid graphs, is investigated in [14].

数学代写|组合优化代写Combinatorial optimization代考|Polyhedra Associated to OLD- and LT D-Sets

In order to apply the polyhedral approach to the $O L D$ – and the $L T D$-problem, we first give according reformulations as set covering problem.
Theorem 1. Let $G=(V, E)$ be a graph.
(a) Let $G$ have neither isolated nodes nor false twins. $C \subseteq V$ is an OLD-set if and only if $C$ has a non-empty intersection with
$O L D_{1} N(i)$ for all $i \in V$,
$O L D_{2} N(i) \triangle N(j)$ for all distinct $i, j \in V$ with $\operatorname{dist}(i, j)=1$ or $\operatorname{dist}(i, j)=2$;
(b) $C \subseteq V$ is an LTD-set if and only if $C$ has a non-empty intersection with $L T D_{1} N(i)$ for all $i \in V$,
$L T D_{2} N(i) \triangle N(j)$ for all distinct $i, j \in V$ with $\operatorname{dist}(i, j)=1$, $L T D_{3} N[i] \triangle N[j]$ for all distinct $i, j \in V$ with $\operatorname{dist}(i, j)=2$.
The matrices $M_{O L D}(G)$ and $M_{L T D}(G)$ encoding row-wise the open neighborhoods and their respective symmetric differences read, therefore, as
$$M_{O L D}(G)=\left(\begin{array}{c} N(G) \ \triangle_{1}(G) \ \triangle_{2}(G) \end{array}\right) \quad M_{L T D}(G)=\left(\begin{array}{c} N(G) \ \triangle_{1}(G) \ \triangle_{2}[G] \end{array}\right)$$
where every row in $N(G)$ is the characteristic vector of an open neighborhood of a node in $G$ and $\triangle_{k}(G)$ (resp. $\left.\Delta_{k}[G]\right)$ is composed of the characteristic vectors of the symmetric difference of open (resp. closed) neighborhoods of nodes at distance $k$ in $G$. We define by
$$P_{X}(G)=Q^{}\left(M_{X}(G)\right)=\operatorname{conv}\left{\mathbf{x} \in \mathbb{Z}{+}^{|V|}: M{X}(G) \mathbf{x} \geq 1\right}$$
the $X$-polyhedron for $X \in{O L D, L T D}$. We first address the dimension of the two polyhedra. It is known from Balas and $\mathrm{Ng}[7]$ that a set covering polyhedron $Q^{}(M)$ is full-dimensional if and only if the matrix $M$ has at least two ones per row.

From the submatrix $N(G)$ encoding the open neighborhoods, we see that
$$V_{N}(G)={k \in V:{k}=N(i), i \in V}$$
are the cases that result in a row with only one 1-entry. From the submatrix $\triangle_{1}(G)$, every row has at least two 1-entries (namely $i$ and $j$ for $N(i) \triangle N(j)$ ). From the submatrix $\Delta_{2}(G)$, we see that
$$V_{2}(G)={k \in V(G):{k}=N(i) \Delta N(j), i, j \in V}$$
are the cases that result in a row with only one 1-entry, whereas every row from the submatrix $\Delta_{2}[G]$ has at least two 1-entries (namely $i$ and $j$ for $N[i] \triangle N[j]$ ). Moreover, if ${k}=N(i)$ and $\operatorname{dist}(i, j)=2$, then $k \in N(j)$. Thus $V_{2}(G) \cap V_{N}(G)=$ $\emptyset$ follows.

数学代写|组合优化代写Combinatorial optimization代考|Complete p-Partite Graphs

In this section, we consider complete $p$-partite graphs and establish a connection to so-called complete 2-roses of order $n$. Given $n>q \geq 2$, let $\mathcal{R}{n}^{q}=(V, \mathcal{E})$ be the hypergraph where $V={1, \ldots, n}$ and $\mathcal{E}$ contains all $q$-element subsets of $V$. Nobili and Sassano $[17]$ called the incidence matrix of $\mathcal{R}{n}^{q}$ the complete $q$-rose of order $n$ and we denote it by $M\left(\mathcal{R}_{n}^{q}\right)$. In $[6]$, it was shown:

Theorem $2([2,6])$. The covering polyhedron $Q^{*}\left(M\left(\mathcal{R}_{n}^{q}\right)\right)$ is given by the nonnegativity constraints and
$$x\left(V^{\prime}\right) \geq\left|V^{\prime}\right|-q+1$$
for all subsets $V^{\prime} \subseteq{1, \ldots, n}$ with $\left|V^{\prime}\right| \in{q+1, \ldots, n}$.

Complete Bipartite Graphs. First we consider complete bipartite graphs $K_{m, n}$ with bipartition $A={1, \ldots, m}$ and $B={m+1, \ldots, m+n}$. We note that $K_{m, n}$ has false twins (unless $m=1=n$ ) and, thus, no $O L D$-set, hence we only analyse $L T D$-sets. We begin with the case of stars $K_{1, n}$, i.e., $A={1}$ and $n \geq 2$. Note that $K_{1,2}=P_{3}$ and it is easy to see that $\gamma_{L T D}\left(K_{1,2}\right)=2$ holds.
Lemma 1. For a star $K_{1, n}$ with $n \geq 3$, we have
$$C_{L T D}\left(K_{1, n}\right)=\left(\begin{array}{c|ccc} \frac{1}{0} & 0 & \ldots & 0 \ 0 & & & \ \vdots & M\left(\mathcal{R}_{n}^{2}\right) \end{array}\right) .$$
From the above description of the facets of the covering polyhedron associated with complete $q$-roses by [2], we conclude:

Corollary 3. $P_{L T D}\left(K_{1, n}\right)$ with $n \geq 3$ is described by the nonnegativity constraints, the inequalities $x_{1} \geq 1$ and $x\left(B^{\prime}\right) \geq\left|B^{\prime}\right|-1$ for all nonempty subsets $B^{\prime} \subseteq{2, \ldots, n+1}$.

Furthermore, combining $x_{1} \geq 1$ and $x(B) \geq|B|-1$ yields the full rank constraint $x(V) \geq|B|$ which immediately implies $\gamma_{L T D}\left(K_{1, n}\right)=|V|-1=n$ (and provides an alternative proof for the result given in [14]).

Observe that for $K_{2,2}$, it is easy to see that $\gamma_{L T D}\left(K_{2,2}\right)=2$. For general complete bipartite graphs $K_{m, n}$ with $m \geq 2, n \geq 3$, we obtain:

Lemma 2. For a complete bipartite graph $K_{m, n}$ with $m \geq 2, n \geq 3$, we have
$$C_{L T D}\left(K_{m, n}\right)=\left(\begin{array}{cc} M\left(\mathcal{R}{m}^{2}\right) & 0 \ 0 & M\left(\mathcal{R}{n}^{2}\right) \end{array}\right) .$$
Note that results from [2] show that $C_{I D}\left(K_{m, n}\right)=C_{L T D}\left(K_{m, n}\right)$. Hence, we directly conclude from the facet description of $P_{I D}\left(K_{m, n}\right)$ by [2]:
Corollary 4. $P_{L T D}\left(K_{m, n}\right)$ is given by the inequalities

1. $x(C) \geq|C|-1$ for all nonempty $C \subseteq A$,
2. $x(C) \geq|C|-1$ for all nonempty $C \subseteq B$.
Moreover, $\gamma_{L T D}\left(K_{m, n}\right)=|V|-2=m+n-2$.
This provides an alternative proof for the result given in [14].

数学代写|组合优化代写Combinatorial optimization代考|Locating Total-Dominating Sets in Graphs

• 一个识别码（ID），如果它是一个支配集，并且ñ[一世]∩C≠ñ[j]∩C, 对于不同的一世,j∈在[15];
• 一个开放的定位支配集（OLD），如果它是一个全支配集并且ñ(一世)∩C≠ñ(j)∩C, 对于不同的一世,j∈在[19];
• 一个定位总支配集（LTD），如果它是一个总支配集，并且ñ(一世)∩ C≠ñ(j)∩C, 对于不同的一世,j∈在−C[13].

C大号吨D(G)≤C这大号D(G)

数学代写|组合优化代写Combinatorial optimization代考|Polyhedra Associated to OLD- and LT D-Sets

(a) 让G既没有孤立节点也没有假孪生。C⊆在是一个旧集当且仅当C与

(二)C⊆在是一个 LTD 集当且仅当C与大号吨D1ñ(一世)对全部一世∈在,

$$P_{X}(G)=Q^{}\left(M_{X}(G)\right)=\operatorname{conv}\left{\mathbf{x} \in \mathbb{Z }{+}^{|V|}: M{X}(G) \mathbf{x} \geq 1\right }$$
X- 多面体X∈这大号D,大号吨D. 我们首先解决两个多面体的维度。它从巴拉斯和ñG[7]一个覆盖多面体的集合问(米)是全维的当且仅当矩阵米每行至少有两个。

数学代写|组合优化代写Combinatorial optimization代考|Complete p-Partite Graphs

X(在′)≥|在′|−q+1

C大号吨D(ķ1,n)=(100…0 0 ⋮米(Rn2)).

C大号吨D(ķ米,n)=(米(R米2)0 0米(Rn2)).

1. X(C)≥|C|−1对于所有非空C⊆一种,
2. X(C)≥|C|−1对于所有非空C⊆乙.
而且，C大号吨D(ķ米,n)=|在|−2=米+n−2.
这为 [14] 中给出的结果提供了另一种证明。

有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。