Grafos

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA

Ingeniería Técnica En Informática De Gestión

Grafos para la Física Cuántica

Realizado por

María De Miguel Jiménez

Dirigido por

José Ramón Portillo Fernández

Departamento

Matemática Aplicada I

Sevilla, Diciembre 2010

2

3

Índice General

1. Definición de Objetivos ...................................................................................... 7

2. Introducción ......................................................................................................... 9

2.1 El Teorema de Kochen-Specker ........................................................................ 9

2.1.1 La Conjetura de Peres ....................................................................... 10

2.2 Grafos para la Física Cuántica ......................................................................... 10

2.3 nauty ..................................................................................................................... 10

3. Conceptos Básicos ........................................................................................... 13

3.1 El Teorema de Kochen-Specker ...................................................................... 13

3.1.1 Antecedentes ...................................................................................... 13

3.1.2 El Teorema de Kochen-Specker ...................................................... 14

3.2 Grafos ................................................................................................................... 16

3.2.1 ¿Qué son? ........................................................................................... 16

3.2.2 Conceptos Importantes ...................................................................... 16

3.2.2.1 Terminología Básica .......................................................... 16

3.2.2.2 Tipos de Grafos .................................................................. 18

3.3 nauty ..................................................................................................................... 20

3.3.1 Instalación ............................................................................................ 20

3.3.2 Herramientas gtools ........................................................................... 20

3.3.2.1 Herramienta geng ............................................................... 21

3.3.2.2 Herramienta listg ................................................................. 21

3.3.2.3 Herramientas pickg y countg ............................................ 22

3.3.3 Extendiendo nauty .............................................................................. 23

3.3.3.1 Extendiendo geng ............................................................... 23

3.3.3.2 Extendiendo pickg y countg .............................................. 25

4. Análisis de Antecedentes y Aportación Realizada ....................................... 27

4.1 Antecedentes: nauty ........................................................................................... 27

4.2 Aportaciones a nauty .......................................................................................... 27

5. Análisis Temporal y de Coste de Desarrollo.................................................. 29

4

6. Análisis de Requisitos, Diseño e Implementación ........................................ 31

6.1 Requisitos ............................................................................................................ 31

6.2 Diseño e Implementación .................................................................................. 32

7. Algoritmos Desarrollados ................................................................................ 33

7.1 Algoritmos para detectar grafos KS-representables ..................................... 33

7.1.1 Algoritmo para detectar grafos KS-representables con d=5 ........ 34

7.1.2 Algoritmo para detectar grafos KS-representables con d=6 ........ 34

7.1.3 Algoritmo para detectar grafos KS-representables con d=n ........ 35

7.2 Algoritmos para detectar grafos cuyos vértices pertenecen a subgrafos

completos ...................................................................................................................... 36

7.2.1 Algoritmo para grafos con todos sus vértices en un K3 ................ 37




7.2.5 Algoritmo para grafos con todos sus vértices en un Kn ................ 40

7.3 Algoritmos para detectar grafos no KS-coloreables ...................................... 40

7.3.1 Algoritmos para grafos con vértices en subgrafos completos ..... 41

7.3.2 Algoritmos para grafos generales .................................................... 42

7.3.3 Algoritmos para grafos generales con coloración inicial .............. 43

7.3.3.1 Coloración inicial elegida por el usuario ......................... 43

7.3.3.2 Coloración inicial automática de dos vértices ................ 44

8. Pruebas y Conclusiones ................................................................................... 45

8.1 Algoritmos para detectar grafos KS-representables ..................................... 45

8.1.1 KS-representables orden 4 ............................................................... 46



8.1.4 KS-representables orden n ............................................................... 49

8.2 Algoritmos para detectar grafos cuyos vértices pertenecen a subgrafos

completos ...................................................................................................................... 49

8.2.1 Pertenecen a K3 .................................................................................. 50

8.2.2 Pertenecen a K4 .................................................................................. 51

8.2.3 Pertenecen a K5 .................................................................................. 53

8.2.4 Pertenecen a K6 .................................................................................. 54

8.2.5 Pertenecen a Kn .................................................................................. 55

5

8.3 Algoritmos para detectar grafos KS-representables y con todos sus

vértices en subgrafos completos ............................................................................... 56

8.3.1 Orden 3 ................................................................................................ 56

8.3.2 Orden 4 ................................................................................................ 58

8.3.3 Orden 5 ................................................................................................ 59

8.3.4 Orden 6 ................................................................................................ 60

8.3.5 Orden n ................................................................................................ 61

8.4 Algoritmos para detectar grafos no KS-coloreables en grafos KS-

representables y cuyos vértices forman parte de un subgrafo completo ........... 61

8.4.1 Orden 3 ................................................................................................ 62

8.4.2 Orden 4 ................................................................................................ 62

8.4.3 Orden 5 ................................................................................................ 63

8.4.4 Orden 6 ................................................................................................ 63

8.4.5 Orden n ................................................................................................ 64

8.5 Algoritmos para detectar grafos no KS-coloreables en grafos generales . 64

8.5.1 Orden 3 .................................................................................... 65

8.5.2 Orden 4 .................................................................................... 65

8.5.3 Orden 5 .................................................................................... 66

8.5.4 Orden 6 .................................................................................... 66

8.5.5 Orden n .................................................................................... 67

8.6 Algoritmos para detectar grafos no KS-coloreables dada una coloración

inicial .............................................................................................................................. 67

8.6.1 Coloración inicial dada por el usuario ............................................. 67

8.6.1.1 Orden 3 ................................................................................ 67

8.6.1.2 Orden 4 ................................................................................ 67

8.6.1.3 Orden 5 ................................................................................ 68

8.6.1.4 Orden 6 ................................................................................ 68

8.6.1.5 Orden n ................................................................................ 68

8.6.2 Coloración inicial de dos vértices ..................................................... 70

8.6.2.1 Orden 3 ................................................................................ 70

8.6.2.2 Orden 4 ................................................................................ 72

8.6.2.3 Orden 5 ................................................................................ 74

8.6.2.4 Orden 6 ................................................................................ 76

8.6.2.5 Orden n ................................................................................ 77

8.7 Tablas de algoritmos .......................................................................................... 78

6

8.7.1 Grafos KS-representables ................................................................. 78

8.7.2 Subgrafos completos ......................................................................... 78

8.7.3 Unión KS-representables y subgrafos completos ......................... 78

8.7.4 Grafos no KS-coloreables ................................................................. 79

8.7.5 Grafos no KS-coloreables con coloración inicial ........................... 79

9. Desarrollos Futuros .......................................................................................... 81

10. Bibliografía ......................................................................................................... 83

7

1

Definición de Objetivos

El objetivo principal de este proyecto es desarrollar herramientas útiles en el

manejo de grafos derivados de pruebas de Física Cuántica. Más concretamente se desea

implementar algoritmos que puedan servir para probar la conjetura de Peres acerca del

Teorema de Kochen-Specker. Según esta conjetura, dado un sistema preparado

arbitrariamente con menos de dieciocho preguntas es imposible que las respuestas, "sí"

o "no", no estén predefinidas.

Para la demostración de la conjetura de Peres se debe probar que no existe

ningún grafo con menos de dieciocho vértices que verifique para cualquier dimensión d

desde 3 a 17 lo siguiente:

La valencia de cada vértice es al menos d, y cada vértice está contenido en

un grafo completo Kd.

No hay ninguna posible coloración verde-rojo de forma que no existan dos

verdes vecinos y haya un sólo vértice verde en cada Kd.

No contiene ningún subgrafo con d+1 vértices que cumpla como mínimo ser

aristas independientes.

8

9

2

Introducción

2.1 El Teorema de Kochen-Specker

Simon B. Kochen y Ernst Specker formularon en 1967 un teorema según el cual

no es posible interpretar la Física Cuántica a partir de variables ocultas fuera de

contexto.

Básicamente el teorema establece que se produce una contradicción en dos de

los supuestos básicos de las teorías de variables ocultas usados para reproducir los

resultados de la mecánica cuántica. Estos dos supuestos son:

Todas las variables en un sistema de mecánica cuántica tienen un valor definido

en cualquier momento.

Los valores de las variables son independientes de cómo son medidas.

Una demostración del teorema de Kochen-Specker es un conjunto de pruebas

cuya respuesta es "sí" o "no". Estas pruebas, según las reglas de la Mecánica

Cuántica, no pueden tener respuestas predefinidas. La prueba original del teorema

requería 117 preguntas en S2, aunque pruebas posteriores han reducido este número.

Actualmente se ha llegado a conseguir la demostración con 18 preguntas en S3,

prueba que Peres considera la menor posible.

10

2.1.1 La Conjetura de Peres

La conjetura de Peres establece que es imposible encontrar un sistema preparado

arbitrariamente en la mecánica cuántica con menos de 18 preguntas, con respuestas "sí"

o "no", de modo que las respuestas no sean predefinidas.

2.2 Grafos para la Física Cuántica

El uso de grafos para demostrar el teorema de Kochen-Specker se debe a la

analogía directa entre los conceptos de Física Cuántica que conciernen al teorema y

algunos de los conceptos usados en Matemática Discreta y Teoría de Grafos. Así

sabemos que:

Un experimento de Física Cuántica puede representarse como un grafo, y una

pregunta en la que se descompone un experimento puede ser representada como un

vértice de dicho grafo.

Así mismo, si dos vectores de un experimento de Física Cuántica son

ortogonales, pueden representarse en Matemática Discreta como dos vértices adyacentes

entre sí.

Por último, si un experimento es una demostración del teorema de Kochen-

Specker, el grafo que lo representa es KS-coloreable.

Para que un grafo sea KS-coloreable ha de cumplir estas tres condiciones para

todo valor de n mayor o igual que 4:

Ser KS-representable, es decir, no contener ningún subgrafo que sea un


Todo vértice debe tener valencia mínima n, y ha de estar incluido en un Kn.

No puede existir una coloración verde-rojo tal que dos vértices verdes sean

adyacentes y en todo Kn haya un vértice verde.

2.3 nauty

nauty es un paquete de herramientas para el tratamiento de grafos en grandes

cantidades desarrollado por Brendan D. McKay, del departamento de Ciencias de la

Computación de la Universidad Nacional Australiana. Su nombre responde a "no

automorphisms, yes?", ya que está encaminado a determinar el grupo de automorfismos

de un grafo coloreado.

11

Gracias a su alta eficiencia tanto en tiempo de ejecución como en consumo de

memoria nauty nos permitirá generar, analizar y filtrar los grafos que utilizaremos para

resolver nuestro problema.

12

13

3 Conceptos Básicos

3.1 El Teorema de Kochen-Specker

3.1.1 Antecedentes

Para hallar el origen de este teorema debemos remontarnos hasta 1935, cuando

Albert Einstein, Boris Podolsky y Nathan Rosen formulan la Paradoja de Einstein

Podolsky Rosen, conocida como Paradoja EPR.

La Paradoja EPR surge a partir de la idea del entrelazamiento cuántico. El

entrelazamiento cuántico es un fenómeno de la Mecánica Cuántica en el cual los estados

cuánticos de dos o más objetos se pueden describir haciendo uso de los estados

cuánticos de todos los objetos del sistema, incluso si dichos objetos están separados

espacialmente. Dicho de otro modo, es imposible obtener información útil sobre el total

del sistema midiendo sólo una de las partículas, y a su vez, manipulando una de las

partículas se puede modificar el estado total del sistema.

Un ejemplo de entrelazamiento cuántico: es posible enlazar dos partículas en un

solo estado cuántico de manera que al observar una de ellas, si tiene el espín arriba, la

otra siempre tendrá el espín abajo, pese a la imposibilidad de predecir su estado

cuántico según los postulados de la Mecánica Cuántica.

El entrelazamiento cuántico fue planteado al principio como un argumento en

contra de la Mecánica Cuántica, concretamente como una prueba de su incompletitud,

ya que se puede demostrar que las correlaciones predichas por la Mecánica Cuántica

14

son inconsistentes con el principio del realismo local, que dice que cada partícula debe

tener un estado bien definido sin que sea necesario hacer referencia a otros sistemas

