0
$\begingroup$

Are there counter examples to the conjecture, that in a complete, finite and symmetric weighted graph $G\left(V,E,\omega\right),\ E=\lbrace \lbrace i,j\rbrace\subset V\times V\rbrace,\ \omega:E\ni e\mapsto\mathbb{R_0^+}$ the edges constituting to the solution of $$min\frac{\sum_{i,j} \alpha_{ij}\omega(e_{ij})}{\sum_{i,j} \alpha_{ij}}$$ $$\sum_{i\ne u}\alpha_{iu}=0,\quad \sum_{i\ne u}\alpha_{ui}=1 $$ $$\sum_{j\ne v}\alpha_{jv}=1,\quad \sum_{j\ne v}\alpha_{vj}=0 $$ $$\sum_{i\notin\lbrace j,k,u,v\rbrace}\alpha_{ik}\ -\sum_{j\notin\lbrace i,k,u,v\rbrace}\alpha_{kj}=\ 0$$ $$\alpha_{ij}\in\lbrace 0,1\rbrace$$

i.e. to the path connecting $u$ to $v$ with minimal average edge-weight are elements of the set of edges constituting to the MST?


Edit to further explain, as requested by Brendan McKay:

  • the graphs, that this question relates to, are undirected and shall have no cycles of negative length; it is further required, that the graph is connected and if not, the question relates to the connected components.

  • a simple path connecting two distinct vertices $u$ and $v$ in such a graph is characterized

    • by the set $P_{uv}$ of edges constituting to that connecting simple path,
    • by the cardinality $C_{uv}$ of that set of edges.
    • by the sum of weights $L_{uv}$ of $P_{uv}$, i.e. the path's length

    • the average edge-length of $P_{uv}$ is then defined as $\frac{L_{uv}}{C_{uv}}$.
      This must not be confused with the average path-length, which is also a the subject of research!


for explaining, what is conjectured, further notation is introduced:

$P_{uv}^E$, $L_{uv}^E$ and $C_{uv}^E$ shall be the set of edges, its sum of weights and its cardinality of a path between $u$ and $v$ consisting of edges from the entire edge-set $E$ of $G$, whereas for $P_{uv}^{MST}$, $L_{uv}^{MST}$ and $C_{uv}^{MST}$ the set of edges shall be restricted to $G$'s minimum spanning tree MST.

Conjecture: $$\frac{L_{uv}^{MST}}{C_{uv}^{MST}}\ \le\ \frac{L_{uv}^E}{C_{uv}^E}\ \forall u,v\in G$$

$\endgroup$
  • $\begingroup$ Please explain better. What are the conditions and what is the (conjectured?) conclusion? $\endgroup$ – Brendan McKay Mar 25 '18 at 0:25
0
$\begingroup$

Meanwhile I found a simple counterexample: enter image description here

the least average edge-length of a path from node A to node D would be A$\mapsto$B$\mapsto$C$\mapsto$D with an average edge length of $\frac{1+1+2}{3}=\frac{4}{3}$, whereas in the MST (bold lines) the only path from A to D is A$\mapsto$D with a length of $\frac{2}{1}=2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.