Gráfico de Isomorfismo para los no-matemático

Question

Pregunta: ¿Qué es una buena explicación de la Gráfica Isomorfismo problema, que sería comprensible - y espero emocionante a una persona que tiene una mínima exposición a las matemáticas? Tenga en cuenta que no necesito esta aplicación para ser realistas, altamente idealizada de las historias de fantasía son absolutamente bien, siempre y cuando tengan sentido como historias. Estoy específicamente no interesados en las aplicaciones reales de la Gráfica Isomorfismo, a menos que sean atractivos para los no-matemáticos

Ejemplo: Los números de Ramsey problema tiene una muy buena "vida real" como los casos de un partido, en el que algunas personas se conocen entre sí, y otros no. A continuación, se puede demostrar que, asumiendo que existen al menos 6 personas, que a tres de ellos son todos amigos, o algunas otras tres de ellos son todos extraños. Este es, precisamente, la afirmación de que $R(3,3) \geq 6$, pero podría decirse que los laicos prefieren pensar en términos de grupos de amigos en los partidos, pero no tanto en términos de monocromático camarillas en los gráficos.

La interpretación de la Sala del teorema como una declaración acerca de los matrimonios es otro ejemplo del tipo de las que estoy buscando. Tenga en cuenta que estos dos ejemplos son de alguna manera canónica - casi siempre, cuando estos problemas se introdujo por primera vez, una de estas interpretaciones se utiliza (o una ligera variación de los mismos).

Tenga en cuenta también que Smullyan libros para dar lugar más involucrados ejemplos explicando algunas ideas fundamentales de la lógica.

Trabajo hasta el momento: La idea de representar un gráfico como una parte es prometedor. Uno puede representar los vértices como personas y en los bordes de los conocidos. Para introducir el isomorfismo, uno podría tener dos formas independientes de referirse a las personas que por falta de una mejor idea, hacer una máscara de la pelota y, a continuación, se refieren a personas, ya sea por los nombres o los trajes, pero tal vez eso sea muy complicado. Ahora, dados dos descripciones de los dos tipos diferentes, la pregunta es: ¿estas descripciones ser el mismo partido? Pero creo que debe haber una mejor manera...

Motivación: Dado el avance reciente de Babai, sería genial ser capaz de comunicar lo sucedido a los no-matemáticos, como la participación de una manera de lo posible.

Disculpa: no estoy seguro de si esta pregunta encaja en el ámbito de la BMV y si posiblemente es demasiado abiertas. Siéntase libre de votar a cerca de si es necesario. Debido a que algunos otros de los problemas tienen una esencia única de la "vida real" de los modelos, tengo la esperanza de que una respuesta a esta pregunta podría, en principio, existe, y no estar muy de opinión.

P. S. hay una manera de hacer la pregunta CW aquí? Me parece que no puede encontrar, y me gustaría usarlo, si es posible.

Answer 1

No estoy seguro de cuánto valor voy a agregar aquí, pero tal vez este ejemplo será interesante para los niños de la edad moderna. Supongamos que tenemos los siguientes dos gráficos de igual tamaño:

• Gráfico 1: Un grupo de jóvenes con Facebook cuentas. Algunos de los pares de la gente en el grupo somos amigos en Facebook, algunos no lo son.
• Gráfico 2: Una habitación llena de pre-programado de la vieja escuela de paginación dispositivos que no son re-programable. En cada dispositivo de paginación es una lista de contactos de otros dispositivos de búsqueda que se está conectado. Las conexiones son de dos vías, es decir, si el dispositivo $A$ $B$ en sus contactos, a continuación, $B$ también ha $A$ en sus contactos.

Ahora, supongamos que este grupo de jóvenes son todos secuestrado un día y llevado a una isla desierta donde todos se les proporciona comida, agua, refugio y estos dispositivos de búsqueda. Para salvarse de la muerte por los medios de comunicación social inanición, se debe ser capaz de conectarse con todos sus amigos en la isla*. También se debe evitar a toda costa que conecta con los extraños: todos hemos visto el Bagre y el peligro que conlleva.

Los jóvenes son, a continuación, confrontado con el problema de isomorfismo: ¿es posible darle a cada persona en la isla un dispositivo de paginación tal que para cada persona, están conectados a través de pager a su Facebook amigos en la isla, y no a alguien más?

Notas

*Me dice específicamente "amigos en la isla" como opuesto a "Facebook amigos", porque estoy seguro de que la totalidad de Facebook graph es para la mayoría de la parte conectada, y la idea de secuestrar a toda su base de usuarios y llevarlos a una isla desierta parece un poco extrema.

