TEORIA DE GRAFOS

Páginas: 8 (1943 palabras) Publicado: 29 de junio de 2014








INTRODUCCIÓN----------------------------------------------------------------------------------- 2

CONCLUSIONES----------------------------------------------------------------------------------- 3
REPRESENTACIÓN MATRICIAL DE GRAFOS-------------------------------------------- 4

MATRIZ DE ADYACENCIA E INCIDENCIA------------------------------------------------ 5CAMINOS-------------------------------------------------------------------------------------------- 6

EJERCICIOS----------------------------------------------------------------------------------------- 9

BIBLIOGRAFÍA------------------------------------------------------------------------------------15










En el presente trabajo de investigación para la materia de Matemáticas Discretasse desarrollará el tema TEORIA DE GRAFOS correspondiente a la unidad de esta asignatura.




Además de conceptos, teoremas y definiciones se encontrará con ejercicios, graficas y típicos ejemplos relacionados al tema antes mencionado.




Esperando así que este trabajo de investigación sirva en un futuro no muy lejano a otras personas o compañeros estudiantes.





1. Se tuvocomo conclusión que la representación matricial de X depende del ordenamiento de los nodos.
2. La matriz de adyacencia e incidencia es la misma en la relación E en V.
3. Si no hay mas de 1 arista entre un par de nodos se dice que es un camino simple.
4. La longitud de un camino en G es igual a la suma de las longitudes de las aristas del camino.
5. Un camino mas corto de un punto a otro puededeterminarse como sigue: Para cada vértice l de t, sea l(t) la longitud del camino mas corto de entre todos los paseos de a hasta t que no incluyen ningún otro vértice de t.
6. Un grafo ponderado es la grafica a la que se le asignan pesos a cada arista.
7. Cualquier grafo es homeomorfo a sí mismo.
8. La locura instantánea trata de colocar los cubos en una columna de 4 de forma que en cada lado deesta aparezcan los 4 colores.
9. El problema de Königsberg se refiere a que se quiso encontrar 1 punto inicial para poder pasear por toda la ciudad, cruzando por cada puente (7) exactamente 1 vez y regresar a dicho punto.




Una representación diagramatica de una grafica tiene una utilidad limitada. Mas aún, una representación de estas solo es posible cuando el numero de nodos y aristas espequeño.


Se pueden usar operaciones bien conocidas del álgebra matricial para calcular trayectos, ciclos y otras características de una grafica.


Dada una digrafica simple G = , es necesario suponer alguna clase de ordenamiento de los nodos de la grafica en el sentido de que un nodo particular se llama primer nodo, otro, el segundo nodo y así sucesivamente. La relpresentación matricial deG depende del ordenamiento de los nodos.


Definición: Sea G = una digrafica simple en la cual V= {v1,v2,...,vn} y los nodos se supone que estan ordenados de v1 a vn. Una matriz A n X n cuyos elementos aij estan dados por

1 Si Є E
0 De lo contrario se llama una matriz de adyacencia de la grafica G.



Recuerdese que la matriz de adyacencia es la misma que lamatriz de incidencia de la relación E en V. Cualquier elemento de la matriz de adyacencia es 0 o 1. cualquier matriz cuyos elementos son 0 o 1 se llama matriz de bit o boleana. Notese que el i-esimo renglón de la matriz de adyacencia esta determinada por las aristas que se originan en el nodo vi. El numero de elementos en el i-esimo renglón cuyo valor es de 1 es igual a los grados de salida del nodovi. De manera similar, el numero de elementos cuyo valor es 1 en una columna, por ejemplo la j-esima columna, es igual al grado de entrada del nodo vj . una matriz de adyacencia define por completo a una digrafica simple.



Para una digrafica dada G = , una matriz de adyacencia depende del ordenamiento de los elementos de V. Para diferentes ordenamientos de los elementos de V se obtienen...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Teoria de Grafos
  • teoria de grafos
  • teoria de grafos
  • teoria de grafos
  • Teoria de Grafos
  • teoria de grafos
  • teoria de grafos
  • Teoria de grafos

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS