SOBRE LOS ISOMORFISMO DE GRAFO

ISADORE NABI

En teoría de grafos, se define como grafo al par G=(V,E), en donde V es el conjunto de aquellos elementos que son vértices y E es el conjunto de pares de vértices cuyos elementos se denominan aristas. A continuación, se presenta un ejemplo simple de grafo con tres vértices (círculos azules) y tres aristas (líneas rectas negras), específicamente un triángulo rectángulo visto como grafo.

Fuente: (Wikimedia, 2021).

Un isomorfismo entre dos grafos G1 y G2 es una relación funcional biyectiva (i.e., que establece una relación uno-a-uno entre los elementos de dos conjuntos) entre los vértices de G1 y G2, que adopta la forma f: V(G1)–>V(G2), en la que cualesquiera dos vértices u, v ∈ G1 son adyacentes (relación entre dos vértices en la que ambos son extremos de la misma arista) si y solo si sus reflejos o imágenes matemáticas f(u) y f(v) son adyacentes en G2. La característica fundamental de un isomorfismo de grafo es que es una relación funcional biyectiva que preserva las aristas que caracterizan al grafo. Que esta transformación matemática preserve las aristas implica que las distancias entre los vértices, analizados estos “de dos en dos”, no cambian.

Son precisamente estas distancias a las que se les conoce como distancias relativas dentro de la estructura matemática, en contraste con las distancias absolutas que son medidas como distancias de los vértices considerados individualmente. Un ejemplo de ello se muestra a continuación.

Fuente: (Jose, 2020).

Los dos grafos anteriores son isomórficos entre sí, i.e., poseen la misma estructura interna o estructura topológica. A continuación, se presenta un ejemplo numérico de ello, en consonancia con lo anteriormente expuesto.

Fuente: (Wikipedia, 2021).

Las diferencias concretas entre las distancias topológicas y las distancias métricas pueden observarse con nitidez en lo relativo al desarrollo teórico y aplicado de modelos que explican el comportamiento colectivo de animales, como lo son bandadas de aves, bancos de peces, etc. Esto es un equivalente concreto a nivel biológico del concepto matemático abstracto de la manera en que se agrupan en subconjuntos los elementos de un determinado conjunto).

Como señala el Instituto de Sistemas Complejos de Italia (Instituto dei Sistemi Complessi, 2021), todos los modelos existentes sobre el comportamiento colectivo de los animales asumen que la interacción entre los diferentes individuos depende de la distancia métrica, al igual que en la Física. Esto implica, por ejemplo, que dos pájaros separados por 5 metros interactúan con más fuerza que dos pájaros separados por 10 metros. Como se señala en la fuente citada, los modelos desarrollados por biólogos se basan en un esquema de “zonas de comportamiento”, donde cada zona está asociada a uno de los tres componentes básicos de todos los modelos: repulsión de corto alcance, alineación, atracción de largo alcance. Los modelos desarrollados por físicos, por otro lado, usaban principalmente una función de fuerza única. Sin embargo, los dos enfoques son sustancialmente equivalentes y lo que importa es que ambos se basan en un paradigma métrico.

El punto crucial es que, dentro del paradigma métrico, el número de vecinos con los que interactúa cada individuo no es una constante, sino que depende de la densidad. Por ejemplo, supóngase que cada ave interactúa con todos los vecinos dentro de un rango de 5 metros. El número de vecinos dentro de los 5 metros será grande en una bandada densa y pequeña en una bandada escasa. Entonces, dentro del paradigma métrico, el número de vecinos que interactúan no es una constante, sino que depende de la densidad. Lo que es constante es el rango métrico de la interacción (5 metros en el ejemplo anterior).

El paradigma métrico parece muy razonable a primera vista. Los animales son buenos para evaluar distancias, por lo que tiene sentido asumir que la fuerza de sus lazos mutuos depende de la distancia. Además, los modelos métricos demostraron ser capaces de reproducir cualitativamente el comportamiento de las bandadas. Por lo tanto, no había razón para cuestionar el paradigma métrico, en ausencia de datos empíricos. Y dado que hasta el momento no se disponía de datos empíricos, todos los modelos utilizaron una interacción métrica.

Los primeros datos empíricos sobre grandes bandadas de estorninos fueron obtenidos por el nodo INFM-CNR dentro del proyecto STARFLAG (esto hace referencia a un proyecto sobre comportamiento colectivo de animales coordinado por el INFM-CNR, organismo que pertenece a la institución citada). Al reconstruir las posiciones en 3D de aves individuales, fue posible mapear la distribución promedio de los vecinos más cercanos (Figura 2), lo que proporciona la caracterización más clara de la estructura de las aves dentro de una bandada.

Así, “Dado un ave de referencia, medimos la orientación angular de su vecino más cercano con respecto a la dirección de movimiento de la bandada, es decir, el rumbo y la elevación del vecino. Repetimos esto tomando a todos los individuos dentro de una bandada como ave de referencia, y de esta manera mapeamos la posición espacial promedio de los vecinos más cercanos.” (Instituto dei Sistemi Complessi, 2021). El fragmento de la cita bibliográfica anterior en negrita y cursiva es en esencia la lógica de tomar a los individuos “de dos en dos”, añadiendo a ello elementos que juegan un rol relevante en este contexto específico de aplicación de las nociones topológicas, como lo son el rumbo y la elevación; sin embargo, hay que decir que a nivel de teoría de grafos, también existen grafos cuyas aristas poseen dirección, los cuales por motivo de simplicidad no fueron expuestos, aunque no por ello deja de ser necesaria esta especificación.

Así, es posible pensar en este mapa como un mapa de la esfera alrededor de cada ave voladora. El centro del mapa es la dirección de avance, los polos son las direcciones hacia arriba y hacia abajo. El color en un punto dado del mapa indica la probabilidad de que el vecino más cercano del pájaro esté en esa dirección particular. Este mapa muestra una sorprendente falta de vecinos más cercanos a lo largo de la dirección del movimiento. Por tanto, la estructura de los individuos es fuertemente anisotrópica[1]. Esta anisotropía probablemente esté relacionada con el aparato visual de las aves. Sin embargo, el punto crucial es que esta anisotropía es el efecto de la interacción entre individuos, cualquiera que sea esta interacción.

Fuente: (Instituto dei Sistemi Complessi, 2021).

Para respaldar esta afirmación, calculamos la distribución de vecinos muy alejados del ave de referencia, por ejemplo, para el décimo vecino más cercano (mapa inferior en la figura).

Fuente: (Instituto dei Sistemi Complessi, 2021).

Esta distribución es uniforme, para garantizar una agregación de puntos completamente isótropa[2] y sin interacción, puesto que ello es una indicación empírica directa de afirmar que la interacción decae con la distancia: cuanto más separadas están dos aves, menor es su grado de correlación. Este resultado también demuestra que podemos usar la anisotropía para obtener información sobre la interacción. De hecho, se puede calcular el mapa de distribución angular[3] de los vecinos incluso para el segundo, tercer, cuarto vecino más cercano, etc., y observar cómo la estructura anisotrópica presente para los vecinos más cercanos se desvanece progresivamente a medida que aumenta el orden del vecino.

La desintegración de esta estructura anisotrópica con la distancia se puede cuantificar de forma precisa calculando el factor de anisotropía gamma[4].  Esta cantidad decae a su valor isotrópico (no interactivo) 1/3 a medida que aumenta el orden n-ésimo del vecino, de manera similar a una función de correlación estándar.

“Sin embargo, el punto crucial es que n es una distancia topológica, es decir, es una distancia medida en unidades de aves, en lugar de metros. A partir del factor de anisotropía podemos calcular el rango topológico, definido como el punto donde el factor de anisotropía se vuelve igual a su valor de no interacción. Este rango topológico es simplemente el número promedio de vecinos con los que interactúa cada ave. Claramente, dada la densidad de la bandada, también podemos definir una distancia métrica estándar y, por lo tanto, un rango métrico de la interacción. El rango métrico de interacción no es más que la distancia máxima de las aves dentro del rango topológico.” Fuente: (Instituto dei Sistemi Complessi, 2021).

Así, el punto importante es que la densidad de las bandadas varía mucho de una bandada a otra, y esto implica que el rango topológico y métrico no puede ser constante cuando la densidad varía. Para dilucidar este punto crucial, considérese dos bandadas con diferentes densidades. Si la interacción depende de la distancia métrica, entonces el rango en metros es el mismo en las dos bandadas, mientras que el número de individuos dentro de este rango es grande en la bandada más densa y pequeño en la más dispersa.

Fuente: (Instituto dei Sistemi Complessi, 2021).

Por el contrario, si la interacción depende de la distancia topológica, el rango en unidades de aves es constante en las dos bandadas, mientras que la distancia de estos n vecinos más cercanos es pequeña en la bandada más densa y grande en la más escasa.

La diferencia entre la hipótesis topológica y métrica es clara: en el escenario topológico, el número de individuos que interactúan es fijo. Por el contrario, en el escenario métrico, dicho número varía con la densidad; por ejemplo, dentro del mismo rango métrico puede haber 10 aves en una bandada muy densa y solo 1 ave en una muy escasa. Por lo tanto, los rangos topológicos y métricos no son caracterizaciones intercambiables de la interacción.

Por lo tanto, para comprender si lo que importa es la métrica o la distancia topológica, debemos medir cómo el rango métrico y topológico depende de la densidad de las bandadas. En promedio, para este caso de aplicación concreto se sostiene en la fuente citada que el rango topológico es igual a 6.5 aves. “Este resultado contrasta con la mayoría de los modelos y teorías de comportamiento animal colectivo actualmente en el mercado, que asumen un rango métrico de interacción.” Fuente: (Instituto dei Sistemi Complessi, 2021).

¿Por qué una interacción topológica y no métrica? El comportamiento colectivo de los animales se escenifica en un entorno natural convulso. Por tanto, el mecanismo de interacción formado por la evolución debe mantener la cohesión frente a fuertes perturbaciones, de las cuales la depredación es la más relevante. Creemos que la interacción topológica es el único mecanismo que otorga una cohesión tan robusta y, por lo tanto, una mayor aptitud biológica. Una interacción métrica es inadecuada para hacer frente a este problema: siempre que la distancia interindividual se hiciera mayor que el rango métrico, la interacción desaparecería, la cohesión se perdería y los rezagados se “evaporarían” de la agregación. Una interacción topológica, por el contrario, es muy robusta, ya que su fuerza es la misma a diferentes densidades. Al interactuar dentro de un número fijo de individuos, en lugar de metros, la agregación puede ser densa o escasa, cambiar de forma, fluctuar e incluso dividirse, pero manteniendo el mismo grado de cohesión. Por lo tanto, la interacción topológica es funcional para mantener la cohesión frente a las fuertes perturbaciones a las que está sujeta una bandada, típicamente depredación. Así, las distancias topológicas son aquellas distancias entre los elementos de un conjunto, o entre los componentes integrantes de un sistema dinámico, que se mantienen invariantes ante perturbaciones. Por ello, en línea con lo planteado en (Nabi, 2021) en el terreno de la biología molecular, las distancias topológicas denotan las propiedades características, i.e., la esencia, de los fenómenos naturales Lo que es más íntimo, más característico del comportamiento estudiado.

Finalmente, es necesario mencionar que existe evidencia de que el valor particular del rango topológico que encontramos (6.5) está relacionado con las capacidades cognitivas de las aves y, en particular, con sus habilidades pre numéricas[5].

REFERENCIAS

Instituto dei Sistemi Complessi. (27 de Febrero de 2021). Topolical vs Metric Distance. Obtenido de Biological Systems: https://www.isc.cnr.it/research/topics/physical-biology/biological-systems/topological-vs-metric-distance/

Jose, K. (27 de Junio de 2020). Graph Theory | Isomorphic Trees. Obtenido de Towards Data Science: https://towardsdatascience.com/graph-theory-isomorphic-trees-7d48aa577e46

Nabi, I. (14 de Marzo de 2021). HACIA UNA INTERPRETACIÓN DIALÉCTICA-MATERIALISTA DE LA TOPOLOGÍA GENERAL: GÉNESIS HISTÓRICA-TEÓRICA DE LA TOPOLOGÍA DESDE LA GEOMETRÍA Y LA TEORÍA DE CONJUNTOS. Obtenido de El Blog de Isadore Nabi: https://marxianstatistics.com/2021/03/14/hacia-una-interpretacion-dialectica-materialista-de-la-topologia-general-genesis-historica-teorica-de-la-topologia-desde-la-geometria-y-la-teoria-de-conjuntos/

Oilfield Glossary en Español. (2021). gamma (γ). Obtenido de Geofísica: https://glossary.oilfield.slb.com/es/terms/g/gamma

The SEG Wiki. (8 de Abril de 2021). Isotropía Transversal. Obtenido de Dictionary: https://wiki.seg.org/wiki/Dictionary:Transverse_isotropy/es

Wikimedia. (6 de Abril de 2021). Commons. Obtenido de Wikipedia: https://upload.wikimedia.org/wikipedia/commons/b/bf/Undirected.svg

Wikipedia. (6 de Julio de 2021). Graph isomorphism. Obtenido de Morphism: https://en.wikipedia.org/wiki/Graph_isomorphism


[1] La anisotropía es la propiedad general de la materia según la cual cualidades como elasticidad, temperatura, conductividad, velocidad de propagación de la luz, etc., varían según la dirección en que son examinadas.​ Un ente anisótropo puede presentar diferentes características según la dirección.

[2] La isotropía es la característica de algunos fenómenos en el espacio cuyas propiedades no dependen de la dirección en que son examinadas.

[3] La distribución angular de un conjunto de observaciones es la distribución de las direcciones hacia donde los electrones son emitidos dentro de un determinado sistema de coordenadas.

[4] Como se señala en (Oilfield Glossary en Español, 2021), el factor de anisotropía gamma es el parámetro de las ondas S para un medio en el cual las propiedades elásticas exhiben isotropía transversal vertical [implica propiedades elásticas que son las mismas en cualquier dirección perpendicular a un eje de simetría y tiene cinco constantes elásticas independientes, como se señala en (The SEG Wiki, 2021)]. Gamma (γ) es el parámetro de anisotropía de las ondas S y equivale a mitad de la razón de la diferencia entre las velocidades de las ondas SH que se propagan en sentido horizontal y vertical, al cuadrado, dividida por la velocidad de las ondas SH que se propagan verticalmente al cuadrado; una onda SH es una onda de corte polarizada horizontalmente.”

[5] Para el caso de los humanos, las habilidades pre numéricas son aquellas necesarias antes de aprender sobre los números, tales como comparar, clasificar, identificar, reunir, establecer relaciones uno a uno, seriar, etc.

UNA INVESTIGACIÓN HISTÓRICA, TEÓRICA Y MATEMÁTICA SOBRE EL CARÁCTER DIALÉCTICO DE LOS FUNDAMENTOS EPISTEMOLÓGICOS DE LA COMPLEJIDAD EN LOS SISTEMAS DINÁMICOS NO-LINEALES DE LARGO PLAZO

ISADORE NABI

Abstracto

Desde Pierre-Simon Laplace en 1840 con su célebre “Ensayo Filosófico Sobre Probabilidades”, los filósofos y científicos se han interesado por dicotomía, sugerida por la observación de los hechos de la realidad, entre la incertidumbre y el determinismo. Henri Poincaré en 1908 coge el testigo de Laplace, comenzando así el esfuerzo consciente por unificarlas filosóficamente y dando así nacimiento a la Teoría del Caos, para que luego Edward Lorenz en 1963 diera a luz los Sistemas Complejos en su investigación titulada “Deterministic Nonperiodic Flow” y finalmente fue Benoit Mandelbrot en 1982 quien revolucionó la Geometría con el planteamiento de las superficies fractales en su obra “La Geometría Fractal de la Naturaleza”. Así como para los sistemas complejos ha sido de vital importancia ir comprendiendo unificadamente el caos y el determinismo, también fue para los sistemas filosóficos (particularmente la Antigua Grecia y del Idealismo Clásico Alemán) alcanzar precisión en las definiciones de las categorías esencia, forma, contenido, apariencia y fenómeno. Estas categorías filosóficas fueron trabajadas por los filósofos soviéticos en su búsqueda por comprender de manera holista la realidad, siendo plasmadas en el célebre “Diccionario Filosófico” publicado en 1971. La presente investigación plantea que la forma óptima de instrumentalizar esa visión filosófica es nutriéndola de los hallazgos realizados en el campo de la Teoría del Caos y también que la forma óptima de depurar teóricamente lo relacionado a los sistemas complejos es mediante su análisis a la luz de la Lógica Dialéctica-Materialista.

