Unidad 6 Matematicas Discretas

3085 palabras 13 páginas
Instituto Tecnológico Superior de los Ríos
Balancán, Tabasco

NOMBRE DEL ALUMNO: EDGAR DIAZ VELASCO

CARRERRA: ING. EN SISTEMAS COMPUTACIONALES

CATEDRATICO: DANY CAMBRANO ARCOS

UNIDAD 6
TEORIA DE GRAFOS

FECHA: 12 DE NOVIEMBRE DEL 2012

INDICE
Contenido
UNIDAD 6 3
TEORIA DE GRAFOS 3
COMPONENTES DE UN GRAFO (VÉRTICES, ARISTAS, BRAZOS, VALENCIA) 3
TIPOS DE GRAFOS (SIMPLES, COMPLETOS, BIPARTIDOS, PLANOS, CONEXOS, PONDERADOR) 4
REPRESENTACION DE LOS GRAFOS 6
REPRESENTACIÓN MATEMÁTICA DE LOS GRAFOS 7
REPRESENTACIÓN COMPUTACIONAL DE LOS GRAFOS 8
EL CAMINO MAS CORTO 9
ARBOLES 11
COMPONENTES (RAIZ, HOJA, PADRE, HIJO, DESCENDIENTES, ANCENTROS) 11
PROPIEDADES DE LOS ARBOLES 12
CLASIFICACION
…ver más…
Grafos Ponderados:
Son aquellos en donde a las aristas se les asigna un valor al cual se le llama ponderación y que podría representar la distancia que hay de un nodo a otro, o bien el costo de transportarse de una ciudad a otra.

REPRESENTACION DE LOS GRAFOS
Representación Matricial
El uso de matrices para representar sistemas de ecuaciones, relaciones o grafos permite una rápida y clara manipulación de la información, así como el determinar algunas propiedades de los grafos que de otra manera serian más difíciles de obtener. Además de esto se tiene que en la computadora es más fácil el manejo de matrices, ya que se pueden tratar como arreglos o listas doblemente ligadas.
Matriz de adyacencia (Ma)
Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y columnas de la matriz. Se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.
Ma = a b c d e a 1 1 1 0 1 b 1 0 1 1 0 c 1 1 1 1 0 d 0 1 1 0 1 e 1 0 0 1 0

Matriz de incidencia (Mi)
Mi = r1 r2 r3 r4 r5 r6 r7 r8 a 1 1 0 0 1 1 1 0 5 b 1 1 1 0 0 0 0 0 3 c 0 0 0 0 0 0 1 0 1 d 0 0 0 1 0 0 0 0 1 e 0 0 0 1 1 1 0 1 4 2 2 1 2 2 2 2 1
En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

REPRESENTACIÓN MATEMÁTICA DE LOS

Documentos relacionados

  • Matematicas Discretas. Unidad 5. (Relaciones. 5.1 Conceptos Basicos Hasta 5.5 Aplicaciones De Las Relaciones Y Las Funciones En La Computadora
    1777 palabras | 8 páginas
  • Unidad 6 desarrollo humano
    1888 palabras | 8 páginas
  • matematicas aplicadas 5ta unidad
    5069 palabras | 21 páginas
  • Matematica discreta
    1907 palabras | 8 páginas
  • Funciones matemáticas discretas ing sistemas
    2332 palabras | 10 páginas
  • Tipos de relaciones.(matematicas discretas)
    898 palabras | 4 páginas
  • MAtematicas 6
    2295 palabras | 10 páginas
  • matematica Discreta, ejercicio
    5904 palabras | 24 páginas
  • Ciclos y Arboles - matematicas Discretas
    1740 palabras | 7 páginas
  • Matematicas Discretas
    2094 palabras | 9 páginas