TEORÍA DE LOS GRAFOS

PROBLEMA DE LOS PUENTES DE KÖNINGSBERG. DOS ISLAS QUE SE ENCUENTRAN EN EL RÍO PREGEL EN KÖNINGSBERG (ANTES PRUSIA ORIENTAL, LLAMADO AHORA KALININGRADO) ESTÁN CONECTADAS ENTRE SI Y CON LA MARGEN DEL RÍO POR PUENTES COMO SE INDICA EN LA SIGUIENTE FIGURA:
1. EL PROBLEMA CONSISTE EN PARTIR DESDE CUALQUIER LUGAR (A, B, C, O D), SEGUIR CAMINANDO Y PASAR POR CADA UNO DE LOS PUENTES UNA SOLA VEZ Y LUEGO VOLVER AL PUNTO DE PARTIDA. A UN RECORRIDO DE ESTE TIPO SE LLAMA "CIRCUITO DE EULER". TAL RECORRIDO PUEDE REPRESENTARSE MEDIANTE UN GRAFO COMO SIGUE:
  1. GRAFO ESTRUCTURAS DE DATOS NO LINEALES QUE TIENEN UNA NATURALEZA DINÁMICA
    1. GRAFOS DIRIGIDOS
      1. UN GRAFO EN EL CUAL TODA ARISTA ES DIRIGIDA SE DENOMINARÁ "DIGRAFO" O BIEN "GRAFO DIRIGIDO". UN GRAFO DIRIGIDO O DÍGRAFO CONSISTE DE UN CONJUNTO DE VÉRTICES V Y UN CONJUNTO DE ARCOS A.
    2. GRAFOS NO DIRIGIDOS
      1. UN GRAFO NO DIRIGIDO, G CONSTA DE UN CONJUNTO V DE VÉRTICES O NODOS Y UN CONJUNTO E DE LADOS, (RAMAS O ARISTAS) TALES QUE CADA LADO E E ESTA ASOCIADO A UN PAR NO ORDENADO DE VÉRTICES.
    3. LAS APLICACIONES MÁS IMPORTANTES DE LOS GRAFOS SON LAS SIGUIENTES: · RUTAS ENTRE CIUDADES. · DETERMINAR TIEMPOS MÁXIMOS Y MÍNIMOS EN UN PROCESO. · FLUJO Y CONTROL EN UN PROGRAMA.
      1. TIPOS DE GRAFOS
        GRAFO SIMPLE: O SIMPLEMENTE GRAFO ES AQUEL QUE ACEPTA UNA SOLA ARISTA UNIENDO DOS VÉRTICES CUALESQUIERA.
        MULTIGRAFO: ES EL QUE ACEPTA MÁS DE UNA ARISTA ENTRE DOS VÉRTICES. ESTAS ARISTAS SE LLAMAN MÚLTIPLES O LAZOS (LOOPS EN INGLÉS).
        PSEUDOGRAFO: SI INCLUYE ALGÚN LAZO.
        GRAFO ORIENTADO: GRAFO DIRIGIDO O DIGRAFO. SON GRAFOS EN LOS CUALES SE HA AÑADIDO UNA ORIENTACIÓN A LAS ARISTAS, REPRESENTADA GRÁFICAMENTE POR UNA FLECHA.
        GRAFO ETIQUETADO: GRAFOS EN LOS CUALES SE HA AÑADIDO UN PESO A LAS ARISTAS (NÚMERO ENTERO GENERALMENTE) O UN ETIQUETADO A LOS VÉRTICES.
        GRAFO ALEATORIO: GRAFO CUYAS ARISTAS ESTÁN ASOCIADAS A UNA PROBABILIDAD.
        HIPERGRAFO: GRAFOS EN LOS CUALES LAS ARISTAS TIENEN MÁS DE DOS EXTREMOS, ES DECIR, LAS ARISTAS SON INCIDENTES A 3 O MÁS VÉRTICES.
        GRAFO INFINITO: GRAFOS CON CONJUNTO DE VÉRTICES Y ARISTAS DE CARDINAL INFINITO
        GRAFO PLANO: LOS GRAFOS PLANOS SON AQUELLOS CUYOS VÉRTICES Y ARISTAS PUEDEN SER REPRESENTADOS SIN NINGUNA INTERSECCIÓN ENTRE ELLOS. PODEMOS ESTABLECER QUE UN GRAFO ES PLANO GRACIAS AL TEOREMA DE KURATOWSKI
        GRAFO REGULAR: UN GRAFO ES REGULAR CUANDO TODOS SUS VÉRTICES TIENEN EL MISMO GRADO DE VALENCIA.
    4. UN GRAFO SE REPRESENTA GRÁFICAMENTE COMO UN CONJUNTO DE PUNTOS LLAMADOS "VÉRTICES O NÓDOS" UNIDOS POR LÍNEAS LLAMADAS "ARISTAS"
      1. UN GRAFO ESTÁ COMPUESTO POR DOS CONJUNTOS FINITOS. UN CONJUNTO DE |A| ARISTAS, UN CONJUNTO DE |V| VÉRTICES J ES LA RELACIÓN DE INCIDENCIA, QUE ASOCIA A CADA ELEMENTO DE |A| UN PAR DE ELEMENTOS DE |V| SE DENOTA G= { A, V, J}
        UN CAMINO ES UNA SECUENCIA DE VÉRTICES DENTRO DE UN GRAFO TAL QUE EXISTA UNA ARISTA ENTRE CADA VÉRTICE Y EL SIGUIENTE.
        UN ÁRBOL ES UN GRAFO EN EL QUE CUALESQUIERA DOS VÉRTICES ESTÁN CONECTADOS POR EXACTAMENTE UN CAMINO. UN BOSQUE ES UNA UNIÓN DISJUNTA DE ÁRBOLES. UN ÁRBOL A VECES RECIBE EL NOMBRE DE ÁRBOL LIBRE.
        UN ÁRBOL ES UN GRAFO SIMPLE NO DIRIGIDO G QUE SATISFACE: 1. G ES CONEXO Y NO TIENE CICLOS . 2. G NO TIENE CICLOS Y, SI SE AÑADE ALGUNA ARISTA SE FORMA UN CICLO. 3. G ES CONEXO Y SI SE LE QUITA ALGUNA ARISTA DEJA DE SER CONEXO. 4. G ES CONEXO Y EL GRAFO COMPLETO DE 3 VÉRTICES NO ES UN MENOR DE G. 5. DOS VÉRTICES CUALQUIERA DE G ESTÁN CONECTADOS POR UN ÚNICO CAMINO SIMPLE.
        ÁRBOL DIRIGIDO ES UN GRAFO DIRIGIDO QUE SERÍA UN ÁRBOL SI NO SE CONSIDERARAN LAS DIRECCIONES DE LAS ARISTAS.
        UN ÁRBOL RECIBE EL NOMBRE DE ÁRBOL CON RAÍZ SI UN VÉRTICE HA SIDO DESIGNADO RAÍZ.
        UN ÁRBOL ETIQUETADO ES UN ÁRBOL EN EL QUE CADA VÉRTICE TIENE UNA ÚNICA ETIQUETA.
        UN ÁRBOL REGULAR U HOMOGÉNEO ES UN ÁRBOL EN EL QUE CADA VÉRTICE TIENE EL MISMO GRADO.
        ARISTAS: SON LAS LÍNEAS CON LAS QUE SE UNEN LOS VÉRTICES DE UN GRAFO.
        ARISTAS ADYACENTES: 2 ARISTAS SON ADYACENTES SI CONVERGEN EN EL MISMO VÉRTICE.
        ARISTAS PARALELAS: SON DOS ARISTAS CONJUNTAS SI EL VÉRTICE INICIAL Y FINAL SON EL MISMO.
        ARISTA CÍCLICAS: ES LA ARISTA QUE PARTE DE UN VÉRTICE PARA ENTRAR EN SÍ MISMO.
        CRUCE: SON 2 ARISTAS QUE CRUZAN EN UN MISMO PUNTO.
        VÉRTICES: LOS VÉRTICES SON LOS ELEMENTOS QUE FORMAN UN GRAFO. CADA UNO LLEVA ASOCIADA UNA VALENCIA CARACTERÍSTICA SEGÚN LA SITUACIÓN, QUE SE CORRESPONDE CON LA CANTIDAD DE ARISTAS QUE CONFLUYEN EN DICHO VÉRTICE.

Next up

TEORÍA DE LOS GRAFOS

Description

Resource summary

Media attachments

Similar

	Created by Alex Castillo about 7 years ago