Flexión

TEORIA DE GRAFOS
http://es.wikipedia.org/wiki/Grado_%28teor%C3%ADa_de_grafos%29
http://es.wikipedia.org/wiki/Grafo
http://dns.uls.cl/~ej/fit_2009/teo_fit_2009/Lect_2009/Fit_1998/pagina_n4.htm
http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/grafo13.gif










1. Enumera y describe brevemente con tus palabras todos los conceptos definidos en el documento sobreteoría de grafos. Realiza un esquema que categorice dichos conceptos por niveles de importancia.

Nivel 1:
Grafos: conjunto de vértices en el espacio unidos por una serie de aristas.
Subgrafos: parte del grafo que por sí misma forma otro grafo, denotado G´ ⊆ G
Operaciones con grafos: método de expresar un grafo como composición más simple de otros grafos con fin de facilitar el mismo.Isomorfismos de grafos: dos grafos estructuralmente iguales.

Nivel 2:
Grado de un vértice: dícese del número de aristas que inciden a un vértice, considerando los bucles como dos aristas incidentes.
Grafos regulares: dícese del grafo cuyos vértices tienen el mismo grado.
Grafos completos: un grafo simple de n vértices en el que todos esos vértices es adyacente a cada uno de los restantes n-1.Nivel 3:
Grafos etiquetados: se obtiene dándole a cada arista del grafo un peso o etiqueta siendo esta un número real.
Subgrafo maximal: el subgrafo con el mismo conjunto de vértices que el grafo original. V=V´
Subgrafo inducido: se denomina subgrafo inducido por un subconjunto de vértices al subgrafo que tiene las aristas del grafo que solamente inciden con los vértices de V´. Y se denominasubgrafo inducido por un subconjunto de aristas al subgrafo que tiene por vértices a todos esos vértices que son extremos de las aristas A´.
Unión del grafo: dícese del nuevo grafo creado al juntar los vértices y las aristas de dos o más grafos, poniendo solo una vez aquellos vértices y aristas que se repitan en ambos grafos.
Intersección del grafo: dícese del nuevo grafo creado por los vértices,aristas y función de incidencias repetidos entre dos o más grafos.
Suma directa: dícese del conjunto formado por las aristas de ambos grafos más las aristas adicionales necesarias para enlazar cada vértice de G1 con cada vértice de G2.
Suma binaria de grafos: dícese del conjunto formado por las aristas que pertenecen a G1 o a G2, pero no a ambos a la vez.
Algoritmo de verificación de isomorfia:dícese del algoritmo que determina la isomorfia de los grados G y G´ comparando sucesivamente la matriz de adyacencia de G con las permutaciones de la matriz de adyacencia de G´.
Matriz de adyacencia: la matriz cuadrada de orden n, donde n es el número de vértices de la matriz, tal que cada elemento es el número de aristas que enlazan los vértices vi y vj, considerando un bucle como aristadoble.
Matriz de incidencia: dícese de la matriz de orden nxm dada por Mi(G)=[xij], contando cada arista y siendo los bucles doble.
NIVEL 4:
Grafo simple, multígrafo y pseudografo: grafo simple es aquel que posee aristas paralelas, el multígrafo contiene al menos dos aristas paralelas, y por último, se considera pseudgrafo a aquel que contenga al menos un bucle.
Grafos etiquetados: dícese delgrafo completamente definido por un conjunto de vértices, un conjunto de aristas, y la función de incidencia y de pesos que le corresponda.
Complemento de un grafo: Dado un grafo simple A de n vértices, se considera complemento del grafo A, al grafo A´ formado por n vértices y por las aristas que no figuren en A. Entonces A y A´ se denominarán como grafos complementarios


2. Describe qué tiposde ejercicios/problemas aparecen en el documento y qué métodos se describen en la teoría para su resolución. Propón dos enunciados de posibles ejercicios/problemas relacionados con el contenido del documento, diferentes a los del listado final, indicando qué método utilizarías para resolver cada uno.
- Dados diferentes grafos con sus respectivos vértices, aristas y funciones de incidencia,...