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

Annotations:

• También llamada gráfica orientada o gráfica dirigida. Consta de nodos y aristas dirigidas, es decir con una fecha.

1. Tipo de digráficas
   1. Conectada

      Annotations:

      • Aquella en la que existe al menos un paseo dirigido entre cualquier par de nodos.
   2. Isomórficas

      Annotations:

      • 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.
   3. Simple

      Annotations:

      • No contiene bucles ni líneas paralelas, pero si puede tener líneas recurrentes
   4. Asimétrica

      Annotations:

      • 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.
      1. Completa

         Annotations:

         • 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
   5. Simétrica

      Annotations:

      • Tiene puros arcos recurrentes.
   6. Completa

      Annotations:

      • También llamada simétrica completa. Para todo par de vértices existe una línea de ida y regreso. No tiene bucles.
   7. Regular

      Annotations:

      • Todos los nodos tienen el mismo número de grado tanto interno como externo y será n-1.
   8. Balanceada

      Annotations:

      • Los grados interno y externo de un nodo son iguales
   9. Pseudográfica

      Annotations:

      • Puede tener líneas paralelas, recurrentes y bucles.
   10. Multidigráfica

       Annotations:

       • Debe tener líneas paralelas pero no bucles.
2. Paseos y trayectorias
   1. Paseos
      1. Dirigido

         Annotations:

         • Secuencia alterna de vértices y líneas donde se respeta la dirección de los arcos. Se puede repetir nodos y arcos.
         1. Abierto
            1. Trayectoria dirigida

               Annotations:

               • Paseo dirigido abierto. No se puede repetir nodos ni arcos. No se puede pasar por bucles.
         2. Cerrado
            1. Circuito dirigido

               Annotations:

               • Paseo dirigido cerrado. Sólo se repetir el primer y último nodo. Se puede pasar por bucles.
      2. Semipaseo

         Annotations:

         • Paseo sin considerar la dirección de los arcos.
3. Tipos de líneas
   1. Bucle

      Annotations:

      • También llamado loop o lazo. Línea dirigida dónde el nodo inicial y terminal es el mismo.
   2. Paralelas

      Annotations:

      • Líneas dirigidas que comparten el mismo nodo inicial y terminal, con el mismo sentido.
   3. Recurrentes

      Annotations:

      • Líneas dirigidas que comparten nodos iniciales y terminales, pero cada una va en sentido contrario a la otra.
4. Tipos de nodos
   1. Aislado

      Annotations:

      • Si el grado interno y externo son 0
   2. Terminal

      Annotations:

      • Si el grado externo es 0 y el interno mayor a 0
   3. Inicial

      Annotations:

      • Si el frado interno es 0 y el externo mayor a 0
   4. Intermedio

      Annotations:

      • Si no es inicial o final. También llamado de paso. 
   5. Colgante

      Annotations:

      • Si su grado es uno. d+(Vi)+d-(Vi)=1
5. Grado
   1. Externo

      Annotations:

      • El grado externo de un nodo es el número de líneas que salen de este. Se denota por d+(Vi)
   2. Interno

      Annotations:

      • El grado interno de un nodo es el número de líneas que llegan a este. Se denota por d-(Vi)

Annotations:

• Es una gráfica conectada sin circuitos

1. Binario

   Annotations:

   • Aquel donde cada nodo tiene uno o dos hijos. El grado de sus nodos es 1, 2 o 3.
2. Estrictamente Binario

   Annotations:

   • Tiene un solo nodo de grado dos (la raíz) y el resto de grado 3 o 1 (colgantes).
3. Arborescencia

   Annotations:

   • Á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.
4. Excentricidad

   Annotations:

   • Longitud del camino que une dos nodos. Denotado por E(Vi)
   1. Centro

      Annotations:

      • Nodo o nodos cuya excentricidad sea la mínima.
5. Bosque

   Annotations:

   • Conjunto de árboles

Annotations:

• Estos conceptos son aplicables a gráficas dirigidas y no dirigidas.

1. Longitud

   Annotations:

   • En un paseo, es el número de líneas que contiene este
   1. Distancia

      Annotations:

      • Longitud del paseo mínimo que une dos nodos.
2. Cortes
   1. Puente

      Annotations:

      • También llamada línea de corte. Si al eliminarse una línea la gráfica se desconecta es un puente.
   2. Corte

      Annotations:

      • Si se elimina un conjunto de aristas y la gráfica queda desconectada es un corte.
      1. Longitud del corte

         Annotations:

         • Aristas que conforman el corte.
         1. Distancia del corte

            Annotations:

            • Mínimo de líneas que conforman el corte.
   3. Punto de articulación

      Annotations:

      • Si la gráfica contiene un nodo que al eliminarlo se desconecta, es un punto de articulación.
   4. Bloque

      Annotations:

      • También llamado gráfica conectada o componente. Gráfica que no contiene puntos de articulación.
   5. Gráfica separable

      Annotations:

      • Gráfica que contiene varios puntos de articulación