Posted on Categories:Graph Theory, 图论, 数学代写

# 数学代写|图论代考GRAPH THEORY代写|Locating Numbers

avatest™

## avatest™帮您通过考试

avatest™的各个学科专家已帮了学生顺利通过达上千场考试。我们保证您快速准时完成各时长和类型的考试，包括in class、take home、online、proctor。写手整理各样的资源来或按照您学校的资料教您，创造模拟试题，提供所有的问题例子，以保证您在真实考试中取得的通过率是85%以上。如果您有即将到来的每周、季考、期中或期末考试，我们都能帮助您！

•最快12小时交付

•200+ 英语母语导师

•70分以下全额退款

## 数学代写|图论代写GRAPH THEORY代考|Locating Numbers

Suppose that a certain facility consists of five rooms $R_1, R_2, R_3, R_4, R_5$ (shown in Figure 12.16). The distance between rooms $R_1$ and $R_3$ is 2 and the distance between $R_2$ and $R_4$ is also 2. The distance between all other pairs of distinct rooms is 1 . The distance between a room and itself is 0 . A certain (red) sensor is placed in one of the rooms. If an unauthorized individual should enter a room, then the sensor is able to detect the distance from the room with the red sensor to the room containing the intruder. Suppose, for example, that the sensor is placed in $R_1$. If an intruder enters room $R_3$, then the sensor alerts us that an intruder has entered a room at distance 2 from $R_1$; that is, the intruder is in $R_3$ since $R_3$ is the only room at distance 2 from $R_1$. If the intruder is in $R_1$, then the sensor indicates that an intruder has entered a room at distance 0 from $R_1$; that is, the intruder is in $R_1$. However, if the intruder is in any of the other three rooms, then the sensor tells us that there is an intruder in a room at distance 1 from $R_1$. But with this information, we cannot determine the precise room containing the intruder. In fact, there is no room in which the (red) sensor can be placed to identify the exact location of an intruder in every instance.

On the other hand, if we place the red sensor in $R_1$ and a blue sensor in $R_2$ and an intruder enters $R_5$, say, then the red sensor in $R_1$ tells us that there is an intruder in a room at distance 1 from $R_1$, while the blue sensor tells us that the intruder is in a room at distance 1 from $R_2$, that is, the ordered pair $(1,1)$ is produced for $R_4$. Since these ordered pairs are distinct for all rooms, the minimum number of sensors required to detect the exact location of an intruder is 2. Care must be taken, however, as to where the two sensors are placed. For example, we cannot place sensors in $R_1$ and $R_3$ since, in this case, the ordered pairs for $R_2, R_4$ and $R_5$ are all $(1,1)$, and we cannot determine the precise location of a possible intruder.

The facility that we have just described can be modeled by the graph of Figure 12.17, whose vertices are the rooms and such that two vertices in this graph are adjacent if the corresponding two rooms are adjacent. This gives rise to a problem involving graphs.

## 数学代写|图论代写GRAPH THEORY代考|Detour and Directed Distance

While the standard distance $d(u, v)$ from a vertex $u$ to a vertex $v$ in a connected graph $G$ is the length of a shortest $u-v$ path in $G$, it is by no means the only definition of distance. For two vertices $u$ and $v$ in a connected graph $G$ of order $\mathrm{n}$, the detour distance $D(u, v)$ from $u$ to $v$ is defined as the length of a longest $u-v$ path in $G$. A $u-v$ path of length $D(u, v)$ is called a $u-v$ detour. For example, for the graph $G$ of Figure $12.21 d(u, v)=3$ while $D(u, v)=8$. A $u-v$ detour (drawn in bold) is also shown in that figure.

As with standard distance, detour distance is also a metric on the vertex set of every connected graph.
Theorem 12.15 Detour distance is a metric on the vertex set of every connected graph.
Proof. Let $G$ be a connected graph. Since (1) $D(u, v) \geq 0$, (2) $D(u, v)=0$ if and only if $u=v$ and (3) $D(u, v)=D(v, u)$ for every pair $u, v$ of vertices of $G$, it remains only to show that detour distance satisfies the triangle inequality.

Let $u, v$ and $w$ be any three vertices of $G$. Since the inequality $D(u, w) \leq D(u, v)+D(v, w)$ holds if any two of these three vertices are the same vertex, we assume that $u, v$ and $w$ are distinct. Let $P$ be a $u-w$ detour in $G$ of length $k=D(u, w)$. We consider two cases.

Case 1. v lies on $P$. Let $P_1$ be the $u-v$ subpath of $P$ and let $P_2$ be the $v-w$ subpath of $P$. Suppose that the length of $P_1$ is $s$ and the length of $P_2$ is $t$. So $s+t=k$. Therefore,
$$D(u, w)=k=s+t \leq D(u, v)+D(v, w) .$$
Case 2. $v$ does not lie on $P$. Since $G$ is connected, there is a shortest path $Q$ from $v$ to a vertex of $P$. Suppose that $Q$ is a $v-x$ path. Thus $x$ lies on $P$ but no other vertex of $Q$ lies on $P$. Let $r$ be the length of $Q$. Thus $r>0$ (see Figure 12.22).

## 数学代写|图论代写GRAPH THEORY代考|Detour and Directed Distance

$$D(u, w)=k=s+t \leq D(u, v)+D(v, w) .$$

## MATLAB代写

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