查看: 97|回复: 1

俄罗斯数学家用半个多世纪否定一项假设

[复制链接]

1

精华

70

帖子

70

积分

新手上路

Rank: 1

积分
70
爱心
0
学币
307
贡献
0
最后登录
2019-7-22
发表于 2019-7-6 22:55:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
注意:该文章为科学类阅读,前半部分指明图论被否定,图论所存在的问题,后半部分讲述了此假设的历史以及其问题的复杂性,该部分较难。可以只阅读前一部分。
Un matemático ruso desmiente una conjetura con más de medio siglo de vida

微信图片_20190706224539.jpg

ALBERTO MÁRQUEZ Y ÁGATA TIMÓN G LONGORIA
5 JUL 2019 - 12:13 EDT


Casi coincidiendo con su 30 cumpleaños (fue el pasado 3 de junio), el nombre de Yaroslav Shitov ha aparecido en buena parte de la prensa(报纸)mundial. Este matemático ruso ha probado que una conjetura(假设)con más de medio siglo de vida sobre un problema de teoría de grafos(图论)es falsa, dando un contraejemplo(反例), es decir, aportando un caso en el que no se cumple lo que la conjetura predecía que sucedía siempre.

图论〔 Teoría de Grafos〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。

Los grafos son una de las estructuras más simples y, a la vez, más versátiles(能转动的)de las matemáticas, con gran cantidad de aplicaciones (desde el diseño de redes de comunicaciones a la distribución de mercancías(货物)y planificación de la producción). Los componen(构成)dos tipos de elementos: vértices(顶点)o puntos, y aristas(交点), que son parejas de puntos. Se suele representar un grafo por un dibujo en el que los vértices son puntos en el plano y las aristas son segmentos(片,段)que los unen.

Uno de los problemas más estudiados en este campo trata de encontrar el mínimo número de colores que se pueden asignar a los vértices de tal forma que no existan dos con el mismo color que estén unidos por una arista.

微信图片_20190706224551.jpg


El problema de coloreado de grafos se suele usar para clasificar objetos o para optimizar(优化)procesos. Por ejemplo, los vértices pueden ser tareas a completar por un conjunto de trabajadores y una arista entre dos vértices indica que esas dos tareas las ha de realizar el mismo trabajador, o que son incompatibles(不可兼容的)por alguna otra razón. Si cada color representa una franja(带)de tiempo, podemos asegurar que las tareas representadas en el grafo anterior necesitan al menos tres franjas de tiempo para completarse.

La historia del coloreado de grafos es muy extensa y se puede remontar(追溯)a mediados del siglo XIX, cuando Francis Guthrie (o su hermano) conjeturó(推测)que cualquier grafo que se pueda dibujar en el plano de forma que dos aristas distintas no se crucen, salvo en un vértice común, se puede colorear siempre con cuatro colores o menos. Este es el llamado problema del mapa de los cuatro colores, que fue resuelto definitivamente por los matemáticos Kenneth Appel y Wolfgang Hanken en 1976, más de 125 años después.

Aunque parezcan juegos de niños, los problemas de coloración pueden ser endiabladamente(极为)complicados: determinar si un grafo puede ser coloreado con menos de una cantidad fija de colores es un problema NP-completo. Esto significa que si nos dan una posible coloración, podemos comprobar tanto si tiene menos de los colores que nos piden y si es válida(有效的), pero es tremendamente(极为)difícil encontrar esa coloración si no nos la dan. Por tanto(因此), si encontramos un algoritmo(算法)que resuelva de forma eficiente el problema de colorear grafos (con una cantidad de operaciones menor que una cantidad relacionada con el número de vértices del grafo), podemos ir al instituto Clay y reclamar un millón de dólares, porque habremos demostrado que P es distinto a NP, y con ello uno de los célebres problemas del milenio cuya resolución lleva asignada ese premio. Si alguno de los lectores tiene el algoritmo pero no entiende por qué implica que P es distinto de NP, los autores de este artículo se brindan a aclarar las dudas. Compartiendo parte del premio, claro está.

Dada la complicación de los problemas de coloreado, un avance sería saber cuál es el mínimo número de colores necesarios para algunos tipos de grafos. Y en este contexto aparece la conjetura de Hedetniemi. En 1966 Stephen Hedetniemi conjeturó en su tesis doctoral que dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial GXH es el menor de los colores necesarios para colorear G y H. Este grafo se obtiene combinando de cierta forma los vértices y aristas de G y H.

Esto se cumplía para todos los ejemplos que se habían encontrado hasta hace un mes, pero nadie había conseguido demostrarlo formalmente. Y por una buena razón: porque es falso. El joven matemático ruso Shitov ha encontrado dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H, demostrando así que la conjetura de Hedetniemi es falsa.

Los ejemplos G y H de Shitov son grafos enormes: es posible que G tenga 2200 vértices, lo cual es un número inmenso, de un orden de magnitud cercano al número de partículas elementales(基本粒子)que podemos encontrar en todo el universo visible. Pero H es aún mayor, mucho mayor, con más de 220000 vértices. De hecho no los construye explícitamente en su corto artículo (dos páginas y media). Pero demuestra que existen basándose en propiedades conocidas, con lo que queda resuelto el problema.




文章来源:https://elpais.com/elpais/2019/0 ... 1975026_683783.html
ÁNIMO!!!

0

精华

226

帖子

226

积分

中级会员

Rank: 3Rank: 3

积分
226
爱心
0
学币
400
贡献
0
最后登录
2019-7-12
发表于 2019-7-7 15:27:21 | 显示全部楼层
收藏了,待后面学习会用到。感谢楼主!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则