Comienzo: Lunes 19
de marzo.
Horario: Lunes, Miércoles y Viernes
de 15:00 hs a 16:30 hs. (los miércoles será el horario
de Práctico)
Lugar: IMERL (Lunes y Miércoles:
Salón de Seminarios; Viernes: salón 105 FIng)
Forma
de evaluación (si el número de estudiantes se mantiene
menor a 15):
a) Carpeta de Ejercicios + b) Exposición
de un tema + c) Oral teórico final.
Libro de
referencia:
Algebraic graph Theory; Chris Godsil, Gordon Royle.
Otros libros de interés:
Algebraic graph theory, Norman Biggs.
Modern Graph Theory, Bollobas.
Página web (si
el número de estudiantes se mantiene menor a 15):
Página web
anterior (con mucha información):
www.fing.edu.uy/~canale/tag/Default.htm
PRÁCTICOS
Para acceder a los prácticos del curso pulse aquí
Publicados:
Práctico 1; Práctico 2, Práctico 3, Práctico 4.
|
Práctico 1 |
Práctico 2 |
Práctico 3 |
Práctico 4 |
Práctico 5 |
||
|
Alejandro Duarte |
17 |
3 |
2 |
|||
|
Cecile Mezzera |
16 |
4 |
5 |
7 |
||
|
Celia Sena |
15 |
3 |
3 |
8 |
||
|
Felipe Negreira |
6 |
2 |
12 |
9 |
||
|
Florencia Cubría |
12 |
8 |
1 |
10 |
||
|
Gustavo Rama |
Ej. extra * |
4 |
14 |
12 |
||
|
Laura Gatti |
17 |
8 |
4 |
4 |
||
|
Marcos Barrios |
16 |
2 |
13 |
6 |
||
|
Martín Zubeldía |
15 |
5 |
6 |
1 |
||
|
Matías Guichón |
6 |
5 |
5 |
|
||
|
Natalia Flores |
11 |
7 |
3 |
5 |
||
|
Ramón Sellanes |
12 |
7 |
2 |
8 |
||
|
Telmo Acosta |
11 |
7 |
1 |
6 |
||
|
* Ejercicio que Rama expuso en clase |
EXPOSICIONES DE LOS ESTUDIANTES
On the shortest spanning subtree of a graph and the traveling problem
Resumen
Bouvka en el 1926 presenta una demostración de la existencia de árbol generador minimal para grafos ponderados (con peso) no dirigido conexo y sin lazos. Kruskal y Prim a mediados del siglo 20 dan algoritmos para la construcción de dichos árboles, en esta presentación se definen todos los conceptos usados y se demuestran una serie de resultados que se usan en la demostración de que los algoritmos antes mencionados efectivamente construyen un árbol generador minimal. Al final se comparan los dos algoritmos computacionalmente.
An edge but not vertex transitive cubic graph
Resumen
En este artículo publicado en 1968 por I. Z. Bouwer se describe un grafo cúbico arista transitivo pero no vértice transitivo con 54 vértices, como respuesta a la pregunta: ¿existe un grafo regular de grado primo impar arista transitivo pero no vértice transitivo?, planteada por J. Folkman en 1967.
Una construcción de grafos vértice transitivos
Resumen
Este artículo define una familia de grafos vértice transitivos: los grafos (m,n)-metacirculantes. Dada una familia transitiva de grupos de permutaciones, considera aquellos grafos que tienen como subgrupo de sus automorfismos a un grupo de dicha familia. Finalmente, busca condiciones para que un grafo (m,n)-metacirculante sea de Cayley y viceversa.
On the multiplicity of the eigenvalues of a graph
Resumen:
Dado un grafo G con polinomio característico P_G (t), se considera la descomposición ML P_G(t) =q_1(t)q_2(t)^2 . . . q_m (t)^m , donde cada q_i(t) es un polinomio con coeficientes enteros y tiene sólo las raíces de multiplicidad i de P_G(t). Luego, se da un algoritmo recursivo para hallar de manera sencilla los polinomios q_i(t) y se describe la relación de los coeficientes de estos polinomios con algunos otros invariantes del grafo G. En particular se deducen cotas superior e inferior para la energía del grafo E(G) = sumatoria en i de |L_i|, en donde L_i son los valores propios de G. La mayoría de los resultados se prueban para el caso más general en donde se tiene una matriz simétrica cuyo polinomio caracterísitco tiene coeficientes enteros.
A 27 vertex group that is vertex transitive and edge transitive but nos 1-transitive
Resumen
En
este artículo Peter G. Doyle construye un grafo de 27
vértices que es vértice transitivo y arista
transitivo, pero no es flecha transitivo. Hasta ese momento, el
grafo más chico que se conocía con estas
caractesísticas era de 54 vértices.
Doyle, en el
artículo, construye un grupo G a partir de dos generadores, a
y c, y ciertas relaciones. Define el grafo X como el grafo de Cayley
que utiliza el grupo G. Al ser un grafo de Cayley, automaticamente
es vértice
transitivo. Para probar
que es arista
transitivo, ve que
cualquier arista puede ser llevada a (1,a) o a (1,c), y también
hay un automorfismo que me lleva la primer arista en la segunda.
Entonces, componiendo los automorfismos, tenemos que el grafo es
arista transitivo.
El razonamiento para ver que el grafo no
es flecha transitivo,
es ver que si considero el subgrafo pleno que toma todos los
vértices que no distan más de 2 de la unidad, queda
claro que no se puede mandar la arista orientada (1,a) en (1,
aˆ(-1)), y de ahí se deduce lo deseado.
Teorema de Hoffman-Singelton
Resumen
El teorema de Hoffman-Singelton demuestra que existe una cantidad finita de grafos de Moore de diámetro 2. En particular, que solamente existen para grados máximos 2, 3, 7 y 57. Un grafo de Moore de diámetro 2 es un grafo conexo regular de diámetro 2 y con k^2+1 vértices siendo k el grado del grafo.
Un grafo no hamiltoniano
Resumen
En este artículo W.T Tutte (1959) presenta un grafo cúbico de 28 vértices, descubierto por el Prof. H.S.M Coxeter, cuya estructura consta de tres heptágonos: A(a1, a2, ..., a7); B(b1, b2, ..., b7) y C(c1, c2, ..., c7) y los siete vértices restantes son di, con 1≤i≤7, tales que los tres vértices incidentes con di,son ai,bi ci,.
Se prueba, que no es un grafo Hamiltoniano. Para dicha prueba se supone que el grafo contiene un ciclo Hamiltoniano (H) y se divide la demostración en 5 casos en los que se toma en cuenta el máximo de aristas consecutivas de A que pertenecen a H.
A Novel Slow Coherency Based Graph Theoretic Islanding Strategy
Resumen
En el artículo “A Novel Slow Coherency Based Graph Theoretic Islanding Strategy”, Yang, Vittal y Heydt presentan una estrategia basada en la teoría de grafos, para la separación en islas de un sistema de potencia. Esta estrategia está basada en el autovector correspondiente al segundo autovalor más pequeño de la matriz Laplaciana del grafo. El valor medio de las componentes de este autovector divide en grafo en dos subgrafos conexos.
Almost all trees are cospectral
Resumen
Constructing cosprectral graphs
Resumen
Fue
probado por Schwenk que la proporción de árboles de
tamaño n que están caracterizados por su
espectro tiende a cero cuando n crece, lo que no se
sabe si es verdad para grafos en general. Para la prueba se
construyen pares de árboles coespectrales.
En este trabajo se presentan varias construcciones de pares de grafos coespectrales, como es la transformación local de un grafo dada una partición de sus vértices con algunas restricciones técnicas, el producto de kronecker y el pegado de grafos.
RESUMEN DE CLASES
Lunes 19 de marzo: 1.1 Grafos; 1.2 Subgrafos; 1.3 Automorfismos.
Miércoles 21 de marzo: 1.4 Homomorfismos; 1.5 Grafos circulantes; 1.6 Grafos de Johnson.
Viernes 23 de marzo: Repaso 1.6; 1.7 Grafos línea; 1.8 Grafos Planos.
Lunes 26 de marzo: 2.1 Grupo de Permutaciones; 2.2 Contando;
Miércoles 28 de marzo: Media clase Práctico I; Repaso y comienzo de 2.3 Grafos Asimétricos.
Viernes 30 de marzo: Repaso de 2.3 y cierre de este punto: Grafos Asimétricos.
Lunes 9 de abril: 2.4 Órbitas de pares. 2.5 Primitivismo.
Miércoles 11 de abril: Práctico (especialmente Ejercicio 6 del Pr. 1); y Teórico cierre de 2.5 Primitivismo.
Viernes 13 de abril: 2.6 Primitivismo y Conectividad, se cierra el Capítulo 2.
Lunes 16 de abril: 3.1 Grafos Vértice-transitivos; 3.2 Grafos Arista-transitivos.
Miércoles 18 de abril: Práctico 2 (Ejercicio 1, Ejercicio 2); Teórico: Cierre de 3.2 Grafos arista-transitivos (presentación de slices con resumen).
Viernes 20 de abril: 3.3 Conectividad por aristas; 3.4 Conectividad por vértices.
Lunes 23 de abril: feriado.
Miércoles 25 de abril: Práctico.
Viernes 27 de abril: 3.4 Conectividad por Vértices.
Lunes 30 de abril: Final de Conectividad por vértices. 3.5 Pareos.
Miércoles 2 de mayo: Clase comenzó media hora tarde. Discusión de un punto teórico. Práctico.
Viernes 4 de mayo: 3.5 Pareos.
Lunes 7 de mayo: 3.6 Caminos y ciclos hamiltonianos. 3.7 Grafos de Cayley.
Miércoles 9 de mayo: Práctico 3.
Viernes 11 de mayo: 3.8 Directed Cayley graphs with no hamiltonian cycles. 3.9 Retracciones.
Lunes 14 de mayo: Exposición de Ramón Sellanes: “On the shortest spanning subtree of a Graph and the traveling salesman problem”
Miércoles 16 de mayo: no hay clase.
Viernes 18 de mayo: Exposición de Telmo Acosta: “An edge but not vertex transitive cubic graph”
Lunes 21 de mayo: feriado
Miércoles 23 de mayo: No hay clase.
Viernes 25 de mayo: Exposición de Florencia Cubría: “A construction for vertex transitive graphs”
Lunes 28 de mayo: 3.9 Retracciones.
Viernes 1 de junio: Exposición de Cecile Mezzera: “A 27 vertex group that is vertex transitive and edge transitive but nos 1-transitive”
Lunes 4 de junio: 3.10 Trasposiciones y reapso del Teorema central de Retracciones.
Miércoles 6 de junio: Exposición de Natalia Flores: “Un grafo no hamiltoniano”
Viernes 8 de junio: 8.1 Matriz de Adyacencia; 8.2 Matriz de Incidencia
Lunes 11 de junio: 8.2 Matriz de Incidencia; 8.3 Matriz de Incidencia de un grafo orientado;
Miércoles 13 de junio: 8.3 Matriz de Incidencia de un grafo orientado; 8.4 Matrices Simétricas (repaso)
Viernes 15 de junio: 8.5 Vectores propios en grafos; 8.6 Matrices semidefinidas positivas.
Lunes 18 de junio: Exposición de Felipe Negreira: “Teorema de Hoffman-Singelton”
Miércoles 20 de junio: 8.6 Matrices semidefinidas positivas.
Viernes 22 de junio: 8.7 Funciones subarmóincas.
Lunes 25 de junio: 8.8 El Teorema de Perrón Frobeniüs. 8.12 Descomposición espectral.
Miércoles 27 de junio: 8.12 Descomposición espectral.. 8.13 Funciones racionales;
Viernes 29 de junio: 8.13 Funciones racionales. 9.1 Interlacing
Lunes 2 de Julio: Exposición de Laura Gatti y Martín Zubeldía ”On the multiplicity of the eigenvalues of a graph”
Miércoles 4 de Julio: Exposición de Laura Gatti y Martín Zubeldía ”On the multiplicity of the eigenvalues of a graph”
Viernes 6 de Julio: 13.1 La Matriz Laplaciana.
Lunes 9 de Julio: Exposición de Celia Sena: “A Novel Slow Coherency Based Graph Theoretic Islanding Strategy”
Miércoles 11 de Julio: Exposición de Marcos Barrios: ”Almost all trees are cospectral”
Viernes 13 de Julio: Exposición de Gustavo Rama “Constructing cosprectral graphs”
Direcciones de correo electrónico:
marclan@fing.edu.uy marclan@cmat.edu.uy
Actualizado el 23 de junio de 2012