Answer 2

El problema de si existe un trivial gráfico automorphism reduce la gráfica de isomorfismo, y no se sabe que es más fácil. Aquí es una manera en que yo pensaba de explicar el problema:

Empezar con un suministro de hilo y algunos gatos. Cada jack representa algún país en el mundo. Si dos países comparten una frontera, una corbata de esas dos tomas junto con un pedazo de hilo. Ahora tome todo el lío y se mezcla. Se puede averiguar que jack está asociado con qué país? Este es un ejemplo de la gráfica automorphism problema. Si tenemos más de una isla (jack sin hilo adjunto), la respuesta es "no" ya que no podemos decir que jack va con la isla. Pero si los países son Canadá, Estados unidos, México, Guatemala, Belice, El Salvador y, a continuación, la respuesta es "sí" desde el automorphism grupo si este gráfico contiene sólo la identidad. No cada gráfico puede ser incrustado en una esfera de modo que la analogía con los países pueden no reflejar adecuadamente la dureza del problema (pero sin duda podemos construir modelos con el hilo que hacer).

Este Topologist del Mapa de los Estados unidos es otro ejemplo de gráfico de automorphism:

Puede determinar qué polígono que corresponde a una de las $48$ estados contiguos más Lago Michigan? También podemos hacer un gráfico de isomorfismo problema preguntando si hay alguna correspondencia a todos sin necesidad de que sea único.

También puedo tratar de explicar gráfico automorphism en términos de una de las partes. Alguien copete el punzón y todo el mundo se olvidó de su identidad! Pero todo el mundo puede reconocer a sus amigos y el banquete es de estar dispuestos de manera que sólo las personas que se conocen sentarse cerca el uno del otro, y cada uno de los asientos está etiquetada con el nombre del huésped. ¿Todo el mundo puede estar seguro de su identidad después de que todo el mundo encuentra una silla donde conocen a todos sus vecinos? Esto es análogo a la de otro ejemplo, imaginemos que hay seis personas y asientos en las posiciones de los países, cada huésped es un jack y cada amistad es un pedazo de hilo. También existe el mismo problema de que una disposición de los asientos puede ser demasiado restrictivo es un tipo de gráfico para abarcar los más de los casos.

Answer 3

Una muy artificial ejemplo.

Explicar el contexto de la Sala del teorema y de cómo podemos modelar con un bipartito gráfico. Es decir, usted tiene $n$ niños y $n$ de las niñas y saber que a uno le gusta que. Llamar a esto la semejanza gráfica.

Si usted tiene sólo dos personas, a continuación, la situación es bastante simple. Ambos se gustan o no - tiene dos no isomorfos casos $K_2$ $\overline{K_2}.$

Usted puede terminar en la siguiente historia.

Trabaja en una compañía que ayuda a los grupos de personas que se casan. Usted es un consejero por cada grupo que llega construcciones de la semejanza gráfica y los asesora que debe casarse basado en el Hall del teorema.

Puesto que usted quiere ser capaz de evaluar su trabajo también almacenar su selección de pares así como la subyacente bipartito gráfico. Después de un tiempo de llamar a estas parejas para comprobar si su relación todavía está trabajando y realizar un análisis de cómo su asignación trabajado.

Ahora cada vez que un nuevo grupo llega usted puede comprobar si su semejanza gráfica corresponde a cualquier grupo que ya está cubierto y si la asignación intentado trabajado o no. Para ello es necesario hacer uso de isomorfismo de pruebas.

Answer 4

No sé lo mucho que mi respuesta está justificado lo que sea necesario, pero para un no-matemático, en el ejemplo siguiente se puede tirar un poco de atención.

Un grupo de cuatro personas (Angelina, Jessica, Bob y Jonty) que trabajan en una empresa que tiene la amistad gráfico representado en el primer gráfico, donde cada uno de ellos tiene exactamente dos amigos del sexo opuesto. Si la empresa decide enviar el macho empleados en las zonas rurales de la rama, a continuación, cada uno de estos cuatro sufrir el aislamiento de síndrome de down en sus horas de trabajo, tal como se representa en el segundo gráfico.La eficiencia del trabajo de cada uno de ellos sin duda será efectuado, pero no sus amistades. El segundo gráfico se obtiene girando y girando en el primer gráfico, pero manteniendo los bordes intactos es isomorfo a la primera.