Palabras Clave: Materialismo Dialéctico, Sistemas Complejos, Fractales, Teoría del Caos, Escuela de Filosofía Soviética.

REREFENCIAS

Aravindh, M., Venkatesan, A., & Lakshmanan, M. (2018). Strange nonchaotic attractors for computation. Physical Review E, 97(5), 1-10. doi:https://doi.org/10.1103/PhysRevE.97.052212

Barnet, W., & Chen, P. (1988). Deterministic Chaos and Fractal Atrractors as Tools for NonParametric Dynamical Econometric Inference: With An Application to the Divisa Monetary Aggregates. Computational Mathematics and Modeling, 275-296. Obtenido de http://www.maths.usyd.edu.au/u/gottwald/preprints/testforchaos_MPI.pdf

Bjorvand, A. (1995). A New Approach to Intelligent Systems Theory. The Norwegian Institute of Technology, The University of Trondheim, Faculty of Electrical Engineering and Computer Science. Trondheim: The University of Trondheim. Recuperado el 15 de Abril de 2020, de https://www.anderstorvillbjorvand.com/_service/53/download/id/3378/name/19950428_project_report_fractal_logic.pdf

Elert, G. (11 de Agosto de 2020). Flow Regimes – The Physics Hypertextbook. Recuperado el 11 de Agosto de 2020, de https://physics.info/turbulence/

Gottwald, G., & Melbourne, I. (2016). The 0-1 Test for Chaos: A review. En U. Parlitz, E. G. Lega, R. Barrio, P. Cincotta, C. Giordano, C. Skokos, . . . J. Laskar, & C. G. Sokos (Ed.), Chaos Detection and Predictability (págs. 221-248). Berlin: Springer.

Halperin, B. (2019). Theory of dynamic critical phenomena. Physics Today, 72(2), 42-43. doi:10.1063/PT.3.4137

Jaynes, E. (2003). Probability Theory. The Logic of Science. Cambridge University Press: New York.

Kessler, D., & Greenkorn, R. (1999). Momentum, Heat, and Mass Transfer Fundamentals. New York: Marcel Denker, Inc.

Kilifarska, N., Bakmutov, V., & Melnyk, G. (2020). The Hidden Link Between Earth’s Magnetic Field and Climate. Leiden: Elsevier.

Landau, L. (1994). Física Teórica. Física Estadística (Segunda ed., Vol. 5). (S. Velayos, Ed., & E. L. Vázquez, Trad.) Barcelona: Reverté, S.A.

Laplace, P.-S. (1902). A Philosophical Essay on Probabilities (1 ed.). (E. M. Pinto, Trad.) London: JOHN WILEY & SONS. Obtenido de http://bibliotecadigital.ilce.edu.mx/Colecciones/ReinaCiencias/_docs/EnsayoFilosoficoProbabilidades.pdf

Lesne, A. (1998). Renormalization Methods. Critical Phenomena, Chaos, Fractal Structures. Baffins Lane, Chichester, West Sussex, England: John Wiley & Sons Ltd.

Lesne, A., & Laguës, M. (2012). Scale Invariance. From Phase Transitions to Turbulence (Primera edición, traducida del francés (que cuenta con dos ediciones) ed.). New York: Springer.

Li, S., & Li, H. (2006). Parallel AMR Code for Compressible MHD or HD Equations. Los Alamos National Laboratory, Mathematical Modeling and Analysis. Nuevo México: Applied Mathematics and Plasma Physics. Obtenido de https://web.archive.org/web/20160303182548/http://math.lanl.gov/Research/Highlights/amrmhd.shtml

Linder, J., Kohar, V., Kia, B., Hippke, M., Learned, J., & Ditto, W. (4 de Febrero de 2015). Strange nonchaotic stars. Recuperado el 16 de Abril de 2020, de Nonlinear Sciences > Chaotic Dynamics: https://arxiv.org/pdf/1501.01747.pdf

