Introducción a la teoría de gráficas

Introducción a la teoría de gráficas

1. Digráfica

   • También llamada gráfica orientada o gráfica dirigida. Consta de nodos y aristas dirigidas, es decir con una fecha.
   • Tipo de digráficas
     • Conectada
       • Aquella en la que existe al menos un paseo dirigido entre cualquier par de nodos.
     • Isomórficas
       • Dos gráficas son isomórficas si: ~Sus gráficas no dirigidas son        isomórficas. ~La dirección de las líneas es la    misma.
     • Simple
       • No contiene bucles ni líneas paralelas, pero si puede tener líneas recurrentes
     • Asimétrica
       • Asimétrica. Tiene máximo una línea dirigida entre un par de nodos y sin bucles. Al menos un arco no tiene un arco recurrente.
       • Completa
         • Asimétrica completa. También se le llama torneo completo. Tiene exactamente una línea dirigida entre cada par de nodos. Tiene (n(n-1))/2 líneas
     • Simétrica
       • Tiene puros arcos recurrentes.
     • Completa
       • También llamada simétrica completa. Para todo par de vértices existe una línea de ida y regreso. No tiene bucles.
     • Regular
       • Todos los nodos tienen el mismo número de grado tanto interno como externo y será n-1.
     • Balanceada
       • Los grados interno y externo de un nodo son iguales
     • Pseudográfica
       • Puede tener líneas paralelas, recurrentes y bucles.
     • Multidigráfica
       • Debe tener líneas paralelas pero no bucles.
   • Paseos y trayectorias
     • Paseos
       • Dirigido
         • Secuencia alterna de vértices y líneas donde se respeta la dirección de los arcos. Se puede repetir nodos y arcos.
         • Abierto
           • Trayectoria dirigida
             • Paseo dirigido abierto. No se puede repetir nodos ni arcos. No se puede pasar por bucles.
         • Cerrado
           • Circuito dirigido
             • Paseo dirigido cerrado. Sólo se repetir el primer y último nodo. Se puede pasar por bucles.
       • Semipaseo
         • Paseo sin considerar la dirección de los arcos.
   • Tipos de líneas
     • Bucle
       • También llamado loop o lazo. Línea dirigida dónde el nodo inicial y terminal es el mismo.
     • Paralelas
       • Líneas dirigidas que comparten el mismo nodo inicial y terminal, con el mismo sentido.
     • Recurrentes
       • Líneas dirigidas que comparten nodos iniciales y terminales, pero cada una va en sentido contrario a la otra.
   • Tipos de nodos
     • Aislado
       • Si el grado interno y externo son 0
     • Terminal
       • Si el grado externo es 0 y el interno mayor a 0
     • Inicial
       • Si el frado interno es 0 y el externo mayor a 0
     • Intermedio
       • Si no es inicial o final. También llamado de paso. 
     • Colgante
       • Si su grado es uno. d+(Vi)+d-(Vi)=1
   • Grado
     • Externo
       • El grado externo de un nodo es el número de líneas que salen de este. Se denota por d+(Vi)
     • Interno
       • El grado interno de un nodo es el número de líneas que llegan a este. Se denota por d-(Vi)

2. Árboles

   • Es una gráfica conectada sin circuitos
   • Binario
     • Aquel donde cada nodo tiene uno o dos hijos. El grado de sus nodos es 1, 2 o 3.
   • Estrictamente Binario
     • Tiene un solo nodo de grado dos (la raíz) y el resto de grado 3 o 1 (colgantes).
   • Arborescencia
     • Árbol con dirección. Debe existir la raíz y al menos una trayectoria dirigida de la raíz hacia a los demás nodos.
   • Excentricidad
     • Longitud del camino que une dos nodos. Denotado por E(Vi)
     • Centro
       • Nodo o nodos cuya excentricidad sea la mínima.
   • Bosque
     • Conjunto de árboles

3. Otros conceptos

   • Estos conceptos son aplicables a gráficas dirigidas y no dirigidas.
   • Longitud
     • En un paseo, es el número de líneas que contiene este
     • Distancia
       • Longitud del paseo mínimo que une dos nodos.
   • Cortes
     • Puente
       • También llamada línea de corte. Si al eliminarse una línea la gráfica se desconecta es un puente.
     • Corte
       • Si se elimina un conjunto de aristas y la gráfica queda desconectada es un corte.
       • Longitud del corte
         • Aristas que conforman el corte.
         • Distancia del corte
           • Mínimo de líneas que conforman el corte.
     • Punto de articulación
       • Si la gráfica contiene un nodo que al eliminarlo se desconecta, es un punto de articulación.
     • Bloque
       • También llamado gráfica conectada o componente. Gráfica que no contiene puntos de articulación.
     • Gráfica separable
       • Gráfica que contiene varios puntos de articulación

Imágenes y archivos del mapa