Artículo
Gradation in Greyscales of Graphs
Autor/es | Castro Ochoa, Natalia de
Garrido Vizuete, María de los Angeles Robles Arias, Rafael Villar Liñán, María Trinidad |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) Universidad de Sevilla. Departamento de Geometría y Topología |
Fecha de publicación | 2016 |
Fecha de depósito | 2021-09-14 |
Publicado en |
|
Resumen | In this work we present the notion of greyscale of a graph as a colouring
of its vertices that uses colours from the real interval [0,1]. Any greyscale
induces another colouring by assigning to each edge the non-negative ... In this work we present the notion of greyscale of a graph as a colouring of its vertices that uses colours from the real interval [0,1]. Any greyscale induces another colouring by assigning to each edge the non-negative dif- ference between the colours of its vertices. These edge colours are ordered in lexicographical decreasing ordering and give rise to a new element of the graph: the gradation vector. We introduce the notion of minimum grada- tion vector as a new invariant for the graph and give polynomial algorithms to obtain it. These algorithms also output all greyscales that produce the minimum gradation vector. This way we tackle and solve a novel vectorial optimization problem in graphs that may produce more satisfactory solu- tions than those ones generated by known scalar optimization approaches. The interest of these new concepts lies in their possible applications for solving problems of engineering, physics and applied mathematics which are modeled according to a network whose nodes have assigned numerical values of a certain parameter delimited by a range of real numbers. The ob- jective is to minimize the differences between each node and its neighbors, ensuring that the extreme values of the interval are assigned. |
Agencias financiadoras | Ministerio de Economia, Industria y Competitividad (MINECO). España Junta de Andalucía |
Identificador del proyecto | MTM2015-65397-P
PAI FQM-164 |
Cita | Castro Ochoa, N.d., Garrido Vizuete, M.d.l.A., Robles Arias, R. y Villar Liñán, M.T. (2016). Gradation in Greyscales of Graphs. ArXiv.org, arXiv:1612.07552 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Gradation in Greyscales of ... | 253.4Kb | [PDF] | Ver/ | |