teoría de grafos y ajedrez
TRANSCRIPT
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.