Ejercicios

1.

• ¿Cuales de los siguientes grafos son planos: graphs.HouseXGraph, graphs.DesarguesGraph, graphs.OctahedralGraph y graphs.DiamondGraph ? ¿Cuáles tienen circuitos eulerianos?
• ¿Qué propiedades especiales tienen los grafos de las familias graphs.StarGraph y graphs.CircularLadderGraph ? ¿son planos? ¿son árboles?
• ¿Para qué valores de k el grafo graphs.CubeGraph(k) tiene un circuito euleriano?
• ¿Para qué valores de k el grafo graphs.CompleteGraph(k) tiene un circuito euleriano?
• ¿Para qué valores de k el grafo graphs.CompleteGraph(k) es plano? Conjetura una respuesta, y confirma la respuesta buscando en interneto en la biblioteca.

2. Subgrafo inducido

Dado un grafo G con un conjunto de vértices V, y un subconjunto V’ de V, el subgrafo de G inducido por V’ es el grafo con V’ como vértices, y sólo aquellas aristas que estaban en G.

• Encuentra tres subgrafos inducidos de 6 vértices del grafo graphs.CubeGraph(3) no isomorfos entre sí.
• ¿Cuántos subgrafos inducidos de 7 vértices tiene el grafo graphs.CubeGraph(3) no isomorfos entre sí?
• Encuentra un subgrafo inducidos del grafo graphs.CubeGraph(4) que sea isomorfo al grafo graphs.CubeGraph(3)

3. Contar grafos

¿Cuántos posibles grafos existen con un conjunto de vértices dado de tamaño k? ¿Cuántos digrafos (grafos dirigidos)?

¿Cuántos posibles grafos no isomorfos existen con exactamente k vértices, para k<=7?

¿Cuántos posibles digrafos conexos no isomorfos existen con 4 vértices ?

¿Cuántos grafos hay con 5 vértices que no sean planos? Dibújalos todos:

Referencia: http://es.wikipedia.org/wiki/Grafo_plano

4. Coloraciones de grafos

Una coloración de un grafo es una asignación de un color a cada vértice del grafo de modo que dos vértices adyacentes tienen asignados colores distintos. Las coloraciones más interesantes son las que tienen menor número de colores. Un conocido teorema afirma que todos los grafos planos se pueden colorear con a lo sumo 4 colores.

• Explora la ayuda de los métodos coloring y plot de los grafos para conseguir dibujar grafos junto con una coloración que tiene el mínimo número de colores.
• Encuentra grafos con k vértices que no se puedan colorear con menos de j colores, para j<k y k hasta 6.
• ¿Cuál es el número cromático del grafo graphs.LollipopGraph(a,b) ?
• ¿Cuál es el número cromático del grafo graphs.BarbellGraph(a,b) ? ¿Cuál es su número de vértices?

5. Grafo de divisores

Dada una lista de números S, construye el grafo de divisores de S, cuyos vértices son los números de S, y que tiene una arista desde j hasta k si y sólo si j es divisor de k ó j es divisor de k.

6.

Calcula el número de aristas del grafo de divisores para las listas S de la forma range(2,k), para distintos valores de k y dibújalas en una gráfica.

7.

El grafo de divisores de una lista de primos no tiene ninguna arista.

El grafo de divisores de una lista de potencias de 2 de tamaño k tiene todas las aristas posibles (es decir, k*(k+1)/2 ).

• ¿Puedes encontrar un grafo con k vértices y 2*k aristas, para k=10, 15 y 20?

Indicación: usa la fuerza (bruta).

Referencia: http://arxiv.org/abs/math/0606483