.. -*- coding: utf-8 -*-



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