distantes.

Los dos conceptos cruciales que critica la Paradoja EPR son la no localidad de

la Mecánica Cuántica (la posibilidad de acción a distancia) y el problema de la

medición. En la física clásica, medir significa revelar o poner de manifiesto propiedades

que estaban en el sistema desde antes de que midamos, pero en Mecánica Cuántica el

proceso de medición altera de forma incontrolada la evolución del sistema, de modo que

cuando medimos ponemos en marcha un proceso que es indeterminable a priori, ya que

habrá distintas probabilidades de medir distintos resultados. Constituye un error pensar

dentro del marco de la Física Cuántica que medir es revelar propiedades que estaban en

el sistema con anterioridad.

En 1964, el físico norirlandés John S. Bell dio un nuevo impulso a este campo

gracias a un refinado análisis de las sutilezas que involucra el entrelazamiento. Bell

propuso una forma matemática para poder verificar la Paradoja EPR, deduciendo unas

desigualdades asumiendo dos hechos: primero, que el proceso de medición en Mecánica

Cuántica obedece a leyes deterministas, y segundo la localidad, es decir, teniendo en

cuenta las críticas de EPR. Si Einstein tenía razón, las desigualdades de Bell son ciertas

y la teoría cuántica es incompleta. Si la teoría cuántica es completa, estas desigualdades

serán violadas.

Desde 1976 en adelante se han llevado a cabo numerosos experimentos, y

absolutamente todos ellos han arrojado como resultado una violación de las

desigualdades de Bell, lo que supone un triunfo para la Teoría Cuántica.

3.1.2 El Teorema de Kochen-Specker

Dentro del contexto anterior, Simon B. Kochen y Ernst Specker formulan, en

1967, el teorema al que dan nombre. Este teorema establece un sólido argumento contra

la posibilidad de interpretar la Física Cuántica a partir de variables ocultas fuera de

contexto (esto es, que si un sistema de Mecánica Cuántica tiene una propiedad, entonces

la tiene independientemente de cualquier tipo de medición que se le haga). Conocido

como el Teorema de KS, complementa la desigualdad de Bell probando que hay una

contradicción entre dos de las suposiciones básicas en las teorías de variables ocultas:

V1 Toda partícula observable tiene valores definidos en cada instante dado.

V2 Los valores de dichas variables son intrínsecos e independientes del dispositivo

usado para medirlas.

15

El Teorema de KS dice:

Sea H un espacio de Hilbert de vectores de Mecánica Cuántica de dimensión x ≥

3. Hay un conjunto M de observables en H, que contienen y elementos, de tal modo que

las dos siguientes suposiciones son contradictorias:

KS1 Todos los y pertenecientes a M tienen valores simultáneamente, por tanto,

pueden asignárseles valores numéricos exactos (que designaremos para las

variables A, B, C, …, como v(A), v(B), v(C), …).

KS2 Los valores de las variables se ajustan a las siguientes condiciones:

a) Si A, B, C son todas compatibles y C = A+B, entonces v(C) = v(A)+v(B).

b) Si A, B, C son todas compatibles y C = A·B, entonces v(C) = v(A)·v(B).

Como puede observarse, KS1 es equivalente a V1. Por su parte, KS2 a) y b) son

las llamadas Regla de la Suma y Regla del Producto, respectivamente.

Una demostración del teorema de Kochen-Specker es un conjunto de pruebas

cuya respuesta es "sí" o "no". Estas pruebas, según las reglas de la Mecánica Cuántica,

no pueden tener asignadas sus respuestas de manera predefinida, ya que el teorema de

KS demuestra que los experimentos no realizados no arrojan resultados.

La prueba original del teorema opera en un espacio de Hilbert tridimensional H3,

y requiere dos cosas: conjuntos de tres rayos ortogonales en H3 y la condición de que

para cada trío ortogonal un rayo tenga asignado un 1 y los otros dos un 0.

KS ilustra la relación de rayos ortogonales mediante grafos, de modo que cada

rayo se representa por un vértice, y vértices adyacentes corresponden a rayos

ortogonales. El problema del coloreado (1-0) queda por tanto trasladado a colorear los

vértices del grafo de manera que no haya dos 1 adyacentes y en cada Kn haya

exactamente un 1.

El récord actual en número de pruebas de KS es de 18 rayos en S3. Según Peres,

ésta es la prueba más simple posible.

Para poder demostrar que Peres está en lo cierto, es necesario generar todos los

grafos de hasta 14 vértices y demostrar que ninguno cumple los requisitos necesarios

para ser una prueba de Kochen-Specker. Los grafos de entre 15 y 17 vértices no son

necesarios, ya que es sabido que por su estructura es imposible que cumplan las

condiciones.

16

3.2 Grafos

3.2.1 ¿Qué son?

Un grafo es una estructura discreta, , donde

es un conjunto de vértices no vacío, y

es un conjunto de aristas, que conectan dos vértices entre sí.

Ilustración 1: Grafo

3.2.2 Conceptos Importantes

3.2.2.1 Terminología Básica

El grado de un grafo es su número de vértices, y se denota por .

Dos vértices de , y , son adyacentes si es una arista de .

Se dice que la arista es incidente con los vértices y si .

El grado o valencia de un vértice es el número de aristas incidentes con él, y se

denota por δ .

Si una arista conecta un vértice consigo mismo recibe el nombre de bucle.

Grafo vacío es aquel que no contiene aristas.

Grafo trivial es aquel que posee un vértice y ninguna arista.

17

Ilustración 2: Grafo Ejemplo

A modo de ejemplo, en la imagen anterior el grado del grafo es , los

vértices 4 y 5 son adyacentes (existe la arista ), la valencia del vértice 4 es

δ y el vértice 3 tiene un bucle.

Un camino es una sucesión de vértices tal que cada uno de ellos es adyacente al

siguiente de la sucesión, es decir, hay una arista que los conecta.

En la siguiente imagen se puede observar un camino señalado en rojo, formado

por los vértices , , , y y las aristas , , y .

Ilustración 3: Camino en Grafo

Un ciclo es un camino que comienza y acaba en el mismo vértice. Un posible

ciclo del grafo anterior es el que recorre las aristas , , y .

18

3.2.2.2 Tipos de Grafos

Un grafo simple es aquel que no posee bucles.

Un subgrafo de un grafo es un grafo tal que y

.

Ilustración 4: Grafo y Subgrafo

Un grafo conexo es todo aquel en el que existe un camino entre cada par de

vértices.

Ilustración 5: Grafo Conexo y Grafo No Conexo

19

Un grafo completo de n vértices, Kn, es un grafo simple en el que cada vértice

del grafo es adyacente a todos los demás vértices del grafo.

A continuación mostramos los grafos completos desde a .

Ilustración 6: K1

Ilustración 7: K2

Ilustración 8: K3

Ilustración 9: K4

Ilustración 10: K5

Ilustración 11: K6

Se dice que un grafo es isomorfo a otro si hay una

función biyectiva de a de tal forma que para cada par de vértices , ∈ , y

son adyacentes si, y sólo si, y son adyacentes en .

En otras palabras, dos grafos son isomorfos si la relación de adyacencia de sus

vértices es equivalente.

Ilustración 12: Grafos Isomorfos

Como se puede observar en la figura, , , , y .

20

3.3 nauty

nauty es un conjunto paquete de herramientas desarrollado por Brendan D.

McKay, del departamento de Ciencias de la Computación de la Universidad Nacional

Australiana. Su nombre responde a "no automorphisms, yes?", y su función principal es

determinar el grupo de automorfismos de un grafo coloreado. La gran utilidad de nauty

radica en que nos permite generar un gran número de grafos distintos, es decir, con la

certeza de que no encontraremos grafos isomorfos en el conjunto.

Escrito en C, nauty resulta altamente portable.

3.3.1 Instalación

Para utilizar nauty se recomienda usar un entorno Unix/Linux. Los pasos a

seguir son:

En primer lugar, descargamos nauty de su web http://cs.anu.edu.au/~bdm/nauty.

A continuación descomprimimos la carpeta descargada, y en consola nos

situamos en ella. Introducimos los comandos ./configure y luego make all, y ya tenemos

todas las herramientas nauty a nuestra disposición.

3.3.2 Herramientas gtools

Dentro del conjunto de utilidades de nauty se encuentra gtools, un conjunto de

herramientas para la generación, el tratamiento y la muestra de grafos. Los grafos

generados por gtools están libres de isomorfismos.

Las funciones básicas de gtools que nos interesan son las siguientes:

geng: genera grafos pequeños

listg: muestra los grafos de varias formas

countg: cuenta grafos que cumplan ciertas propiedades

pickg: selecciona grafos que cumplan ciertas propiedades

21

3.3.2.1 Herramienta geng

geng es una herramienta que nos permite generar todos los grafos de un

determinado tipo, según especifiquemos al ejecutar.

El uso de geng es:

