Gráficos multiaspecto: representación algebraica y algoritmos
Autores: Wehmuth, Klaus; Fleury, Éric; Ziviani, Artur
Idioma: Inglés
Editor: MDPI
Año: 2016
Acceso abierto
Artículo científico
2016
Gráficos multiaspecto: representación algebraica y algoritmos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Representación algebraica
Gráficos multiAspect
Forma de matriz
Algoritmos de gráficos
Gráficos dirigidos
Implementaciones de Python
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Presentamos la representación algebraica y los algoritmos básicos para Grafos de Múltiples Aspectos (MAGs). Un MAG es una estructura capaz de representar redes de capas múltiples y variables en el tiempo, así como redes de orden superior, manteniendo la propiedad de ser isomorfo a un grafo dirigido. En particular, mostramos que, como consecuencia de las propiedades asociadas con la estructura MAG, un MAG puede ser representado en forma de matriz. Además, también demostramos que cualquier función MAG posible (algoritmo) puede obtenerse a partir de esta representación basada en matrices. Este es un resultado teórico importante ya que allana el camino para adaptar algoritmos de grafos conocidos para su aplicación en MAGs. Presentamos un conjunto de algoritmos MAG básicos, construidos a partir de algoritmos de grafos conocidos, como el cálculo de grados, la Búsqueda en Anchura (BFS) y la Búsqueda en Profundidad (DFS). Estos algoritmos adaptados al contexto MAG pueden usarse como primitivas para construir otros algoritmos MAG más sofisticados. Por lo tanto, tales ejemplos pueden considerarse como pautas sobre cómo derivar adecuadamente algoritmos MAG a partir de algoritmos básicos en grafos dirigidos. También ponemos a disposición implementaciones en Python de todos los algoritmos presentados en este documento.
Descripción
Presentamos la representación algebraica y los algoritmos básicos para Grafos de Múltiples Aspectos (MAGs). Un MAG es una estructura capaz de representar redes de capas múltiples y variables en el tiempo, así como redes de orden superior, manteniendo la propiedad de ser isomorfo a un grafo dirigido. En particular, mostramos que, como consecuencia de las propiedades asociadas con la estructura MAG, un MAG puede ser representado en forma de matriz. Además, también demostramos que cualquier función MAG posible (algoritmo) puede obtenerse a partir de esta representación basada en matrices. Este es un resultado teórico importante ya que allana el camino para adaptar algoritmos de grafos conocidos para su aplicación en MAGs. Presentamos un conjunto de algoritmos MAG básicos, construidos a partir de algoritmos de grafos conocidos, como el cálculo de grados, la Búsqueda en Anchura (BFS) y la Búsqueda en Profundidad (DFS). Estos algoritmos adaptados al contexto MAG pueden usarse como primitivas para construir otros algoritmos MAG más sofisticados. Por lo tanto, tales ejemplos pueden considerarse como pautas sobre cómo derivar adecuadamente algoritmos MAG a partir de algoritmos básicos en grafos dirigidos. También ponemos a disposición implementaciones en Python de todos los algoritmos presentados en este documento.