Teorias De Grafos En Informatica

2809 palabras 12 páginas
MATEMATICA APLICACIONES DE LA TEORIA DE GRAFOS EN LA INFORMÁTICA
CONTENIDO
Introducción
Proposito
Formulacion del problema y justificacion
Objetivos
Grafos
Historia
Definicion
Tipos de grafos
Modelos de los grafos
Aplicaciones
Arboles
Arbol Binario
Arbol de decision y aplicaciones
Software algoritmos voraces

INTRODUCCIÓN
La teoría de grafos también llamada teoría de las gráficas, es una disciplina que es importante tanto para las matemáticas como para la teoría de la computación. En esta última disciplina todo es manejado a través de los grafos que son estructuras discretas que constan de puntos y de líneas que se conectan entre sí. Es importante saber que existen diferentes tipos de grafos, que se distinguen entre sí
…ver más…
Cada sentencia se representa por un vértice, y hay una arista de un vértice a un segundo si la sentencia representada por el segundo vértice no puede ejecutarse hasta la sentencia representada por el primero se ha ejecutado.
Diseño de bases de datos
Empresa:
Vértices: Empleados, trabajos, departamentos y Empresa.
Enlaces: La comunicación.

APLICACIONES INFORMÁTICAS EN GRAFOS BIPARTITOS
Comparación de archivos de computador, utilizando el problema de la Longest Common Subsequence (LCS), en español Subsecuencia Común Más Larga.
Dadas dos palabras X e Y sobre un alfabeto finito cualquiera, pretende encontrar cuál es el largo máximo que puede tener una palabra que sea subsecuencia de X e Y simultáneamente.
El largo de una LCS se usa comúnmente como criterio de comparación de palabras, pues está relacionada con la cantidad de "pasos" necesarios para ir de una palabra a la otra mediante operaciones de inserción, eliminación y reemplazo de caracteres.
Todopar de palabras puede representarse convenientemente como un grafo bipartito donde los arcos unen a los caracteres coincidentes de ambas palabras.
Un matching en un grafo arbitrario (no necesariamente bipartito) es cualquier conjunto de arcos que no comparten extremos; un PM es un matching en donde los arcos no se cruzan ni comparten extremos. Así, calcular la LCS entre dos palabras no es más que calcular el matching planar de costo máximo del grafo bipartito

Documentos relacionados

  • Antropologia y la salud publica
    3492 palabras | 14 páginas
  • Monografia Teoria de Grafos
    3010 palabras | 13 páginas
  • La pobreza en guatemala
    2016 palabras | 9 páginas
  • La comunicación y conflictos bélicos
    1044 palabras | 5 páginas
  • Modelos de argumentos apodícticos
    1657 palabras | 7 páginas
  • Moneda banca y credito
    4465 palabras | 18 páginas
  • La informatica y su relacion con la matematica
    1762 palabras | 8 páginas
  • Tipos y diseños de investigacion
    1018 palabras | 5 páginas
  • Ciencias De La Computación
    2092 palabras | 9 páginas
  • Computacion
    2149 palabras | 9 páginas