Introducción
En matemáticas, como en la vida, las pequeñas decisiones pueden tener grandes consecuencias. Esto es especialmente cierto en la teoría de grafos, un campo que estudia las redes de objetos y las conexiones entre ellos. Aquí hay un pequeño rompecabezas para ayudarte a ver por qué.
Dados seis puntos, su objetivo es conectarlos entre sí con segmentos de línea para que siempre haya un camino entre cualquier par de puntos, sin que el camino exceda los dos segmentos de línea de longitud. Deje de desplazarse por un momento e intente encontrar una solución.
Si lo resolviste, apuesto a que tienes algo parecido a esto:
(haga clic aquí para revelar la respuesta)
Tenga en cuenta que esto de hecho satisface los requisitos del rompecabezas. Hay un camino entre dos puntos, lo que los teóricos de grafos llaman vértices, y ningún camino es más largo que dos segmentos de línea o bordes. (Nota: en el rompecabezas y en toda la columna, no se permite que las rutas usen el mismo borde más de una vez). Su solución puede verse ligeramente diferente, pero terminará con la misma estructura esencial, que es más fácil de ver si mueve un poco los vértices.
Esta estructura de "estrella" en la teoría de grafos tiene un vértice central que se conecta a cada uno de un grupo de otros vértices por un solo borde, sin bordes entre los otros vértices. Esta estrella no es solo una solución a nuestro rompecabezas; es la única solución. (Tendrá la oportunidad de probar esto en los ejercicios al final de la columna).
Este acertijo ilustra cómo las restricciones locales, como prohibir caminos de longitud 3 o más, a veces pueden obligar a estructuras globales, como la estrella, a surgir como resultado. Aprovechar relaciones como estas puede ser una herramienta poderosa para comprender gráficos y redes, especialmente cuando busca ciertas estructuras importantes.
Una de esas estructuras es una "camarilla", un conjunto de vértices donde cada vértice está conectado directamente con todos los demás vértices por un borde. Las camarillas son importantes porque identifican áreas de máxima conectividad y dependencia. Por ejemplo, en una red de rutas aéreas, una camarilla representa un grupo de ciudades conectadas entre sí por vuelos directos en ambas direcciones. Esta es una fuente de fortaleza en la red, ya que se puede llegar a cualquier ciudad en un solo vuelo, y si se cancela una ruta, aún se puede conectar a cualquier destino con relativa facilidad.
Por el contrario, una “anti-camarilla” es un conjunto de vértices donde ninguno está conectado directamente con los demás. En un mapa de vuelos, esto representa un grupo de ciudades sin vuelos directos entre ellas. Es posible que aún pueda ir del punto A al punto B en un anti-camarilla, pero no directamente. Primero tendrá que viajar fuera del grupo, por lo que llegar allí le costará: en tiempo, dinero o, más generalmente, en eficiencia. En cierto modo, las anticamarillas identifican zonas de máxima independencia en una red, por lo que también se conocen como conjuntos independientes. (También puede ver estos conjuntos denominados "cocliques" o "conjuntos estables" en otros lugares).
Encontrar grandes camarillas o grandes conjuntos independientes, o simplemente garantizar que existan, resulta ser una parte importante del análisis de gráficos y redes. Y ahí es donde entra en juego la conjetura de Erdős-Hajnal. Esta dice que si se prohíben ciertas estructuras locales en los gráficos, entonces ciertas estructuras globales, en particular, camarillas relativamente grandes o conjuntos independientes relativamente grandes, son inevitables. Es una de las muchas preguntas abiertas. atribuido a Paul Erdős, el famoso nómada matemático que viajó por el mundo compartiendo café y conjeturas con miles de colaboradores. Cuando se cumple la conjetura de Erdős-Hajnal, proporciona información que los científicos pueden utilizar en campos tan diversos como la biología, la logística y la informática para sacar conclusiones aún más sólidas sobre las estructuras globales de sus redes.
De hecho, ya hemos visto la conjetura de Erdős-Hajnal en acción. En nuestro rompecabezas original, la forma de estrella era inevitable y resulta que esa forma garantiza un gran conjunto independiente. Los cinco vértices conectados al centro de la estrella no tienen otras conexiones entre sí. Puedes ver este conjunto independiente ignorando el vértice central y las aristas que se conectan a él.
Nótese que la existencia de este conjunto independiente nos alerta de una vulnerabilidad en nuestra red. Si esto fuera un mapa de vuelo, y esa ciudad central se volviera inaccesible, nadie podría volar a ninguna parte.
En nuestro acertijo, prohibir la estructura local de caminos de longitud 3 o más garantiza un conjunto independiente de tamaño 5. Sin embargo, este acertijo se basa en algo que la conjetura de Erdős-Hajnal no hace, a saber, que existe un camino entre dos vértices cualesquiera. Esto significa que la gráfica debe estar "conectada", y esto no es parte de la conjetura de Erdős-Hajnal. ¿Es inevitable un gran conjunto independiente si dicho gráfico no está necesariamente conectado?
Para ver si podemos evitar un gran conjunto independiente en nuestro gráfico, pensemos como matemáticos y comencemos considerando casos extremos. Si no estamos obligados a conectar todo, ¿qué pasa si no conectamos nada?
No agregar ningún borde en realidad nos da el conjunto independiente más grande posible, los seis vértices. De hecho, cualquier vértice que no se conecta a una arista se puede agregar a cualquier conjunto independiente existente para hacerlo más grande, por lo que para obtener conjuntos independientes más pequeños probablemente querremos que cada vértice tenga al menos una arista. ¿Qué pasa con algo como esto?
Este gráfico está en dos partes y puedes obtener un conjunto independiente de tamaño 4 seleccionando los dos vértices en los extremos de cada parte. Observe cómo ninguno de los cuatro vértices elegidos está conectado por una arista a cualquiera de los otros, formando así un conjunto independiente.
¿Qué pasa con un gráfico como este?
Este gráfico está en tres partes desconectadas y puedes obtener un conjunto independiente de tamaño 3 seleccionando un vértice de cada parte.
Este resulta ser el conjunto independiente más pequeño que podemos lograr bajo las condiciones dadas. En otras palabras, en un gráfico con seis vértices, prohibir caminos de longitud 3 garantiza un conjunto independiente que es al menos la mitad del tamaño del gráfico original, que es bastante grande cuando se trata de gráficos.
En realidad, está pasando algo más general. Todos los gráficos que exploramos tienen una cosa importante en común: ¡Todos son conjuntos de estrellas!
El gráfico de la izquierda son dos estrellas de tres vértices cada una, y el gráfico de la derecha son tres estrellas de dos vértices cada una. Incluso el gráfico sin bordes se puede considerar como seis estrellas de un vértice cada una. La regla que prohíbe caminos de longitud 3 obliga a que el gráfico sea una colección de estrellas, y esto es cierto ya sea que empieces con seis vértices o con 600. Entonces, cuando se trata de encontrar conjuntos independientes, la única pregunta es con cuántas estrellas desconectadas terminas.
En general, si terminas con muchas estrellas, es fácil obtener un conjunto grande e independiente. Dado que las estrellas no están conectadas entre sí, solo puede elegir un vértice de cada estrella, lo que garantiza un conjunto independiente al menos tan grande como el número de estrellas. En el ejemplo de arriba a la derecha, puedes tomar un vértice de cada una de las tres estrellas de tamaño 2 y producir un conjunto independiente de tamaño 3.
Por otro lado, si terminas con solo unas pocas estrellas, las estrellas en sí deben ser lo suficientemente grandes para dar cuenta de todos los vértices en el gráfico original, y ya hemos visto cómo obtener un conjunto independiente relativamente grande de una estrella, solo toma todo menos el vértice central. Por ejemplo, si un gráfico consta de solo dos estrellas, se garantiza que una de las estrellas contenga al menos la mitad de los vértices del gráfico original, y esto garantiza un conjunto independiente de aproximadamente la mitad del tamaño del gráfico original. Podemos hacer un conjunto independiente aún más grande en nuestro ejemplo combinando los conjuntos independientes de las estrellas desconectadas. (¿Qué tan pequeño podría ser el conjunto independiente más grande posible? Consulte los ejercicios para obtener más información al respecto).
En general, para un gráfico que es solo una colección de estrellas desconectadas, es inevitable un gran conjunto independiente. Las estrellas grandes producen grandes conjuntos independientes, pero las estrellas pequeñas significan muchas estrellas, que también producen grandes conjuntos independientes. Este enfoque no solo funciona para nuestro ejemplo simple. También sugiere cómo manejar un problema más complicado.
Supongamos que tiene un gráfico con n vértices e impone la siguiente restricción local: no se pueden conectar tres vértices entre sí. Esto sería como diseñar un mapa de vuelo con el objetivo particular de minimizar las rutas localmente redundantes. Si puede llegar entre A y B y entre B y C, entonces no puede crear una ruta directa separada entre A y C.
En otras palabras, no puede haber camarillas de tamaño 3. En términos de geometría, el gráfico es "libre de triángulos".
¿Debe un gráfico sin triángulos tener un conjunto independiente relativamente grande? La respuesta es sí, y como antes, el secreto está en las estrellas. Podemos demostrar que un gráfico sin triángulos con n los vértices deben tener un conjunto independiente que tenga al menos un tamaño aproximado de $latex sqrt{n}$, que es relativamente grande según los estándares de la teoría de grafos. Analicemos el argumento usando el siguiente gráfico sin triángulos como ejemplo.
Comience eligiendo cualquier vértice en el gráfico y considerando todos sus vecinos, los vértices conectados a él por una arista.
Ninguno de estos vecinos de su vértice elegido está conectado entre sí, porque eso haría un triángulo y este es un gráfico sin triángulos, por lo que cada vértice y su conjunto de vecinos forman esencialmente una estrella.
Aunque esta estrella está conectada a otros vértices en el gráfico, aún podemos usar sus propiedades para garantizar un gran conjunto independiente. La clave es formar una estrella y luego eliminarla y todos los bordes que se conectan a ella.
Ahora busque una estrella en el gráfico restante y elimínela también.
En este ejemplo, ahora nos quedan dos vértices individuales, estrellas de un vértice, y formamos un conjunto independiente de tamaño 4 al agregar los vértices centrales de las otras dos estrellas que encontramos. Dado que nuestro gráfico original tiene nueve vértices y $latex sqrt{9}=3$, nuestro conjunto independiente de tamaño 4 se ajusta a nuestra conjetura.
Este argumento funciona en general para cualquier gráfico sin triángulos. La clave es seguir encontrando y eliminando estrellas y los bordes que se conectan a ellas hasta que hayas contabilizado todos los vértices. Una vez que hayas hecho eso, solo cuenta el número de estrellas.
Digamos que terminas con k estrellas. Si $latex k > sqrt{n}$, entonces puede formar un conjunto independiente de tamaño k tomando el vértice central de cada estrella. Esto funciona porque no se pueden conectar dos vértices centrales de dos estrellas cualquiera, ya que eso los habría convertido en vecinos en el gráfico original.
Si $latex k < sqrt{n}$, entonces este menor número de estrellas garantiza que al menos una de las estrellas debe ser relativamente grande. De hecho, debe tener al menos $latex sqrt{n}$ vértices. ¿Por qué? porque todos n Los vértices del gráfico deben encontrarse entre los k estrellas. si todos los k las estrellas tenían menos de $latex sqrt{n}$ vértices cada una, entonces el número total de vértices en el gráfico sería menor que $latex k por sqrt{n}$. Pero como $latex k < sqrt{n}$, esto significa que el número total de vértices en el gráfico debería ser menor que $latex sqrt{n} multiplicado por sqrt{n} = n$. Como sabemos que la gráfica tiene n vértices, la suposición de que las estrellas son pequeñas deja algunos vértices sin tener en cuenta, lo que significa que al menos una de las estrellas debe tener al menos $latex sqrt{n}$ vértices. Y una estrella de tamaño $latex sqrt{n}$ garantiza un conjunto independiente con un tamaño de al menos $latex sqrt{n} -1$, que es aproximadamente $latex sqrt{n}$. (Los teóricos de grafos generalmente están interesados en qué tan grande es un subgráfico en relación con el tamaño del gráfico original, por lo que $latex sqrt{n}$ es mucho más importante que $latex – 1$).
Al igual que con nuestro ejemplo original, este resultado sobre los gráficos sin triángulos está relacionado con la conjetura de Erdős-Hajnal. Si un gráfico no tiene triángulos, entonces no puede tener una camarilla de tamaño mayor que 2, ya que una camarilla de tamaño 3 o más requeriría un triángulo. Prohibir triángulos significa prohibir grandes camarillas, y esto obliga a que surjan grandes conjuntos independientes, tal como predice la conjetura de Erdős-Hajnal.
Los matemáticos demostraron recientemente mucho más. La conjetura de Erdős-Hajnal se ha probado en todos los casos en los que el subgrafo prohibido consta de cuatro o menos vértices (como un cuadrado o un camino de longitud 4). Y en 2021 un grupo de matemáticos demostrado que si un gráfico no contiene pentágonos, es decir, un bucle que conecta cinco vértices, entonces debe existir como consecuencia una camarilla inusualmente grande o un conjunto independiente inusualmente grande. Esto sorprendió a algunos de los matemáticos que lo probaron, ya que esperaban que la conjetura de Erdős-Hajnal fuera falsa para los pentágonos. Fue otro resultado matemático sorprendentemente poderoso que surgió de pensar localmente para actuar globalmente.
Introducción
Introducción
1. Supón que el conjunto independiente más grande que puedes encontrar en un gráfico tiene un tamaño de 1. ¿Qué puedes decir sobre el gráfico?
Haga clic para la respuesta 1:
Esto significa que todas las aristas posibles existen en el gráfico. En este caso, el gráfico en sí es una camarilla. Llamamos a tales gráficos "gráficos completos".
Introducción
2. Explica por qué es imposible obtener otra cosa que no sea una estrella en un gráfico conectado sin caminos de longitud 3 o más.
Haga clic para la respuesta 2:
Si solo hay un vértice, es una estrella y listo. Si hay dos vértices, deben estar conectados, formando una estrella de dos vértices. Si hay tres vértices, entonces hay tres posibles aristas que podrían existir entre ellos. Dadas las condiciones, los tres vértices deben formar un camino de longitud 2, así:
Esto se debe a que si faltara alguno de estos bordes, el gráfico no estaría conectado, pero si agregara el tercer borde, haría un triángulo, lo que le daría un camino de longitud 3.
Si hay otros vértices, ¿dónde podrían conectarse? Tendría que ser el vértice medio y el vértice medio solamente. Conectarse al vértice en cualquiera de los extremos crearía inmediatamente un camino de longitud 3. Por lo tanto, el resultado será un grupo de vértices, todos conectados por un solo borde a un vértice central. En otras palabras, una estrella.
Introducción
3. Supongamos un gráfico con n vértices no tiene caminos de longitud 3. ¿Qué tan grande se garantiza un conjunto independiente en tal gráfico?
Haga clic para la respuesta 3:
If n es par, $latex frac{n}{2}$; si n es impar, $latex frac{n+1}{2}$. En otras palabras, el “techo” de $latex frac{n}{2}$, escrito $latex lceil{frac{n}{2}}rceil$.
Ya sabemos que dicho gráfico debe ser una colección de estrellas desconectadas, y dado que las estrellas están desconectadas, siempre podemos formar un conjunto independiente combinando los conjuntos independientes de cada estrella individual. También sabemos que cada estrella puede contribuir con todos menos uno de sus vértices a un conjunto independiente simplemente quitando el centro. En particular, si una estrella tiene tamaño m > 1, entonces puede contribuir m − 1 de sus vértices a un conjunto independiente. La estrategia es hacer m − 1 lo más pequeño posible para cada estrella, y para hacer eso, haces tantas estrellas de dos vértices como puedas.
If n es incluso, terminas con un montón de pares como este:
Y forma un conjunto independiente tomando un vértice de cada uno, produciendo un conjunto independiente igual en tamaño al número de estrellas: $latex frac{n}{2}$.
If n es impar, te sobrará un vértice cuando emparejes los vértices.
Aquí, el conjunto independiente será un vértice de cada uno de los pares $latex frac{n-1}{2}$ más el vértice sobrante para un conjunto independiente de tamaño $latex frac{n-1}{2} + 1 = frac{n+1}{2}$.
- Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
- PlatoData.Network Vertical Generativo Ai. Empodérate. Accede Aquí.
- PlatoAiStream. Inteligencia Web3. Conocimiento amplificado. Accede Aquí.
- PlatoESG. Automoción / vehículos eléctricos, Carbón, tecnología limpia, Energía, Ambiente, Solar, Gestión de residuos. Accede Aquí.
- Desplazamientos de bloque. Modernización de la propiedad de compensaciones ambientales. Accede Aquí.
- Fuente: https://www.quantamagazine.org/math-that-lets-you-think-locally-but-act-globally-20230721/
- :posee
- :es
- :no
- :dónde
- ][pag
- $ UP
- 1
- 2021
- a
- Poder
- Nuestra Empresa
- arriba
- Mi Cuenta
- Lograr
- Actúe
- la columna Acción
- adicional
- la adición de
- línea aérea
- Alertas
- Todos
- permitido
- ya haya utilizado
- también
- hacerlo
- entre
- an
- el análisis de
- y
- Otra
- https://www.youtube.com/watch?v=xB-eutXNUMXJtA&feature=youtu.be
- cualquier
- cualquier cosa
- dondequiera
- enfoque
- somos
- áreas
- argumento
- en torno a
- AS
- asunción
- At
- evitar
- BE
- se convirtió en
- porque
- esto
- antes
- Bet
- entre
- Big
- más grande
- Mayor
- biología
- Poco
- ambas
- Manojo
- pero
- by
- llamar al
- llegó
- PUEDEN
- Puede conseguir
- case
- cases
- Reubicación
- central
- a ciertos
- oportunidad
- opciones
- Elige
- elegido
- Cities
- Ciudad
- clic
- camarilla
- CAFÉ
- --
- colecciones
- Columna
- combinar
- proviene
- Algunos
- Complicado
- computadora
- Ciencias de la Computación
- condiciones
- conjetura
- Contacto
- conectado
- Conectándote
- Conexiones
- Conectividad
- conecta
- Consecuencias
- en vista de
- consiste
- que no contengo
- contiene
- contraste
- contribuir
- Cost
- podría
- Para crear
- dependencia
- diseño
- destino
- una experiencia diferente
- de reservas
- directamente
- desconectado
- diverso
- do
- sí
- No
- hecho
- No
- dibujar
- Dejar caer
- cada una
- facilidad
- más fácil
- de forma sencilla
- Southern Implants
- eficiencia
- ya sea
- en otra parte
- surgir
- final
- termina
- suficientes
- igual
- especialmente
- esencial
- esencialmente
- Incluso
- Cada
- todo
- ejemplo
- superior
- existe
- existencia
- existente
- existe
- esperado
- Explicar
- explorado
- extremo
- hecho
- false
- famoso
- pocos
- menos
- campo
- Terrenos
- Encuentre
- la búsqueda de
- Nombre
- vuelo
- Vuelos
- siguiendo
- FORCE
- Fuerzas
- formulario
- Formularios
- encontrado
- Digital XNUMXk
- Desde
- General
- en general
- obtener
- conseguir
- Donar
- dado
- da
- Buscar
- En todo el mundo
- objetivo
- va
- gráfica
- gráficos
- Grupo procesos
- garantizamos
- garantia
- garantías
- tenido
- A Mitad
- mano
- encargarse de
- Tienen
- ayuda
- esta página
- mantiene
- Cómo
- Como Hacer
- Sin embargo
- HTTPS
- i
- Identifique
- if
- ilustra
- inmediatamente
- importante
- impuesta
- imposible
- in
- En otra
- inaccesible
- en efecto
- independencia
- independientes
- INSTRUMENTO individual
- información
- interesado
- IT
- SUS
- sí mismo
- solo
- Guardar
- Clave
- Saber
- conocido
- large
- mayores
- mayor
- menos
- izquierda
- Sobrante
- Longitud Mínima
- menos
- Permíteme
- aprovechando
- se encuentra
- Vida
- como
- línea
- pequeño
- local
- localmente
- Logística
- por más tiempo
- Mira
- mirando
- MIRADAS
- Lote
- hecho
- revista
- para lograr
- Realizar
- muchos
- mapa
- las matemáticas
- matemático
- máximas
- Puede..
- personalizado
- significa
- Ed. Media
- podría
- minimizando
- que falta
- momento
- dinero
- más,
- movimiento
- mucho más
- debe
- a saber
- necesariamente
- vecinos
- del sistema,
- telecomunicaciones
- no
- NOMAD
- Aviso..
- ahora
- número
- objetos
- of
- on
- una vez
- ONE
- , solamente
- habiertos
- or
- reconocida por
- Otro
- Otros
- nuestros
- salir
- afuera
- Más de
- par
- pares
- parte
- particular
- camino
- Paul
- pieza
- piezas
- Platón
- Inteligencia de datos de Platón
- PlatónDatos
- más
- punto
- posible
- poderoso
- Predice
- bastante
- probablemente
- Problema
- producir
- propiedades
- Demostrar.
- demostrado
- proporciona un
- rompecabezas
- Revista Quanta
- pregunta
- Preguntas
- en comunicarse
- razón
- recientemente
- referido
- relacionado
- Relaciones
- relativo
- relativamente
- restante
- remove
- la eliminación de
- representa
- exigir
- Requisitos
- Requisitos
- restricción
- restricciones
- resultado
- género
- Derecho
- aproximadamente
- Ruta
- rutas
- Regla
- mismo
- dices
- dice
- Ciencia:
- los científicos
- desplazamiento
- Secreto
- ver
- visto
- segmentos
- seleccionar
- separado
- set
- Sets
- Forma
- compartir
- Mostrar
- sencillos
- desde
- soltero
- SEIS
- Tamaño
- ligeramente diferente
- chica
- menores
- So
- a medida
- algo
- algo
- Fuente
- cuadrado
- estándares de salud
- Estrella
- Estrellas
- comienzo
- Sin embargo
- Detener
- Estrategia
- fuerza
- más fuerte
- estructura
- estudios
- subgrafo
- tal
- Sugiere
- sorprendido
- ¡Prepárate!
- toma
- términos
- que
- esa
- La
- La gráfica
- el mundo
- su
- Les
- sí mismos
- luego
- teoría
- Ahí.
- Estas
- ellos
- cosa
- pensar
- Ideas
- Código
- así
- ¿aunque?
- pensamiento
- miles
- Tres
- A través de esta formación, el personal docente y administrativo de escuelas y universidades estará preparado para manejar los recursos disponibles que derivan de la diversidad cultural de sus estudiantes. Además, un mejor y mayor entendimiento sobre estas diferencias y similitudes culturales permitirá alcanzar los objetivos de inclusión previstos.
- a lo largo de
- Así
- equipo
- veces
- a
- demasiado
- del IRS
- Total
- viajes
- viajado
- verdadero
- try
- se convierte
- dos
- bajo
- comprensión
- hasta
- us
- utilizan el
- usado
- usando
- vulnerabilidad
- quieres
- fue
- Camino..
- we
- webp
- tuvieron
- ¿
- cuando
- sean
- que
- QUIENES
- porque
- seguirá
- palabras
- Actividades:
- rutina de ejercicio
- funciona
- mundo
- se
- daría
- escrito
- si
- flexible
- Usted
- tú
- zephyrnet