The Triangle Inequality

Many approximation algorithms for the Traveling Salesman Problem (TSP) assume that the graph satisfies the triangle inequality:

\[ c(x,y) \le c(x,z) + c(z,y) \]

for any vertices \(x\), \(y\), and \(z\).

This assumption is used in algorithms such as Rosenkrantz-Stearns-Lewis and Christofides.

Problem Statement

Which of the following statements is true?

a) Consider a complete weighted graph whose vertices are points in \(\mathbb{R}^3\). The weight of an edge is the Euclidean distance between its endpoints. In this graph, the triangle inequality is guaranteed to hold.

b) Consider a complete weighted graph whose vertices are points in \(\mathbb{R}^3\). The weight of an edge is the square of the Euclidean distance between its endpoints. In this graph, the triangle inequality is guaranteed to hold.

c) Consider a complete weighted graph whose edge weights are chosen independently by a random process. In this graph, the triangle inequality is guaranteed to hold.

d) Consider a weighted bipartite graph. Regardless of the edge weights, the triangle inequality is guaranteed to hold.

e) None of the above.

Original idea by: Luis Alberto Vásquez Vargas

Comments

Inverse Problem for Degree Sequences

Let G = (V,E) be a simple undirected graph , meaning that it has no self-loops (edges of the form (v,v)) and no multiple edges between the same pair of vertices. For such a graph we can define its degree sequence deg , where each element represents the degree of a vertex. For example, the graph shown below has degree sequence deg = (3,1,1,1) In this exercise we consider the inverse problem : given a degree sequence deg , determine whether it is possible to construct a simple undirected graph with that sequence. For each of the following statements, determine whether it is True (T) or False (F) . i) deg = (2,2) generates more than one graph. ii) deg = (2,2,2) generates exactly one graph. iii) deg = (2,2,2,2,2,2) generates exactly one graph. Alternatives a) TTF b) FTT c) TFT d) FTF e) None of the above Original idea by: Luis Alberto Vásquez Vargas

The Barking Dog Dilemma

Albert enjoys walking through his neighborhood to buy groceries. He models the neighborhood as an undirected simple graph \(G=(V,E)\), where: Each corner is represented by a vertex . Each street connecting two corners is represented by an edge . Albert starts from his home at vertex \(s\) and wants to reach the grocery store at vertex \(t\). Some dogs in the neighborhood bark aggressively. Dogs may be located either at corners or along streets , and they are represented in the graph as follows: If a dog is located at a corner , the corresponding vertex is considered unsafe . If a dog is located along a street , the corresponding edge is considered unsafe . Consider the graph with: Vertices \(V=\{s,1,2,3,4,5,6,t\}\) Edges \(E=\{(s,1),(s,3),(1,3),(1,2),(3,4),(3,6),(4,5),(5,6),(4,2),(2,t)\}\) Additionally: Edge \((1,2)\) is unsafe. Edge \((3,4)\) is unsafe. Vertex \(1\) is unsafe. s 1 2 3 4 5 6 t ...

Logistics Grid

A mining site consists of \(n\) Extraction Mines and \(m\) Refining Plants (where \(n, m \geq 1\)). For logistical efficiency, every mine must be connected to every plant by a direct road. In mathematics, we represent this as a complete bipartite graph , denoted by \(K_{n, m}\). In this bipartite structure, the nodes are divided into two distinct sets: a set of \(n\) nodes representing the mines and a set of \(m\) nodes representing the plants. Connections only exist between nodes of different sets—never between two mines or two plants. To prevent traffic collisions, these roads are built on a single flat plain and must be planar (meaning no two roads are allowed to cross). Problem Statement Consider a "Feasibility Matrix" \(M\) for all \(n, m \geq 1\), where an entry \(M_{n,m} = 1\) if a planar layout for the graph \(K_{n, m}\) is possible, and \(0\) otherwise. Which of the following statements is true? a) \(M_{n, m} = 0\)...

Quiz - MO412 - Luis Vásquez

Search This Blog