Teoría de grafos y ajedrez

Teoría de Grafos y AjedrezMiguel González GonzálezDepartamento de MatemáticasIES Pintor Antonio LópezTutora: Celia Pérez Delgado

¿Qué es un grafo?• En nuestro mundo existen infinidad de elementos conectados

formando redes.

• Las matemáticas formalizan cualquier red con los grafos, teniendo en cuenta dos conceptos: vértices y aristas.G = ( ) V, E E = { }

v1, v2, v3 {v1, v2} , {v2, v3}v1 v3

v2

Formalmente:Gráficamente:

V = { }

Problema de dominación de un grafo

v1 v3v2 v4

v5

v6

• Objetivo: Cubrir el grafo de manera óptima

v4v5

v6v2

v1 v3

Número dominante: 2

Ajedreza3 b3 c3a2 b2 c2a1 b1 c1

Grafo de una pieza:

3 x 3

Dominación en ajedrez• Objetivo: Cubrir todas las casillas con el menor número de

piezas de un tipo.Torre:

Número dominante = 8

Dominación con la dama• Primer algoritmo: Búsqueda por fuerza bruta.

• Para la dama, no existe ninguna regla general a seguir.

n =k = 358135• Se evalúa la

posición.• Se obtiene otra posición.• Al final se evalúan todas las posibilidades, obteniendo las soluciones que existan.

• Segundo algoritmo: Algoritmo Voraz• Genera un conjunto dominante

para el tablero escogido.• Primero se numeran las

casillas según el alcance que tenga una dama en ellas.

12

3

4

56

7

8

910

11121314

15 16 17 18 19 20 2124

2322

2526

27

28 282828

26262626

26

26

26

26

26

26

26

26

2424

24

24242424

24

24

24

24

24

24

24

24

24

24

24

24

2222222222222222

22

22

22

22

22

22

22

22

22

22

22

22

22

22

22

22

22

22

2224

22

141010

16

12

12

10

1512161416131411

14

12

16

12

12

16

16

13

12

1212131611

16

15 1

5

15

15

15

13

13

12

10

12 1

2

12

12

12

10

10

10

14

14

14

14

14

14

14

11

11

15

15

13 1

3

13

16 1

6• Se selecciona la mejor

casilla para asignarle una dama.• Se repite el proceso hasta que el tablero queda cubierto.

Conclusiones

Muchas gracias

Bibliografía:Bibliografía:•Las figuras, gráficas y algoritmos/resultados son Las figuras, gráficas y algoritmos/resultados son de fuente propia.de fuente propia.•Referencias de consulta:Referencias de consulta:

• Cockayne, E. J. Cockayne, E. J. Chessboard domination Chessboard domination problems. Discrete mathematics 86 (1990), problems. Discrete mathematics 86 (1990), 13–20.13–20.

• Patric R. J. Östergard, W. D. Weakley Patric R. J. Östergard, W. D. Weakley Values of domination numbers of the Values of domination numbers of the queen’s graph.queen’s graph.

• Van Steen, MVan Steen, M. An Introduction to Graph . An Introduction to Graph Theory and Complex Networks. 2010.Theory and Complex Networks. 2010.

• Watkins, J. J. Watkins, J. J. Across the Board: The Across the Board: The Mathematics of Chessboard Problems. 2004.Mathematics of Chessboard Problems. 2004.