Gráfico Mediana
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de abril de 2018; las comprobaciones requieren 2 ediciones .La mediana es el vértice de la gráfica para el cual la suma de las distancias más cortas desde ella hasta los vértices de la gráfica es la mínima posible.
Sea necesario elegir un lugar para colocar una centralita telefónica, una subestación eléctrica, bases de suministro en una red de carreteras o un departamento de clasificación en un servicio postal. En todos estos problemas de ubicación de instalaciones, se requiere ubicar esta instalación de tal manera que la suma de las distancias más cortas desde esta instalación hasta los vértices del gráfico sea lo más pequeña posible. La ubicación óptima del punto en el sentido indicado se llama mediana de la gráfica.
El problema de la p-mediana
El problema de encontrar la p-mediana de un gráfico dado es el problema de ubicar un número dado (digamos, p) de instalaciones tal que la suma de las distancias más cortas desde los vértices del gráfico hasta las instalaciones más cercanas tome el valor mínimo posible. .
p-mediana de un gráfico
Generalicemos el concepto de mediana definiendo p-mediana .
Sea un subconjunto del conjunto de vértices X de un grafo dirigido y suponga que contiene p vértices. Redefinimos la siguiente notación:
![d(X_{p},x_{j})=mín[d(x_{i},x_{j})]](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ed24de42d47746aed900a839b8f93e51e1feb06)
, donde se busca lo mínimo por encima de todo .
![d(x_{j},X_{p})=mín[d(x_{j},x_{i})]](https://wikimedia.org/api/rest_v1/media/math/render/svg/0feb36d6a3782c8dc7ee479a869b892f9b4887e4)
Si es un vértice de , en el que se alcanza el mínimo en las fórmulas anteriores, entonces se dice que el vértice está unido a .
Las relaciones de transmisión de un conjunto de vértices se definen de manera similar a las relaciones de transmisión de un solo vértice:
- relación de transmisión externa ,
- relación de transmisión interna .
El conjunto para el cual (se busca el mínimo sobre todos ) se denomina p-mediana externa del gráfico , y la p-mediana interna se define de manera similar.
![\sigma _{o}(X_{o}^{*})=mín[\sigma _{o}(x_{i})]](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc8c6d7cd03b0f8432a45b7e84b1b0303d7e113e)
Absoluta p-mediana
Para simplificar la tarea, consideraremos aún más un gráfico no dirigido G. Entonces los índices "t" y "o" estarán ausentes, ya que las relaciones de transmisión externas e internas coincidirán. El punto del gráfico (vértice o punto del arco), para el cual la relación de transmisión tomará el valor más pequeño, se denominará mediana absoluta del gráfico G.
Literatura
- Christofides N. Teoría de grafos. Enfoque algorítmico. — M .: Mir, 1978.
- E. Mainik. Algoritmos de optimización para redes y grafos. — M .: Mir, 1981. — 324 p.