Lorenz, E. (1963). Deterministic Nonperiodic Flow. JOURNAL OF THE ATMOSPHERIC SCIENCES, 20, 130-141.

Mandelbrot, B. (1983). THE FRACTAL GEOMETRY OF NATURE. New York: W.H. Freeman and Company.

Marxist.org. (21 de Junio de 2018). Formal Logic and Dialectics. Recuperado el 14 de Abril de 2020, de The Meaning of Hegel’s Logic: https://www.marxists.org/reference/archive/hegel/help/mean05.htm

McCullagah, P., & Nelder, J. (1989). Generalized Linear Models (Segunda ed.). New York, United States of America: Chapman & Hall.

Nabi, I. (18 de Marzo de 2021). Diferentes abordajes para el TCL con variables dependientes. Obtenido de La Biblioteca del Pueblo | El Blog de Isadore Nabi: https://mega.nz/folder/lERCnLxD#0RP8MLIq6vEYR5GBsA7kog/folder/UYRwHZaS

Nabi, I. (18 de Marzo de 2021). Diferentes abordajes para la LGN con variables dependientes. Obtenido de La Biblioteca del Pueblo | El Blog de Isadore Nabi: https://mega.nz/folder/lERCnLxD#0RP8MLIq6vEYR5GBsA7kog/folder/wVAiBTQZ

Oestreicher, C. (2007). A history of chaos theory. Dialogues in Clinical Neuroscience, 9(3), 279–289. Obtenido de https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3202497/pdf/DialoguesClinNeurosci-9-279.pdf

Pezard, L., & Nandrino, J. (2001). Paradigme dynamique en psychopathologie: la “Théorie du chaos”, de la physique à la psychiatrie [Dynamic paradigm in psychopathology: “chaos theory”, from physics to psychiatry]. Encephale, 27(3), 260-268. Obtenido de https://pubmed.ncbi.nlm.nih.gov/11488256/

Poincaré, H. (1908). Chance. En H. Poincaré, Science and Method (págs. 64-90). London: THOMAS NELSON AND SONS. Obtenido de https://www.stat.cmu.edu/~cshalizi/462/readings/Poincare.pdf

Princeton University. (30 de Septiembre de 2019). The Fundamental Postulate . Obtenido de http://assets.press.princeton.edu/chapters/s3_9634.pdf

ResearchGate. (3 de Mayo de 2018). When should one use Fuzzy set theory and Rough set theory? Is there any clear-cut line of difference between them? Recuperado el 6 de Julio de 2020, de https://www.researchgate.net/post/When_should_one_use_Fuzzy_set_theory_and_Rough_set_theory_Is_there_any_clear-cut_line_of_difference_between_them

ResearchGate. (2 de Mayo de 2020). What is the difference between Fuzzy rough sets and Rough fuzzy sets? Recuperado el 6 de Julio de 2020, de https://www.researchgate.net/post/What_is_the_difference_between_Fuzzy_rough_sets_and_Rough_fuzzy_sets

Rosental, M., & Iudin, P. (1971). Diccionario Filosófico. San Salvador: Tecolut.

Russell, K. (29 de Enero de 2014). Hypothesis testing. Recuperado el 15 de Abril de 2020, de Stats – Kevin Russell – University of Manitoba: http://home.cc.umanitoba.ca/~krussll/stats/hypothesis-testing.html

Sharma, V. (2003). Deterministic Chaos and Fractal Complexity in the Dynamics of Cardiovascular Behavior: Perspectives on a New Frontier. The Open Cardiovascular Medicine Journal(3), 110-123.

Stanford Encyclopedia of Philosophy. (4 de Febrero de 2002). Quantum Logic and Probability Theory. Recuperado el 6 de Julio de 2020, de https://plato.stanford.edu/entries/qt-quantlog/

Valdebenito, E. (1 de Julio de 2019). Fractales: La Geometría del Caos. Recuperado el 11 de Agosto de 2020, de viXra: https://vixra.org/pdf/1901.0152v1.pdf

Werndl, C. (2013). What Are the New Implications of Chaos for Unpredictability? The British Journal for the Philosophy of Science, 60(1), 1-25. doi:10.1093/bjps/axn053