./geng [-cCmtfbd#D#] [-uygsnh] [-lvq] [-x#X#] n [mine[:maxe]] [res/mod] [file]

n número de vértices (1..32). Es el único parámetro obligatorio.

Comentaremos ahora las opciones más interesantes:

-C grafos conexos

-f grafos libres de ciclos de 4 vértices

-d# valencia mínima de los vértices

-D# valencia máxima de los vértices

-u no mostrar los grafos, sólo contarlos

file fichero donde queremos volcar el resultado

Un ejemplo del uso de geng: generar todos los grafos conexos con 9 vértices y

valencia mínima 5, guardando el resultado en un archivo llamado grafos9v.

./geng 9 -Cd5 grafos9v

3.3.2.2 Herramienta listg

listg es una utilidad para mostrar grafos en formato legible para el ojo humano.

El uso de listg es:

./listg [-fp#:#l#o#Ftq] [-a|-A|-c|-d|-e|-M|-s] [infile [outfile]]

Las opciones más útiles para nuestro caso son:

-a mostrar como matrix de adyacencias

-e escribir los grafos como lista de aristas

infile fichero de entrada

outfile fichero donde volcar los grafos

22

Si no especificamos ninguna opción, listg mostrará los grafos como una lista de

adyacencias.

Como ejemplo, veamos la salida de listg dado el siguiente grafo

Ilustración 13: Grafo ejlistg

./listg ejlistg

./listg -a ejlistg

./listg -e ejlistg

0: 1 3 4; 1: 2 3; 2: 1 4; 3: 0 1 4; 4: 0 2 3;

01011 10110 01001 11001 10110

01 03 04 12 13 24 34

3.3.2.3 Herramientas pickg y countg

pickg y countg seleccionan y cuentan, respectivamente, los grafos que les llegan

según sus propiedades.

El uso de pickg (countg es similar) es:

./pickg [-fp#:#q -V] [--keys] [-constraints -v] [ifile [ofile]]

De entre las opciones standard de pickg la única que puede resultarnos

interesante es -v, que devuelve los grafos que no cumples las opciones dadas.

23

3.3.3 Extendiendo nauty

nauty está pensado para ser extendido, por lo que ofrece formas muy sencillas de

añadir nuevas subrutinas. En este proyecto hemos usado las facilidades dadas en geng y

pickg para añadir nuestros algoritmos.

3.3.3.1 Extendiendo geng

Una de las opciones que geng ofrece para llamar funciones hechas por el

usuario, y de la que hemos hecho uso, es PRUNE.

geng llama a PRUNE para cada grafo intermedio y final (grafo intermedio es

aquel que está en construcción y al que por tanto le faltan vértices por añadir). La

función debe tener la siguiente cabecera:

int PRUNE (graph *g, int n, int maxn)

g es el grafo en formato nauty

n es el número de vértices del grafo

maxn es el número de vértices del grafo final

Semejante a PRUNE está la opción PREPRUNE, que puede ser útil para reducir

los tiempos de ejecución en según qué casos.

Para hacer uso de PRUNE debemos crear un archivo nuevo en C con un nombre

diferenciante, por ejemplo archivo1.c, y nuestra función principal ha de llamarse como

hemos explicado antes: int PRUNE (graph *g, int n, int maxn). Respecto a la salida, si

la función devuelve 0 el grafo será mostrado (o continuará siendo tratado si aún no ha

alcanzado maxn), mientras que si devuelve 1 el grafo se descarta.

Una vez hemos creado el nuevo archivo, el siguiente paso es modificar el

archivo makefile.in. En este archivo especificaremos las dependencias y el modo de

compilar nuestro nuevo programa, de modo que podremos crear su ejecutable. En las

primeras líneas de makefile.in, buscamos lo siguiente:

gtools : copyg listg labelg dretog amtog geng complg shortg showg NRswitchg \

biplabg addedgeg deledgeg countg pickg genrang newedgeg catg genbg directg \

multig;

Es al final de estas líneas donde debemos añadir el nombre de nuestro archivo,

del siguiente modo:

24



multig archivo1;

Finalmente, añadimos la compilación para crear nuestro ejecutable:

archivo1 : geng.c archivo1.c gtools.o nauty1.o nautil1.o

${CC} -o archivo1 ${CFLAGS} ${USERFLAGS} archivo1 geng.c archivo1.c gtools.o \

nauty1.o nautil1.o naugraph1.o

Tras estos pasos, nos queda reconfigurar nauty para poder hacer uso de nuestro

programa, por lo que en consola introducimos los comandos ./configure y make all. Ya

podemos llamar a nuestro nuevo programa, de modo similar a como llamamos a geng:

./archivo1 9 -Cd5

Un caso especial a la hora de extender geng es cuando deseamos introducir más

de un parámetro por la línea de comandos, como en el caso de los algoritmos de orden

general. Un ejemplo de lo que se desea conseguir:

./archivo2 9 5 -Cd5

Para lograr esto, se ha creado una copia de geng, llamada wggeng, donde se ha

introducido un nuevo parámetro, al que hemos llamado wd, de tal modo que si no se

proporciona al llamar al algoritmo correspondiente, éste avisa de que se ha producido un

error porque falta dicho argumento.

Ya que el objetivo no es ejecutar wggeng por sí mismo (no tendría sentido), sino

haciendo uso de programas externos que lo usen, no añadimos wggeng a la lista de

ejecutables de gtools, pero sí nuestro programa:



multig archivo1 archivo2;

Y para compilar el ejecutable:

archivo2 : wggeng.c archivo2.c gtools.o nauty1.o nautil1.o

${CC} -o archivo2 ${CFLAGS} ${USERFLAGS} archivo2 wggeng.c archivo2.c

gtools.o \

nauty1.o nautil1.o naugraph1.o

Como puede observarse, el único cambio consiste en introducir wggeng donde

antes estaba geng.

25

Por último, para hacer uso de esta nueva posibilidad, nuestro programa debe

tener la siguiente cabecera:

int PRUNE (graph *g, int n, int maxn, int wd)

Con esto, ya estamos en disposición de hacer uso de un nuevo parámetro de

entrada desde la línea de comandos.

3.3.3.2 Extendiendo pickg y countg

pickg es fácilmente ampliable para crear nuevas restricciones según las cuales

seleccionar los grafos de entrada. Cabe aclarar ahora que pickg y countg usan el mismo

fichero como fuente, por lo que una modificación de ese fichero afectará a ambos por

igual. El archivo en cuestión es testg.c, y en su propia descripción se especifica cómo

añadir nuevas restricciones. Lo explicamos a continuación:

En primer lugar, encontrar una letra libre para darle nombre a nuestra opción.

Por ejemplo, usaremos -O. Buscamos el array de propiedades, constraint[], y añadimos

una nueva línea para nuestro algoritmo:

#define I_O N

{'O',0,FALSE,FALSE,0,-NOLIMIT,NOLIMIT,"funcion1 ",BOOLTYPE,0}

N es un número correlativo, su valor depende de la última propiedad definida en

constraint[] antes de Q.

funcion1 es el nombre de nuestra función

BOOLTYPE es el tipo de la salida de la función, para tratarla después. Puede

ser también INTTYPE, GROUPSIZE o INTVECTOR.

A continuación, se añade la nueva opción a compute(), aquí es donde

especificamos qué función llamará nuestra nueva opción:

case I_O:

VAL(I_O) = funcion1(g,m,n);

COMPUTED(I_O) = TRUE;

break;

En VAL(I_O) se almacena el valor devuelto por la función.

Por último, queda añadir nuestra función, lo que haremos tras compute(). La

cabecera básica es:

int funcion1 (graph *g, int m, int n)

26

Para poder aplicar nuestra nueva condición, -O, primero debemos rehacer pickg

mediante make pickg (si queremos también countg, deberemos hacer make countg, o de

manera más general make all, que sólo rehará aquellos ejecutables cuyos ficheros fuente

hayan sido modificados). La llamada a nuestra nueva opción quedaría:

./pickg -O [ifile[ofile]]

Por último, advertir de que pickg actúa al contrario que geng, es decir, si la

función devuelve 0 el grafo es descartado, mientras que si devuelve 1 será tenido en

cuenta.

27

4

Análisis de Antecedentes y Aportación Realizada

4.1 Antecedentes: nauty

nauty es un paquete de herramientas para el tratamiento de grafos en grandes

cantidades desarrollado por Brendan D. McKay, del departamento de Ciencias de la

Computación de la Universidad Nacional Australiana.

De entre todas las herramientas a nuestro alcance para la manipulación de

grafos, nauty es sin duda la que mayor eficiencia consigue tanto en tiempo de ejecución

como en consumo de memoria, y esto por lo que se ha escogido.

Este proyecto se basa en ampliar los algoritmos desarrollados en nauty para

obtener nuevos programas útiles para el tratamiento de grafos en el campo de la física

cuántica.

4.2 Aportaciones a nauty

La aportación realizada puede dividirse en tres grupos: algoritmos para detectar

grafos KS-representables, algoritmos para detectar grafos con todos sus vértices en

subgrafos completos, y algoritmos para encontrar grafos no KS-coloreables, divididos a

su vez en tres bloques: algoritmos para encontrar grafos no KS-coloreables con todos

28

sus vértices en subgrafos completos, algoritmos para encontrar grafos no KS-

coloreables generales y algoritmos para encontrar grafos no KS-coloreables dada una

coloración inicial de vértices. Todos estos algoritmos están desarrollados para orden

entre 3 y 6, además de un algoritmo general para cualquier orden.

El primer grupo de algoritmos, los que hallan grafos KS-representables, está

desarrollado usando las posibilidades de geng, el segundo grupo está implementado

tanto con geng como con pickg, mientras que el último bloque sólo está desarrollado en

pickg.

Además de esto, se ha implementado un algoritmo que une el primer y segundo

grupo, con lo que también disponemos de herramientas para generar todos aquellos

grafos KS-representables de orden n (entre 3 y 6) y que además tengan todos sus

vértices en un subgrafo completo del mismo orden n.

Para un estudio en mayor profundidad de cada uno de los algoritmos

desarrollados remitimos al lector a las secciones 7 y 8, donde se describe cada programa

y se muestran las pertinentes pruebas de cada uno de ellos.

29

5 Análisis Temporal y de Coste de

Desarrollo

El desarrollo de este proyecto ha constado de las siguientes fases:

Documentación, estudio de antecedentes y recopilación de información: en esta

fase se han invertido las dos primeras semanas de desarrollo, aunque el estudio y

la recopilación de nuevos documentos ha sido una constante a lo largo de todo el

tiempo dedicado al proyecto.

Desarrollo de algoritmos: esta tarea es la que más tiempo ha requerido, seis

semanas de generación de código en las que se buscaban resultados

semanalmente.

Pruebas y conclusiones: las pruebas se han ido realizando paralelamente a la

fase anterior, lo que también ha ayudado a detectar y corregir errores. El estudio

de los resultados obtenidos ha sido también por tanto una tarea que se ha

prolongado durante todo el desarrollo del código.

30

Creación de la memoria: el presente documento se ha ido redactando en su

mayoría al tiempo que el desarrollo de los algoritmos, dedicándole una especial

dedicación durante las dos últimas semanas de realización del proyecto.

En total, el tiempo invertido ha sido de diez semanas, con una dedicación

exclusiva al desarrollo del proyecto.

Respecto al coste de desarrollo, se ha trabajado en plataformas de software libre

y haciendo uso de nauty, de libre distribución.

31

6 Análisis de Requisitos, Diseño e

Implementación

6.1 Requisitos

Nuestro proyecto está encaminado a proporcionar herramientas útiles para el

manejo de grafos en la resolución de problemas físicos. Más concretamente, se desean

programas que puedan ayudar en la demostración de la conjetura de Peres.

La conjetura de Peres exige tres condiciones en nuestros grafos:

Ser KS-representable, es decir, no contener ningún subgrafo que sea un


Todo vértice debe tener valencia mínima n, y ha de estar incluido en un Kn.



Además de los algoritmos para hallar grafos que cumplan las condiciones

anteriores, también se nos pide desarrollar programas para encontrar coloración verde-

rojo dada una coloración inicial de los vértices, y programas para buscar parejas de

vértices que en un grafo estén relacionados de tal modo que si uno de ellos es verde el

otro deba ser rojo forzosamente para que haya una coloración como la expuesta en el

punto tres.

32

6.2 Diseño e Implementación

A la hora de trabajar con grafos nos hemos decantado por usar nauty, un paquete

de herramientas escrito en C altamente eficiente en la generación y tratamiento de

grafos.

Dado el gran volumen de grafos con los que tenemos que lidiar la rapidez en los

cálculos resulta esencial, y es en velocidad de procesamiento de datos en lo que nauty

precisamente destaca, lo que nos resultará inmensamente útil.

Además de esto, las facilidades que nauty ofrece para su extensión y

modificación lo aventajan sin duda ante cualquier otro generador de grafos. El único

"pero" posible a nauty es su interfaz, inexistente. El trabajo con nauty ha de hacerse por

completo en consola, lo que visualmente puede desmerecerlo, pero en nuestro caso no

nos afecta ya que buscamos grafos de hasta 17 vértices, cuya representación puede

resultar considerablemente confusa al ojo humano.

33

7 Algoritmos Desarrollados

7.1 Algoritmos para detectar grafos KS-representables

En esta sección explicaremos los algoritmos desarrollados para la detección de

grafos KS-representables.

Un grafo es KS-representable si no contiene ningún subgrafo tal que para una

dimensión d, cumple ser

aristas independientes, es decir, un subgrafo que si

se le añadieran

aristas sería un . También es posible expresarlo como un

subgrafo formado por un C4 con el resto de vértices dentro (hasta completar d+1) y

conectados entre sí quitando

aristas disjuntas.

Por ejemplo, para d=4 tendríamos

, es decir, aristas

independientes.

Ilustración 14:

34

7.1.1 Algoritmo para detectar grafos KS-representables con d=5

Un grafo no KS-representable con d=5 es

, es decir, aristas

independientes.

Ilustración 15:

El algoritmo para hallar estos grafos consta de los siguientes pasos:

Dado un grafo con n vértices, numerados desde 0 a n-1.

1. Tomamos el vértice n-1 y recorremos el resto del grafo buscando un vecino, v,

desde n-2 hasta 3 (inclusive). Si llegados al vértice número 3 no es vecino

podemos concluir que n-1 no forma parte de un subgrafo no KS-representable

(como se ve en la figura, para que un vértice esté contenido en el subgrafo debe

tener al menos cuatro vecinos válidos).

2. Una vez encontrado un v vecino a n-1, buscamos dos vértices adyacentes a

ambos, que llamaremos u y w (de no haber, pasaríamos al siguiente v).

3. Buscamos un vértice, z, que sea vecino de n-1, u y w (y que no sea v).

4. Si existe z, buscamos un vértice adyacente a v, u, w, y z (excluyendo n-1). Si ese

vértice existe, hemos hallado el subgrafo no KS-representable.

7.1.2 Algoritmo para detectar grafos KS-representables con d=6

Un grafo no KS-representable con d=6 es

, es decir, aristas

independientes.

Ilustración 16:

35

El algoritmo para hallar estos grafos consta de los siguientes pasos:

Dado un grafo con n vértices, numerados desde 0 a n-1.

1. Tomamos el vértice n-1 y recorremos el resto del grafo buscando un vecino,

v, desde n-2 hasta 4 (inclusive). Si llegados al vértice número 4 no es vecino

podemos concluir que n-1 no forma el subgrafo no deseado (como se ve en

la figura, para que un vértice esté contenido en el subgrafo debe tener al

menos cinco vecinos válidos).

2. Una vez encontrado un v vecino a n-1, buscamos dos vértices adyacentes a

ambos, que llamaremos u y w.

3. Si u y w son adyacentes entre sí, buscamos un tercer vecino a n-1 y v, que

llamaremos z.

4. Si w y z son vecinos, buscamos vecinos comunes entre u, w, z y n-1

(excluyendo a v, que ya sabemos es vecino de todos ellos). Llamaremos C1

al conjunto de vecinos.

5.a Si hay vértices en C1, buscamos los vecinos comunes a u, w, z y v

(excluyendo de este conjunto a n-1). Llamaremos C2 a este conjunto.

5.a.1 Si hay vértices en C2, y alguno de los vértices de C1 es adyacente a

alguno de los vértices de C2, el grafo no es KS-representable.

5.a.2 Si no hay vértices en C2 significa que n-1 es el vértice vecino a todos

los demás del subgrafo, y que hay un vecino más a n-1 y v, que

llamaremos x. Si x tiene algún vecino en C1 y además es adyacente a

u y a z, hemos encontrado un grafo no KS-representable.

5.b Si no hay vértices en C1, buscamos los vecinos comunes a u, w, z y v

(excluyendo a n-1). Llamaremos C2 a este conjunto.

5.b.1 Si hay vértices en C2 significa que v es el vértice vecino a todos los

demás del subgrafo, y que hay un vecino más a n-1 y v, que

llamaremos x. Si x tiene algún vecino en C2 y es además vecino de u

y de z, el grafo es no KS-representable.

7.1.3 Algoritmo para detectar grafos KS-representables con d=n

En primer lugar, y para entender mejor el desarrollo de este algoritmo,

cambiaremos el modo de visualizar los subgrafos prohibidos.

36

Los grafos anteriores son isomorfos, y representan un

. Para representar

, tan sólo necesitamos añadir un vértice más adyacente a todos los anteriores:

El algoritmo para hallar grafos no KS-representables para cualquier d se basa en

encontrar primero cuatro vértices (los vértices 1, 2, 4 y 5 de la imagen, por ejemplo) del

siguiente modo:

1. Se toma un vértice, n-1, y se busca un vecino a él, v. Aquí hay que considerar las

diferencias entre tener d par o impar. Si d es impar (y por tanto el número de

vértices en el grafo es par) el grafo resultante es simétrico, y cada vértice debe

tener d-1 vecinos que me sirvan, por lo que v irá de n-2 a d-2. En el caso de que

d sea par v tiene que ir hasta d-3, ya que el vértice adyacente a todos no nos

sirve al inicio del algoritmo.

2. Se toman dos vértices, u vecino a n-1 y w vecino a v, y que además sean vecinos

entre sí. Hacemos p= d-3.

3. Llamamos C1 al conjunto formado por los vecinos comunes de n-1, v, u y w.

4. Si en C1 hay al menos p vértices y mientras p>0, se coge uno de esos vecinos.

4.1 Si d es par y p=1, hemos encontrado el subgrafo prohibido.

4.2 Si no, se toma otro vecino, y se actualiza C1 descartando aquellos

vértices que no sean vecinos de los dos últimos. Si el número de vértices

en C1 es mayor o igual que p-2, decremento p dos unidades. Si p=0,

hemos hallado el subgrafo.

7.2 Algoritmos para detectar grafos cuyos vértices pertenecen

a subgrafos completos

En esta sección se expondrán los algoritmos desarrollados para la selección de

aquellos grafos cuyos vértices estén todos contenidos en un grafo completo de un orden

n dado.

37

7.2.1 Algoritmo para grafos con todos sus vértices en un K3

Ilustración 17: Grafo con todos sus vértices en K3

El algoritmo para hallar grafos cuyos vértices estén todos contenidos en un grafo

completo de orden 3 consta de los siguientes pasos:

1. Se inicializa un conjunto, vacío, C.

2. Se toma un vértice, v, que no esté en C. Si su valencia es menor de 2, el grafo no

es válido y se termina.

3. Para cada vecino de v, u, si tiene vecinos comunes con v, almaceno v, u y los

vecinos comunes en C. Si no quedan vecinos de v y v está contenido en C se va

al paso 2. Si v no está en C, el grafo no es válido.

4. Si C contiene todos los vértices del grafo, se cumple que todos los vértices

forman parte de un K3 y se termina. Si no, se va al paso 2 hasta comprobar todos

los vértices del grafo.



38

El algoritmo para hallar grafos cuyos vértices estén todos contenidos en un grafo

completo de orden 4 es muy similar al anterior, y consta de los siguientes pasos:


2. Se toma un vértice del grafo, v, que no esté en C. Si su valencia es menor de 3,

el grafo no es válido y se termina.

3. Para cada vecino de v, u, si tiene 2 o más vecinos comunes con v, se almacenan

los vecinos comunes en un conjunto, A. Si no quedan vecinos de v y v está

contenido en C se va al paso 2. Si v no está en C, el grafo no es válido.

4. Para cada vértice en A se comprueba si tiene 1 o más vecinos en común con v y

u. De ser así, se almacenan todos estos vértices en C.

4.1 Si C contiene todos los vértices del grafo, se cumple que todos los

vértices forman parte de un K4 y se termina. Si no, se va al paso 4 hasta

comprobar todos los vértices en A.

4.2 Si no quedan vértices en A, se va al paso 3.



De nuevo, este algoritmo es similar al anterior, salvo por el número de pasos:







4. Para cada vértice w en A se comprueba si tiene 2 o más vecinos en común con v

y u. De ser así, se almacenan los vecinos comunes en un conjunto, B.

39

5. Para cada vértice en B, si tiene 1 o más vecinos en común con v, u, y w, se

toman todos estos vértices y se almacenan en C.

5.1 Si C contiene todos los vértices del grafo, se cumple que todos los vértices

forman parte de un K5 y se termina.

5.2 Si no, se va al paso 4 hasta comprobar todos los vértices de A.



Similar al anterior, este algoritmo añade algunos pasos:







4. Para cada vértice w en A se comprueba si tiene 3 o más vecinos en común con v

y u. De ser así, se almacenan los vecinos comunes en un conjunto, B.

5. Para cada vértice x en B, si tiene 2 o más vecinos en común con v, u, y w, se

toman los vecinos comunes y se almacenan en D.

6. Para cada vértice de D se comprueba si tiene 1 o más vecinos en común con v, u,

w y x. De ser así, se almacenan todos en C.

6.1 Si C contiene todos los vértices del grafo, se cumple que todos los

vértices forman parte de un K6 y se termina.

6.2 Si no, se va al paso 5 hasta comprobar todos los vértices de B.

40

7.2.5 Algoritmo para grafos con todos sus vértices en un Kn

Los pasos seguidos en este algoritmo son los siguientes:

Dado n:

1. Se crean dos arrays, A, y B, para listas de adyacencias y vértices

respectivamente, y un número b. También se inicializan dos conjuntos C y D de

vértices.

2. Se toma un vértice v del grafo, que no esté en C. Si su valencia es menor que n,

el grafo no es válido y se termina. Se inicializan b a 1, A[b] con los adyacentes a

v y B[b] con v y D con v.

3. Mientras b sea mayor que 0 y menor o igual a n:

3.1 Si hay vértices en A[b], mientras haya y b sea menor o igual a n:

3.1.1 Se toma un vértice, u, de A[b]. Si tiene adyacentes suficientes

comunes con v, se incrementa b y en A[b] se guardan los vértices

comunes a u y al vértice en B[b-1]. En B[b] y en D se guarda u.

3.1.2 Si hay en D n vértices, se vuelca el contenido de D en C

(respetando, si había, los vértices en C), se vacía D y se hace b 0.

3.2 Si no hay vértices en A[b], se borra B[b], se decrementa b y se vuelve al

paso 2.

4. Si al finalizar el recorrido por los vértices del grafo hay en C tantos vértices

como vértices tenía el grafo, se cumple la condición.

7.3 Algoritmos para detectar grafos no KS-coloreables

En esta sección se expondrán los algoritmos desarrollados para la selección de

aquellos grafos que cumplan la siguiente condición:



Se han desarrollado algoritmos para orden 3, 4, 5, 6 y para orden general n.

Dado que todos ellos siguen una misma estructura, sin cambios significativos excepto

los derivados del orden de los Kn, explicaremos sólo los algoritmos para n=3.

En primer lugar, expondremos los algoritmos para grafos en los que tenemos la

certeza de que todos sus vértices se encuentran en un grafo completo de orden n Kn.

A continuación están los algoritmos para grafos generales, es decir, cuyos

vértices pueden estar, o no, en un Kn, para un n dado.

41

Finalmente, como variante de éstos últimos, se encuentran los algoritmos para

detectar si una coloración inicial de uno o varios vértices de un grafo es posible o por el

contrario no hay modo de colorear dicho grafo partiendo de esa coloración inicial.

7.3.1 Algoritmos para grafos con vértices en subgrafos completos

Ilustración 21: Grafo coloreable orden 3

Los pasos a seguir en este algoritmo son:

1. Se buscan y almacenan todos los triángulos (K3) del grafo en

triangulo[numT][3].

2. Creamos seis arrays, color[n] para guardar el estado de los colores de los

vértices, visitado[numT] para guardar los triángulos visitados, oc[n][n] para

almacenar los colores de los vértices, l[numT][numT] para almacenar el estado

de los triángulos, lvlI[numT] para determinar el nivel del triángulo en el que nos

encontramos y lt[numT] para almacenar el triángulo del nivel en el que estamos.

3. Inicializamos color[], lvlI[] y visitado[] a indeterminado (4 en dimensión 3, 5 en

dimensión 4, 6 en dimensión 5 y 7 en dimensión 6), 0 y 0, respectivamente.

Creamos una variable, lvl, y otra, tn, que toman también valor 0.

4. Iteramos sobre los triángulos, mientras tn sea menor que numT:

4.1 Si visitado[tn] es 0, es decir, el triángulo no ha sido visitado:

4.1.1 Doy por visitado el triángulo tn, hago lt[lvl]=tn, almaceno los

estados de color[] y visitado[].

4.1.2 Miramos ahora el nivel lvlI[] de nuestro triángulo.

Si es menor que 3, es decir, no hemos recorrido todos los

vértices que lo componen, busco un vértice no coloreado

en él.

Si no, retrocedo de nivel y vuelvo al triángulo anterior, y

en caso de llegar hasta el primero, acabo porque no es

posible colorear el grafo.

4.1.3 Hago verde el vértice seleccionado, y todos sus adyacentes los

hago rojos.

42

4.1.4 Recorro ahora la lista de triángulos, triangulo[][], y si no ha sido

ya visitado lo compruebo.

Si hay tres rojos y estoy en el último vértice del primer

triángulo, no es posible colorear.

Si hay tres rojos y estoy en el último vértice del triángulo,

o si mi triángulo se ha creado a partir de dos rojos, vuelvo

al triángulo anterior y voy a 4.1.1.

Si hay tres rojos y el triángulo actual fue elegido al azar,

vuelvo a 4.1.1 y paso al siguiente vértice del triángulo.

Si hay dos rojos y uno verde, dos por visitado el triángulo

que estoy comprobando.

4.1.5 A continuación, aumento lvl, ya que mi triángulo actual ha

superado las restricciones, y busco si algún triángulo de

triangulo[][] tiene dos vértices rojos y uno sin color, y de ser así

lo tomo mi triángulo actual y voy a 4.1.

4.2 Si el triángulo ya ha sido visitado, busco entre todos los triángulos,

empezando en el 0, el primer no visitado, y voy a 4.1.

4.3 Si no quedan triángulos por visitar, acabo: el grafo es coloreable.

7.3.2 Algoritmos para grafos generales

Ilustración 22: Grafo coloreable

Como se observa en la imagen, los grafos que tratamos ahora pueden tener

vértices que no estén en ningún grafo completo, como es el caso del vértice 1. A

consecuencia de esto, el algoritmo de coloreado deberá iterar ahora sobre vértices y no

sobre grafos completos, del siguiente modo:

1. Se buscan y almacenan todos los triángulos (K3) del grafo en

triangulo[numT][3].

2. Creamos seis arrays, color[n] para guardar el estado de los colores de los

vértices, visitado[numT] para guardar los triángulos visitados, oc[n][n] para

guardar los colores de los vértices, l[n][numT] para almacenar el estado de los

43

triángulos, lvlI[n] para determinar el vértice de cada nivel y lt[n] para almacenar

el número de vértices visitados en un nivel.

3. Inicializamos color[], lvlI[], lt[] y visitado[] a dimensión más uno el primero y 0

los restantes. Creamos una variable, lvl, y otra, ni, que toman también valor 0.

4. Iteramos sobre los vértices, mientras ni sea menor que n:

4.1 Si color[ni] es indeterminado, es decir, el vértice no ha sido coloreado:

4.1.1 Almaceno los estados de color[] y visitado[], hacemos

lvlI[lvl]=ni, ni pasa a ser verde y almacenamos en lt[lvl] el

número de vétices coloreados.

4.1.2 Si hay triángulos en el grafo, recorro ahora la lista de triángulos,

triangulo[][], y si no ha sido ya visitado lo compruebo.

Si hay tres rojos y ya he comprobado todos los vértices

(lt[lvl] es n y lvl=0), no es posible colorear.

Si hay tres rojos y vengo de un triángulo inducido o si ya

he recorrido todos los vértices (lt[lvl] es n y lvl es mayor

de 0), vuelvo al vértice anterior y voy a 4.

En cualquier otro caso, de haber tres rojos hago rojo el

vértice actual y paso a otro vértice.

Si hay dos rojos y un verde, doy como visitado ese

triángulo.

4.1.3 A continuación, aumento lvl, ya que mi triángulo actual ha

superado las restricciones, y busco si algún triángulo de

triangulo[][] tiene dos vértices rojos y uno sin color, y de ser así

guardo el vértice incoloro en ni y voy a 4.1.

4.2 Si el vértice ya ha sido visitado, busco entre todos los vértices,

empezando en el 0, el primero no visitado, lo almaceno en ni y voy a 4.

4.3 Si no quedan vértices por visitar, acabo: el grafo es coloreable.

7.3.3 Algoritmos para grafos generales con coloración inicial

7.3.3.1 Coloración inicial elegida por el usuario

En este caso el algoritmo es exactamente igual al anterior, salvo que en el paso 3

color[] se inicializa con los colores iniciales que tiene el grafo, almacenados en un

archivo de texto que el usuario puede modificar a su conveniencia, y a continuación se

recorren todos los vértices buscando verdes. Si se encuentra algún vértice verde todos

sus vecinos pasan a ser rojos, y estos colores quedan inamovibles durante todo el

algoritmo.

44

7.3.3.2 Coloración inicial automática de dos vértices

De nuevo, el algoritmo principal es igual al descrito en 7.3.2, salvo que la

coloración inicial es automática, y se comprueban dos vértices no vecinos de tal modo

que si al ser verde el primero obliga al segundo a ser rojo para que exista coloración

verde-rojo, se devuelve el grafo. Este fenómeno es conocido como YIN (Yes Implies

No) y tiene utilidad por sí mismo, no sólo en el campo de la física cuántica.

El problema planteado se soluciona haciendo dos llamadas al algoritmo en 7.3.2,

la primera con coloración inicial de los vértices verde - rojo, y la segunda verde - verde.

Si se encuentra coloración para el primer caso pero no para el segundo, se devuelve el

grafo y se imprime en pantalla la primera pareja de vértices en conflicto, sin importar si

hay más.

45

8 Pruebas y Conclusiones

En esta sección se muestran los resultados de la ejecución de los algoritmos

antes expuestos y las órdenes para cada uno de ellos.

Todas las pruebas presentadas a continuación se han realizado en una máquina

virtual con una distribución Ubuntu, bajo Windows 7. Las características de la máquina

son:

Procesador: Intel Core 2 Quad Q8300 @ 2'50 GHz

Memoria RAM: 4'00 Gb

Al final de este capítulo se ofrece una tabla con todos los algoritmos y su modo

de ejecutarlos.

8.1 Algoritmos para detectar grafos KS-representables

A continuación presentamos los resultados obtenidos en las pruebas de los

algoritmos desarrollados para detectar grafos KS-representables. Se ofrecen los

resultados para orden d 4, 5 y 6, además de completar con los tiempos de ejecución del

algoritmo de carácter general para cualquier orden. En el caso de d=3 los subgrafos

prohibidos son ciclos de cuatro vértices, lo que se consigue con la opción -f de geng,

que genera grafos sin dichos ciclos, y por tanto no hemos incluido esos resultados.

46

Estos algoritmos han sido desarrollados sirviéndonos de las facilidades para

extender geng, creando archivos independientes para cada uno de ellos. Todas las

pruebas están repetidas con el fin de comprobar qué opción entre PRUNE y

PREPRUNE da mejor resultado.

Recordamos ahora que para que un grafo sea KS-representable debe cumplir la

siguiente restricción:



A fin de reducir el número de grafos resultantes hemos también impuesto la

condición de que la valencia de cada vértice sea al menos d, como requiere la primera

condición de Peres:



8.1.1 KS-representables orden 4

El nombre del ejecutable para orden 4 es w4free, creado a partir del código en

w4free.c, y para ejecutarlo debemos escribir

./w4free n -Cd4

Donde n es el número de vértices y d4 es la restricción en la valencia mínima de

cada vértice.

En la siguiente tabla podemos observar los resultados obtenidos con la opción

PRUNE.

w4free.c - wgfree.c

Vértices Valencia Mínima Nº de Grafos

Tiempo de

Ejecución (s)

w4free - wgfree

8 4 27 0'00 - 0'00

9 4 423 0'02 - 0'02

10 4 19987 0'54 - 0'98

11 4 1599138 36'17 - 80'46

12 4 190092204 4561'07 - 12056'12

Como es lógico, los tiempos de wgfree son considerablemente mayores que los

de w4free. Este comportamiento lo observaremos en todas las pruebas posteriores.

47

Respecto a los tiempos en sí, a mayor número de vértices se disparan.

Los tiempos resultantes con PREPRUNE son:

w4free.c - wgfree.c


Tiempo de

Ejecución (s)

w4free - wgfree

8 4 27 0'00 - 0'00

9 4 423 0'01 - 0'02

10 4 19987 0'20 - 0'73

11 4 1599138 11'48 - 64'09

12 4 190092204 1245'94 - 9305'17

Claramente estos tiempos son mucho menores que los obtenidos con PRUNE, y

resulta por tanto recomendable usar PREPRUNE a la hora de ejecutar w4free.


El nombre del ejecutable para d=5 es w5free (código en w5free.c), y la orden es

./w5free n -Cd5

Donde n es el número de vértices y d5 significa que la valencia mínima de cada

vértice es 5.


PRUNE.

w5free.c - wgfree.c


Tiempo de

Ejecución (s)

w5free - wgfree

8 5 8 0'00 - 0'00

9 5 204 0'00 - 0'00

10 5 19826 0'20 - 0'27

11 5 4084233 27'14 - 41'38

12 5 1344947026 8295'61 - 13773'87

De nuevo observamos que los tiempos de wgfree son considerablemente

mayores (un 166% mayores en el caso de 12 vértices). También es curioso ver cómo a

partir de 11 vértices el número de grafos resultantes supera a los grafos obtenidos con

48

w4free, mientras que con menor número de vértices se obtenían también menos grafos

en la salida.

A continuación, los tiempos con PREPRUNE.

w5free.c - wgfree.c


Tiempo de

Ejecución (s)

w5free - wgfree

8 5 8 0'00 - 0'00

9 5 204 0'00 - 0'00

10 5 19826 0'13 - 0'23

11 5 4084233 16'60 - 39'65

12 5 1344947026 4516'56 - 13650'46

En este caso cabe destacar cómo los tiempos se reducen casi en un 50% en el

caso de w5free, y sin embargo apenas disminuyen para wgfree.


El archivo que contiene el código para d=6 es w6free.c, y la orden es

./w6free n -Cd6

Donde n es el número de vértices y d6 la valencia mínima de cada uno de ellos.


PRUNE.

w6free.c - wgfree.c


Tiempo de

Ejecución (s)

w6free - wgfree

8 6 0 0'00 - 0'00

9 6 24 0'00 - 0'00

10 6 1604 0'03 - 0'05

11 6 479220 4'19 - 10'26

12 6 296653750 2513'04 - 7051'44

Los tiempos de ejecución de w6free y wgfree son mucho menores que en los

casos anteriores, que podemos achacar a la reducción del número de grafos debida a la

restricción en la valencia mínima. Como se observa en la tabla, para 8 vértices no hay

grafos resultantes.

49

La tabla con los resultados de PREPRUNE.

w6free.c - wgfree.c


Tiempo de

Ejecución (s)

w6free - wgfree

8 6 0 0'00 - 0'00

9 6 24 0'00 - 0'00

10 6 1604 0'03 - 0'06

11 6 479220 4'87 - 15'78

12 6 296653750 3246'63 - 11368'17

En este caso se da un fenómeno curioso. Mientras que en todos los anteriores la

opción PREPRUNE mejoraba los tiempos de ejecución, llegados a dimensión 6 esta

opción los empeora sensiblemente.

8.1.4 KS-representables orden n

El archivo que contiene el código para d=n es wgfree.c, y la orden es

./wgfree n o -Cdo

Donde n es el número de vértices y o el orden que deseamos en el grafo KS-

representable.

Aun cuando este programa nos permite obtener los grafos KS-representables de

cualquier orden, como se ha podido ver en la ejecución de los anteriores, el tiempo de

ejecución de wgfree es considerablemente mayor que el de los algoritmos específicos de

cada dimensión, por lo que se recomienda, para un uso continuado de una dimensión

concreta, desarrrollar o usar los algoritmos para esa dimensión.

8.2 Algoritmos para detectar grafos cuyos vértices pertenecen

a subgrafos completos

En este apartado se exponen los resultados de la ejecución de los algoritmos

destinados a seleccionar aquellos grafos que cumplan que todos sus vértices se

encuentran en un subgrafo completo de orden n. Se han desarrollado algoritmos para

orden 3, 4, 5 y 6, además de uno general para cualquier orden.

50

Al igual que los algoritmos anteriores, se ha hecho uso de la capacidad de

extensión de geng, y las pruebas se han realizado con las dos opciones PRUNE y

PREPRUNE.

Estos algoritmos están desarrollados para satisfacer la condición:



Además del desarrollo en geng también se han incluido estos algoritmos en

pickg, por si pudiera resultar útil a efectos de ejecuciones futuras.

8.2.1 Pertenecen a K3

El nombre del ejecutable para d=3 es k3all (k3all.c es el archivo que contiene el

código fuente), y se ha de usar del siguiente modo:

./k3all n -Cd3

n es el número de vértices y d3 la valencia mínima de cada uno de ellos.

En el caso de pickg, el uso es:

./geng n -Cd3 | ./pickg -k

Donde geng se puede sustituir por un archivo de entrada del siguiente modo:

./pickg -k [infile]


PRUNE del algoritmo incluido en geng.

k3all.c - knall.c


Tiempo de

Ejecución (s)

k3all - knall

8 3 2232 0'00 - 0'00

9 3 72177 0'14 - 0'16

10 3 4473622 7'62 - 9'20

11 3 503231789 862'58 - 1030'63

12 3 100928585235

Como vemos, el número de grafos obtenidos aumenta considerablemente

conforme crece el número de vértices, y lo mismo ocurre con los tiempos de ejecución.

En este caso, los tiempos del algoritmo general, aun siendo superiores, no son

51

extremadamente disparatados en comparación con k3all. Respecto a los resultados con

12 vértices, sólo se muestran los obtenidos al ejecutar k3all.


k3all.c - knall.c


Tiempo de

Ejecución (s)

k3all - knall

8 3 2232 0'00 - 0'00

9 3 72177 0'14 - 0'18

10 3 4473622 8'04 - 10'38

11 3 503231789 897'02 - 1204'57

12 3 100928585235 168959'80

Como podemos ver, los tiempos de ejecución con PREPRUNE son ligeramente

mayores que con PRUNE.

A continuación, una muestra de los resultados obtenidos con pickg:


Tiempo de

Ejecución (s)

-k - -MB3

8 3 2232 0'02 - 0'01

9 3 72177 0'54 - 0'56

10 3 4473622 29'36 - 36'98

En este caso, los tiempos no sólo son mayores que los obtenidos con k3all y

knall, sino que además a los tiempos de ejecución de pickg hay que sumarle los tiempos

de ejecución de geng o, en su defecto, el tiempo de generación del archivo contenedor

de los grafos que tomará pickg como entrada. Claramente, el uso de pickg debe

limitarse a aquellos casos concretos donde nos resulte de alguna utilidad.


El archivo que contiene el código para d=4 es k4all.c, y la orden es:

./k4all n -Cd4

n es el número de vértices y d4 la valencia mínima de cada uno de ellos.

En el caso de que deseemos ejecutar el desarrollado en pickg, el uso es:

./geng n -Cd4 | ./pickg -K

52


./pickg -K [infile]

En la siguiente tabla podemos observar los resultados obtenidos con geng con la

opción PRUNE.

k4all.c - knall.c


Tiempo de

Ejecución (s)

k4all - knall

8 4 199 0'00 - 0'00

9 4 5312 0'04 - 0'05

10 4 335055 2'31 - 2'90

11 4 43523506 316'45 - 417'06

12 4 10751446866

Como vemos, el número de grafos cuyos vértices pertenecen todos a un K4 es

superior al de grafos KS-representables, y los tiempos de ejecución son igualmente

superiores.

Los resultados de PREPRUNE son los siguientes:

k4all.c - knall.c


Tiempo de

Ejecución (s)

k4all - knall

8 4 199 0'00 - 0'00

9 4 5312 0'03 - 0'04

10 4 335055 1'79 - 2'66

11 4 43523506 238'07 - 391'05

12 4 10751446866 61055'95

En el caso de la dimensión 4, PREPRUNE ofrece mejores tiempos que PRUNE.

Respecto a los tiempos obtenidos con pickg:


Tiempo de

Ejecución (s)

-k - -MB3

8 4 199 0'00 - 0'00

9 4 5312 0'06 - 0'09

10 4 335055 5'29 - 5'62

sólo podemos concluir lo mismo que en dimensión 3.

53


El nombre del archivo para d=5 es k5all.c, y el ejecutable se ha de usar del

siguiente modo:

./k5all n -Cd5


Para pickg el uso es:

./geng n -Cd5 | ./pickg -s


./pickg -s [infile]

En la siguiente tabla tenemos los resultados obtenidos con la opción PRUNE de

geng.

k5all.c - knall.c


Tiempo de

Ejecución (s)

k5all - knall

8 5 17 0'00 - 0'00

9 5 201 0'01 - 0'01

10 5 7056 0'30 - 0'40

11 5 643749 45'53 -71'29

12 5 134601998

Como vemos, el número de grafos resultantes sigue disminuyendo conforme

avanzamos en las dimensiones, lo que también ayuda a que sean menores los tiempos de

ejecución.


k5all.c - knall.c


Tiempo de

Ejecución (s)

k5all - knall

8 5 17 0'00 - 0'00

9 5 201 0'00 - 0'00

10 5 7056 0'20 - 0'39

11 5 643749 28'70 -76'05

12 5 134601998 10325'11

54

De nuevo vemos como PREPRUNE nos ofrece menores tiempos de ejecución.

Ahora vemos los tiempos obtenidos con pickg:


Tiempo de

Ejecución (s)

-k - -MB3

8 5 17 0'00 - 0'00

9 5 201 0'00 - 0'00

10 5 7056 0'38 - 0'5

Como en los casos anteriores, son tiempos mayores (sin contar los de generación

de los grafos que pickg estudiará), lo que hace poco recomendable usar esta opción en el

caso de que haya que manejar una gran cantidad de datos.


El archivo para d=6 se llama k6all.c, y el ejecutable se ha de usar del siguiente

modo:

./k6all n -Cd6


Con pickg el uso es:

./geng n -Cd6 | ./pickg -m


./pickg -m [infile]


PRUNE.

k6all.c - knall.c


Tiempo de

Ejecución (s)

k6all - knall

8 6 3 0'00 - 0'00

9 6 17 0'00 - 0'00

10 6 201 0'02 - 0'02

11 6 7121 2'51 - 3'94

12 6 763175 1141'24

55

Como vemos, en dimensión 6 el número de grafos resultantes es muy pequeño, y

los tiempos de ejecución son igualmente muy inferiores a los de las dimensiones

anteriores.


k6all.c - knall.c


Tiempo de

Ejecución (s)

k6all - knall

8 6 3 0'00 - 0'00

9 6 17 0'00 - 0'00

10 6 201 0'01 - 0'02

11 6 7121 1'77 - 4'25

12 6 763175 636'97 - 2428'02

Destacar aquí el hecho de que aun cuando los resultados con PREPRUNE son en

general mejores que con PRUNE, se da la circunstancia de que para 11 vértices y

haciendo uso de knall, el resultado con PRUNE es mejor.

Ahora vemos los tiempos obtenidos con pickg:


Tiempo de

Ejecución (s)

-k - -MB3

8 6 3 0'00 - 0'00

9 6 17 0'00 - 0'00

10 6 201 0'01 - 0'04

11 6 7121 1'68 - 3'62

Curiosamente, los tiempos de pickg son menores que los de los programas

desarrollados en geng, pero como ya sabemos, estos tiempos deben ser sumados a los de

generación de los grafos, los que los empeora.

8.2.5 Pertenecen a Kn

El archivo que contiene el código para d=n es knall.c, y para ejecutarlo debemos

usar la siguiente orden

./knall n o -Cdo

56

Donde n es el número de vértices y o el orden del subgrafo completo que

buscamos.

Con pickg el uso es:

./geng n -Cdo | ./pickg -MB#


./pickg -MB# [infile]

8.3 Algoritmos para detectar grafos KS-representables y con

todos sus vértices en subgrafos completos

Los siguientes algoritmos son el resultado de la unión de los programas

desarrollados para grafos KS-representables y grafos con todos sus vértices contenidos

en subgrafos completos.

Estos algoritmos nos darán como resultado todos aquellos grafos que cumplan

las dos condiciones siguientes:





La unión en un sólo programa de ambos algoritmos nos permite obtener menores

tiempos de ejecución y por tanto mayor eficiencia que si ejecutáramos los dos

programas de los apartados anteriores por separado.

8.3.1 Orden 3

Éste es un caso especial. El nombre del ejecutable para orden 3 es k3all, el

mismo que para obtener todos los grafos cuyos vértices se encuentren en subgrafos

completos de este orden, K3 (k3all.c es el archivo que contiene el código fuente), y se ha

de usar del siguiente modo:

./k3all n -Cfd3

n es el número de vértices y d3 la valencia mínima de cada uno de ellos. Nótese

la -f , que es la razón de que se use k3all y no haya habido necesidad de generar un

57

algoritmo nuevo, ya que -f es una opción de geng que permite generar sólo aquellos

grafos libres de ciclos de orden 4, lo que equivale a

, como puede observarse

en la siguiente ilustración:

Ilustración 23 .


PRUNE.

k3all.c


Tiempo de

Ejecución (s)

k3all -f

8 3 0 0'00

9 3 0 0'00

10 3 1 0'00

11 3 1 0'01

12 3 6 0'05

Vemos cómo el número de grafos resultantes se ha reducido drásticamente, lo

que nos acerca más a lo conjeturado por Peres. Respecto a los tiempos de ejecución,

para orden 3 son mínimos e iguales con ambas opciones.

Tiempos con PREPRUNE.

k3all.c


Tiempo de

Ejecución (s)

k3all -f

8 3 0 0'00

9 3 0 0'00

10 3 1 0'00

11 3 1 0'01

12 3 6 0'05

58

8.3.2 Orden 4

El nombre del ejecutable para orden 4 es w4k4 (w4k4.c es el archivo que

contiene el código fuente), y se ha de usar del siguiente modo:

./w4k4 n -Cd4


Tiempos con PRUNE.

w4k4.c - wnkn.c


Tiempo de

Ejecución (s)

w4k4 - wnkn

8 4 7 0'00 - 0'00

9 4 5 0'02 - 0'02

10 4 237 0'55 - 1'02

11 4 4094 36'25 - 86'88

12 4 293817 4770'08 - 12247'64

En este caso resulta curioso ver que hay más grafos obtenidos para 8 vértices

que para 9, para luego recuperar el crecimiento tanto en cantidad como en tiempos de

ejecución. Cabe resaltar el inmenso salto entre la ejecución para 11 vértices y la

ejecución para 12 vértices, y como siempre, se desaconseja el uso del algoritmo general

cuando se dispone de uno específico y por tanto con mejor tiempo de ejecución.


w4k4.c - wnkn.c


Tiempo de

Ejecución (s)

w4k4 - wnkn

8 4 7 0'00 - 0'00

9 4 5 0'01 - 0'01

10 4 237 0'18 - 0'75

11 4 4094 9'96 - 67'96

12 4 293817 1119'06 - 9591'87

Vemos cómo los tiempos son mejores con PREPRUNE, como viene siendo

habitual.

59

8.3.3 Orden 5

El nombre del ejecutable para orden 5 es w5k5 (w5k5.c es el archivo que

contiene el código fuente), y se ha de usar del siguiente modo:

./w5k5 n -Cd5


Tiempos con PRUNE.

w5k5.c - wnkn.c


Tiempo de

Ejecución (s)

w5k5 - wnkn

8 5 0 0'00 - 0'00

9 5 7 0'00 - 0'00

10 5 123 0'21 - 0'30

11 5 1239 28'61 - 48'03

12 5 134357 9094'97 - 15123'05

Curiosamente, para dimensión 5 el número de grafos resultantes es menor que en

dimensión 4, fenómeno que no ocurría entre la 3 y la 4.

A pesar de ello, el tiempo de ejecución del algoritmo es mayor que en el caso

anterior, compárese por el ejemplo el tiempo para 11 vértices.

Sobre los tiempos obtenidos en función del algoritmo (el específico para orden 5

o el general) la pérdida de eficiencia en la ejecución llega hasta casi el 400%.


w5k5.c - wnkn.c


Tiempo de

Ejecución (s)

w5k5 - wnkn

8 5 0 0'00 - 0'00

9 5 7 0'00 - 0'00

10 5 123 0'11 - 0'26

11 5 1239 14'13 - 67'96

12 5 134357 4203'33 - 16051'09

Como vemos, PREPRUNE sigue ofreciéndonos menores tiempos de ejecución.

60

8.3.4 Orden 6

Para orden 6 el ejecutable es w6k6 (w6k6.c es el archivo que contiene el código

fuente), y su uso:

./w6k6 n -Cd6


Tiempos con PRUNE.

w6k6.c - wnkn.c


Tiempo de

Ejecución (s)

w6k6 - wnkn

8 6 0 0'00 - 0'00

9 6 0 0'00 - 0'00

10 6 7 0'03 - 0'04

11 6 123 4'83 - 11'38

12 6 13970 2716'89 - 7988'33

De nuevo obtenemos menos grafos en la salida, lo que nos va acercando más a

los resultados esperados por Peres. Respecto a los tiempos de ejecución, se viene

repitiendo la tónica habitual.


w6k6.c - wnkn.c


Tiempo de

Ejecución (s)

w6k6 - wnkn

8 6 0 0'00 - 0'00

9 6 0 0'00 - 0'00

10 6 7 0'02 - 0'05

11 6 123 5'36 - 16'86

12 6 13970 3135'64 - 14288'64

Al comparar los tiempos de ejecución para orden 6, comprobamos que, en este

caso, los resultados con PRUNE son bastante menores que los resultados que se han

obtenido con PREPRUNE. Recordamos que este fenómeno se producía también en la

ejecución de w6free.

61

8.3.5 Orden n

En el caso de desear ejecutar estos algoritmos para cualquier orden mayor de 3,

el ejecutable es wnkn (wnkn.c es el archivo que contiene el código fuente), y su uso:

./wnkn n o -Cdo

Donde n es el número de vértices y o el orden para el que deseamos ejecutar el

programa, además de la valencia mínima de cada uno de los grafos que deseamos tratar.

8.4 Algoritmos para detectar grafos no KS-coloreables en

grafos KS-representables y cuyos vértices forman parte de un

subgrafo completo

En este apartado vamos a ver los resultados de los algoritmos desarrollados para

detectar grafos no KS-coloreables. Con esta restricción cubriríamos las tres condiciones

de la conjetura de Peres antes expuestas:



No hay ninguna posible coloración verde-rojo de forma que no existan dos

verdes vecinos y haya un sólo vértice verde en cada Kd.



Sin embargo, y como se podrá ver a raíz de los resultados, hay algunos grafos

que superan las tres condiciones. Esto nos haría pensar que la conjetura de Peres no es

válida, pero estaríamos equivocados, ya que el problema radica en la existencia de

aristas ocultas en los grafos resultantes, de tal modo que en el mundo físico existiría una

ortogonalidad entre vectores que no se ve reflejada en el grafo que representa dichos

vectores.

Estos algoritmos han sido desarrollados haciendo uso de las facilidades ofrecidas

por pickg para su extensión. Todas las pruebas reciben como entrada los grafos

resultantes de las pruebas hechas en el apartado 8.3, pero los tiempos mostrados son

sólo los de pickg.

62

8.4.1 Orden 3

Para dimensión 3, el modo de ejecutar el algoritmo es:

./pickg -R

Más concretamente para esta prueba se ha usado la siguiente orden:

./k3all n -Cfd3 | ./pickg -R

En la siguiente tabla podemos observar cómo el número de grafos resultantes es

nulo para grafos de entre 8 y 12 vértices:

pickg -R


Tiempo de

Ejecución (s)

-R - -uy3

8 3 0 0'00 - 0'00

9 3 0 0'00 - 0'00

10 3 0 0'00 - 0'00

11 3 0 0'00 - 0'00

12 3 0 0'00 - 0'00

8.4.2 Orden 4


./pickg -X

Para esta prueba en concreto se ha usado la siguiente orden:

./w4k4 n -Cd4 | ./pickg -X

En la siguiente tabla tenemos los resultados para grafos de entre 8 y 12 vértices:

pickg -X


Tiempo de

Ejecución (s)

-X - -uy4

8 4 0 0'00 - 0'00

9 4 0 0'00 - 0'00

10 4 1 0'00 - 0'00

11 4 0 0'00 - 0'00

12 4 14 0'26 - 0'62

63

Se produce aquí el fenómeno explicado anteriormente de las aristas ocultas, lo

que provoca que los algoritmos devuelvan cierto número de grafos que no deberían

estar presentes según la conjetura de Peres. Para poder solucionar esto es necesario

desarrollar un nuevo algoritmo que detecte dichas aristas y las vaya añadiendo al grafo,

comprobando nuevamente si es posible su coloración.

8.4.3 Orden 5

En el caso de dimensión 5, el modo de ejecutar el algoritmo es:

./pickg -x

Para esta prueba se ha usado la siguiente orden:

./w5k5 n -Cd5 | ./pickg -x

La tabla con los resultados:

pickg -x


Tiempo de

Ejecución (s)

-x - -uy5

8 5 0 0'00 - 0'00

9 5 0 0'00 - 0'00

10 5 0 0'00 - 0'00

11 5 0 0'00 - 0'00

12 5 0 0'14 - 0'63

Como puede observarse, ningún grafo supera las tres condiciones de Peres en

orden 5.

8.4.4 Orden 6

Para orden 6, el modo de ejecutar el algoritmo es:

./pickg -w

Y la orden usada en esta prueba:

./w6k6 n -Cd6 | ./pickg -w

64

Como queda plasmado en la siguiente tabla, el número de grafos devueltos es

nulo para las pruebas de entre 8 y 12 vértices. Por tanto, tan sólo hemos hallado grafos

donde se dé el fenómeno de las aristas ocultas en dimensión 4.

pickg -w


Tiempo de

Ejecución (s)

-w - uy6

8 6 0 0'00 - 0'00

9 6 0 0'00 - 0'00

10 6 0 0'00 - 0'00

11 6 0 0'00 - 0'00

12 6 0 0'01 - 0'05

8.4.5 Orden n

En el caso de desear ejecutar el algoritmo para cualquier dimensión n, el modo

de hacerlo es:

./pickg -uy#

Como se ha podido comprobar a partir de las pruebas realizadas, el tiempo de

ejecución del algoritmo general es considerablemente superior al de los algoritmos

concretos, y aunque sean poco determinantes en comparación a los tiempos de los

algoritmos que pickg toma como entrada, siempre es recomendable hacer uso de los

algoritmos desarrollados específicamente para cada dimensión.

8.5 Algoritmos para detectar grafos no KS-coloreables en

grafos generales

En el apartado anterior se han ofrecido los resultados de los algoritmos que

requieren que todos los vértices formen parte de un subgrafo completo. En este apartado

observaremos las diferencias entre dichos algoritmos y aquellos desarrollados para

cualquier grafo.

Como es lógico, al estar estos algoritmos pensados para grafos generales, el

tiempo de ejecución es superior (o igual) al obtenido en 8.4, ya que cuanto menos

específico es el código peores son los tiempos resultantes.

65

8.5.1 Orden 3


./pickg -l


./k3all n -Cfd3 | ./pickg -l

La tabla de la ejecución muestra los mismos resultados que en 8.4.1, y también

los mismos tiempos.

pickg -l


Tiempo de

Ejecución (s)

-l - -GH3

8 3 0 0'00 - 0'00

9 3 0 0'00 - 0'00

10 3 0 0'00 - 0'00

11 3 0 0'00 - 0'00

12 3 0 0'00 - 0'00

8.5.2 Orden 4

En el caso de la dimensión 4, el algoritmo es:

./pickg -L


./w4k4 n -Cd4 | ./pickg -L

pickg -L


Tiempo de

Ejecución (s)

-L - -GH4

8 4 0 0'00 - 0'00

9 4 0 0'00 - 0'00

10 4 1 0'00 - 0'00

11 4 0 0'00 - 0'00

12 4 14 0'36 - 0'58

66

En la tabla anterior comprobamos el aumento del tiempo de ejecución en este

caso, que es de un 38%.

8.5.3 Orden 5


./pickg -O


./w5k5 n -Cd5 | ./pickg -O

pickg -O


Tiempo de

Ejecución (s)

-O - -GH5

8 5 0 0'00 - 0'00

9 5 0 0'00 - 0'00

10 5 0 0'00 - 0'00

11 5 0 0'00 - 0'00

12 5 0 0'33 - 0'63

Aquí el tiempo de ejecución para 12 vértices aumenta en un 135%.

8.5.4 Orden 6

Para orden 6, el ejecutable es:

./pickg -h


./w6k6 n -Cd6 | ./pickg -h

pickg -h


Tiempo de

Ejecución (s)

-h - -GH6

8 6 0 0'00 - 0'00

9 6 0 0'00 - 0'00

10 6 0 0'00 - 0'00

11 6 0 0'00 - 0'00

12 6 0 0'03 - 0'07

67

En la tabla se puede ver como los tiempos aumentan en un 200% respecto a los

obtenidos en 8.4.4 para 12 vértices.

8.5.5 Orden n

Para cualquier dimensión n, el modo de ejecutar el algoritmo es:

./pickg -GH#

8.6 Algoritmos para detectar grafos no KS-coloreables dada

una coloración inicial

8.6.1 Coloración inicial dada por el usuario

Este es un caso especial de algoritmo desarrollado para hacer comprobaciones

muy concretas sobre grafos ya conocidos.

A la hora de ejecutar este algoritmo, el usuario debe antes haber introducido una

coloración inicial a su parecer en el archivo coloreado.txt, introduciendo primero el

número del vértice y a continuación, separado por un espacio, el color (0 para rojo, 1

para verde) de dicho vértice. Todos aquellos vértices que no reciban coloración inicial

en el archivo serán tratados como indeterminados. En el caso de que el archivo esté en

blanco, el algoritmo funcionará de manera similar a los algoritmos del apartado 8.5.

8.6.1.1 Orden 3


./pickg -A [infile]

En infile se encontrará el grafo sobre el que deseamos establecer una coloración

inicial.

8.6.1.2 Orden 4


./pickg -N [infile]

68

En infile se encontrará el grafo, conocido, sobre el que deseamos establecer una

coloración inicial.

8.6.1.3 Orden 5

Para orden 5, el algoritmo se ejecuta del siguiente modo:

./pickg -C [infile]

infile cotiene el grafo sobre el que deseamos establecer una coloración inicial.

8.6.1.4 Orden 6


./pickg -P [infile]

Donde infile es el archivo contenedor del grafo sobre el que deseamos establecer

una coloración inicial.

8.6.1.5 Orden n

Para orden n, el modo de ejecutar el algoritmo es:

./pickg -US# [infile]

Veamos ahora un ejemplo de cómo funcionan estos algoritmos:

Ilustración 24: Grafo

69

Dado el grafo de la imagen anterior, se desea saber si es posible encontrar una

coloración verde-rojo de dicho grafo haciendo verdes los vértices 2 y 10, del siguiente

modo:

Ilustración 25: Grafo con coloración inicial

Para ello, guardaremos el grafo en un archivo llamado grafoci, y en coloreado.txt

introduciremos las siguientes líneas:

Ejecutamos ahora la siguiente orden, suponiendo que deseamos ver el resultado

para dimensión 3:

./pickg -A grafoci

El resultado es que no es posible colorear el grafo con esa coloración inicial.

Probamos a continuación con el vértice 10 en rojo:

Volvemos a ejecutar el algoritmo, y el resultado en esta ocasión es positivo,

devolviendo una posible coloración del grafo, en este caso la siguiente:

2 1

10 0

2 1

10 1

70

Ilustración 26: Grafo coloreado

8.6.2 Coloración inicial de dos vértices

En este apartado están las pruebas resultantes de la ejecución de los algoritmos

que detectan aquellos grafos que contienen alguna pareja de vértices cuya coloración

cumpla que si uno de los vértices es verde, obliga al otro a ser rojo para que exista

coloración verde-rojo válida. Los conjuntos de vértices en los que se cumple esto son

los llamados conjuntos YIN (Yes Implies No).

Para evitar posibles errores en la ejecución del algoritmo, queremos hacer

hincapié en el cambio del ejecutable. Antes veníamos usando pickg, pero para la

ejecución de estos algoritmo haremos uso de pickgci. pickgci no es más que un

duplicado de pickg hecho exclusivamente para la ejecución de los algoritmos de

coloración inicial (de ahí el ci final). Nos vimos en la necesidad de crear esta copia de

pickg por la falta de letras para la adición de nuevas opciones.

Las pruebas que se presentan a continuación se han realizado con diferentes

entradas, a saber: geng -Cd2, wNfree, kNall y wNkN, los tres últimos con -CdN, donde

N es la dimensión a estudiar.

8.6.2.1 Orden 3


./pickgci -A

71

La orden usada en esta prueba:

./geng n -Cd2 | ./pickgci -A

pickgci -A


Tiempo de

Ejecución (s)

-A - -US3

8 3 2573 0'12 - 0'19

9 3 57163 6'24 - 9'1

10 3 1927224 542'52 - 816'43

Como puede verse, el tiempo de ejecución se dispara entre un valor del número

de vértices y el siguiente. No se presentan los resultados más allá de 10 vértices debido

a que el tiempo de ejecución es demasiado largo, y puesto que estos resultados son sólo

a modo informativo y no necesarios, se ha optado por postergar estas pruebas a favor de

otras de mayor importancia.

La siguiente prueba es para todos los grafos libres de ciclos de orden 4, es decir,

buscamos conjuntos YIN en grafos KS-representables. La ejecución se ha hecho con la

siguiente orden en consola:

./geng n -Cfd3 | ./pickgci -A

pickgci -A


Tiempo de

Ejecución (s)

-A

8 3 0 0'00

9 3 0 0'00

10 3 2 0'00

11 3 6 0'00

12 3 30 0'00

El número de grafos resultantes es bastante pequeño, y el tiempo de ejecución

nulo.

A continuación, presentamos los resultados para grafos con todos sus vértices

contenidos en un subgrafo completo de orden 3. La orden usada en esta prueba:

./k3all n -Cd3 | ./pickgci -A

72

pickgci -A


Tiempo de

Ejecución (s)

-A

8 3 489 0'06

9 3 11649 2'25

10 3 449534 233'08

11 3

12 3

Como puede verse, el tiempo de ejecución se dispara entre un valor del número

de vértices y el siguiente.

Por último, presentamos los resultados para grafos KS-representables y con

todos sus vértices en subgrafos completos de orden 3. La orden usada es:

./k3all n -Cfd3 | ./pickgci -A

pickgci -A


Tiempo de

Ejecución (s)

-A

8 3 0 0'00

9 3 0 0'00

10 3 1 0'00

11 3 0 0'00

12 3 5 0'00

El número de grafos resultantes es muy pequeño en orden 3.

8.6.2.2 Orden 4


./pickgci -N

Y la orden usada en esta primera prueba:

./geng n -Cd2 | ./pickgci -N

73

pickgci -N


Tiempo de

Ejecución (s)

-N - -US4

8 4 1421 0'12 - 0'15

9 4 71379 4'13 - 6'26

10 4 4638034 297'52 - 470'77

La siguiente prueba es para grafos KS-representables. La ejecución se ha hecho

con la siguiente orden en consola:

./w4free n -Cd4 | ./pickgci -N

pickgci -N


Tiempo de

Ejecución (s)

-N

8 4 5 0'00

9 4 84 0'01

10 4 4563 0'56

11 4 401416 76'22

12 4 52582390 13065'19

Como puede verse el número de grafos resultante crece continuamente, al igual

que los tiempos de ejecución. Notable sobre todo la diferencia entre los tiempos para 11

y 12 vértices.

La próxima prueba es para grafos cuyos vértices se encuentran todos en un

subgrafo compelto de orden 4. La ejecución se ha hecho con la siguiente orden en

consola:

./k4all n -Cd4 | ./pickgci -N

pickgci -N


Tiempo de

Ejecución (s)

-N

8 4 70 0'01

9 4 2238 0'14

10 4 135214 13'34

11 4

12 4

74

Por último, los resultado de buscar conjuntos YIN en grafos KS-representables y

con todos sus vértices en subgrafos de orden 4. La orden en consola es:

./w4k4 n -Cd4 | ./pickgci -N

pickgci -N


Tiempo de

Ejecución (s)

-N

8 4 2 0'00

9 4 5 0'00

10 4 163 0'00

11 4 2706 0'19

12 4 200630 11'57

Recordamos ahora que aunque los tiempos de ejecución del algoritmo son

pequeños, no ocurre igual con la primera parte de la orden dada, la generación de los

grafos, cuyos tiempos se reflejan en el apartado 8.1.4.

8.6.2.3 Orden 5


./pickgci -C


./geng n -Cd2 | ./pickgci -C

pickgci -C


Tiempo de

Ejecución (s)

-C - -US5

8 5 185 0'07 - 0'09

9 5 9555 3'5 - 4'96

10 5 831555 261'08 - 415'1

A continuación los resultados de la ejecución del algoritmos en grafos KS-

representables. La orden en consola es:

./w5free n -Cd5 | ./pickgci -C

75

pickgci -C


Tiempo de

Ejecución (s)

-C

8 5 0 0'00

9 5 13 0'00

10 5 1874 0'47

11 5 423636 132'67

12 5

Como puede verse el número de grafos resultante crece continuamente, al igual

que los tiempos de ejecución. Entre 10 vértices y 11 se produce un salto en el aumento

de los tiempos de ejecución.

La próxima prueba es para grafos cuyos vértices se encuentran todos en un

subgrafo compelto de orden 5. La ejecución se ha hecho con la siguiente orden en

consola:

./k5all n -Cd5 | ./pickgci -C

pickgci -C


Tiempo de

Ejecución (s)

-C

8 5 2 0'00

9 5 70 0'00

10 5 3293 0'25

11 5 336174 34'55

12 5



./w5k5 n -Cd5 | ./pickgci -C

pickgci -C


Tiempo de

Ejecución (s)

-C

8 5 0 0'00

9 5 2 0'00

10 5 20 0'00

11 5 1081 0'04

12 5

76

8.6.2.4 Orden 6


./pickgci -P


./geng n -Cd2 | ./pickgci -P

pickgci -P


Tiempo de

Ejecución (s)

-P - -US6

8 6 8 0'06 - 0'07

9 6 421 2'83 - 3'56

10 6 37079 208'04 - 273'79

En la siguiente tabla se ha ejecutado el algoritmo en los grafos obtenidos a partir

del programa para hallar grafos KS-representables en dimensión 6. La orden en consola

es:

./w6free n -Cd6 | ./pickgci -P

Y los resultados obtenidos:

pickgci -P


Tiempo de

Ejecución (s)

-P

8 6 0 0'00

9 6 0 0'00

10 6 35 0'02

11 6 14122 12'86

12 6

A continuación se detalla el resultado de ejecutar el algoritmo de coloración

inicial en aquellos grafos cuyos vértices se encuentran todos contenidos en un subgrafo

completo de orden 6. La ejecución se ha hecho con la siguiente orden en consola:

./k6all n -Cd6 | ./pickgci -P

La tabla con los resultados:

77

pickgci -P


Tiempo de

Ejecución (s)

-P

8 6 0 0'00

9 6 2 0'00

10 6 70 0'02

11 6 3293 0'39

12 6 403291 65'36

Como dato a señalar, resulta curioso que los resultados para 9, 10 y 11 vértices

sean idénticos que para 8, 9 y 10 vértices en la dimensión anterior.



./w6k6 n -Cd6 | ./pickgci -P

pickgci -C


Tiempo de

Ejecución (s)

-P

8 6 0 0'00

9 6 0 0'00

10 6 2 0'00

11 6 20 0'00

12 6 2443 1'04

Se repite aquí de nuevo el mismo fenómeno que en el caso anterior, los

resultados para 9, 10 y 11 vértices son iguales que los resultados para 8, 9 y 10 vértices

en dimensión 5.

8.6.2.5 Orden n

Para cualquier dimensión n, el modo de ejecutar el algoritmo es:

./pickgci -US#

78

8.7 Tablas de algoritmos

En las siguientes tablas se exponen todos los algoritmos y sus modos de

ejecución. Los símbolos utilizados son los siguientes:

n: número de vértices

o: orden en que se desea ejecutar (geng)

#o: orden en que se desea ejecutar (pickg)

8.7.1 Grafos KS-representables

Orden Herramienta Ejecución

4 geng ./w4free n

5 geng ./w5free n

6 geng ./w6free n

d geng ./wgfree n o

8.7.2 Subgrafos completos


3 geng ./k3all n

3 pickg ./pickg -k

4 geng ./k4all n

4 pickg ./pickg -K

5 geng ./k5all n

5 pickg ./pickg -s

6 geng ./k6all n

6 pickg ./pickg - m

d geng ./knall n o

d pickg ./pickg -MB#o

8.7.3 Unión KS-representables y subgrafos completos


3 geng ./k3all n -f

4 geng ./w4k4 n

5 geng ./w5k5 n

6 geng ./w6k6 n

d geng ./wnkn n o

79

8.7.4 Grafos no KS-coloreables

Grafos compuestos de subgrafos completos:


3 pickg ./pickg -R

4 pickg ./pickg -X

5 pickg ./pickg -x

6 pickg ./pickg -w

d pickg ./pickg -uy#o

Grafos generales:


3 pickg ./pickg -l

4 pickg ./pickg -L

5 pickg ./pickg -O

6 pickg ./pickg -h

d pickg ./pickg -GH#o

8.7.5 Grafos no KS-coloreables con coloración inicial

Coloración dada por el usuario:


3 pickg ./pickg -A

4 pickg ./pickg -N

5 pickg ./pickg -C

6 pickg ./pickg -P

d pickg ./pickg -US#o

Hallar pareja de vértices verde-rojo, conjuntos YIN:


3 pickgci ./pickgci -A

4 pickgci ./pickgci -N

5 pickgci ./pickgci -C

6 pickgci ./pickgci -P

d pickgci ./pickgci -US#o

80

81

9 Desarrollos Futuros

En este proyecto se ha hecho una pequeña incursión en el mundo de los grafos

aplicados a la Física Cuántica. Los algoritmos desarrollados sin embargo pueden tener

utilidad en ambos campos, tanto la Matemática Discreta como la Física Cuántica, lo que

nos deja un amplio margen de futuras ampliaciones.

Centrándonos en la Física Cuántica, son tantas las posibles aplicaciones de

grafos en la resolución de problemas que podríamos pasar años desarrollando nuevos

algoritmos, cada uno especializado en un problema concreto. En la línea del Teorema de

Kochen-Specker y la conjetura de Peres, aún queda por resolver el problema de las

aristas ocultas, aquellas que aunque no aparezcan en el grafo, por la estructura que éste

tiene existen si trasladamos el problema a su argumento físico.

Otra posible ampliación de este proyecto se basa en los algoritmos de coloración

inicial para pruebas YIN (Yes Implies No) y YIY (Yes Implies Yes). Una prueba YIY

es un conjunto de preguntas cuánticas en las cuales si una es true, la otra, que no es

afectada directamente, ha de ser true también. Estas pruebas sirven para demostrar la

contextualidad de la Física Cuántica, ya que, como sabemos, si el estado de un elemento

es true, hay una probabilidad no nula de que el estado del otro sea false. Sin embargo,

las pruebas de conjuntos YIY demuestran que los estados de elementos no contextuales

están conectados, lo que las convierte en pruebas que refutan la no contextualidad de la

Física Cuántica.

Los conjuntos YIY pueden ser representados mediante grafos, como ya

sabemos, donde los vértices son las proposiciones, las aristas unen aquellas

proposiciones que se excluyen mutuamente y d vértices conectados entre sí representan

82

contextos completos. Respecto a las pruebas YIN, aparte de su importancia propia,

ayudan también a encontrar demostraciones del teorema de Kochen-Specker. La

siguiente figura representa la menor prueba YIN posible en dimensión 3 y la única con

8 vértices:

Ilustración 27: YIN mínima d=3

Como puede observarse en la imagen, el que el vértice etiquetado con Y sea

verde obliga a que el vértice N sea rojo. De esta prueba con 8 vértices, es posible pasar a

la prueba mínima YIY en dimensión 3, que consta de 10 vértices:

Ilustración 28: YIY mínima d=3

La prueba original de 117 vértices del teorema de Kochen-Specker está basada

en repeticiones de esta prueba.

El algoritmo de coloración inicial desarrollado en este proyecto ha ayudado a

encontrar pruebas mínimas YIN en dimensión 4.

83

10 Bibliografía

nauty User's Guide (Versión 2.4 Nov 2009). Brendan D. McKay.

Quantum Theory: Concepts and Methods. Asher Peres. 2002 Kluwer

Academic Publishers.

The Kochen-Specker Theorem. Stanford Encyclopedia of Philosophy.

Consultado Noviembre 2010:

http://plato.stanford.edu/entries/kochen-specker/

Artículos de wikipedia. Consultado Noviembre 2010:

http://es.wikipedia.org/wiki/Teoría_de_variables_ocultas

http://es.wikipedia.org/wiki/Paradoja_EPR

http://es.wikipedia.org/wiki/Teoría_de_grafos

Practical Graph Isomorphism. Brendan D. McKay. Congressus

Numerantium, 30 (1981).

Minimun yes-implies-yes sets. Adán Cabello, José R. Portillo y Karl Svozil

(sin publicar).

Documents

Grafos