Teoría de Gráficas

Teoría de Gráficas

1. Grafos G(V,A) V=Vértices A=Aristas

   • Tipos de Grafos
     • Grafos Completos (Kn)
       • Tienen vértices adyacentes entre sí y n(n-1)/2 aristas.
       • Caminos Simples
     • Caminos Simples (Pn)
       • Son grafos lineales sin ciclos, tienen n vértices y n-1 aristas
     • Gráfica Dirigida
       • Las aristas que unen a los nodos tienen una dirección representada por flechas
         • Digráfica Simple
           • No contiene búcles ni líneas paralelas
           • Tiene n vértices y k componentes y tiene a lo más (n-k)(n-k+1) líneas
         • Digráfica Simétrica
           • Por cada arco que une a los nodos Vi a Vj existe uno que los une de Vj a Vi.
         • Digráfica Completa
           • Se denota como DKn donde n es el número de nodos y todos sus nodos tienen arcos paralelos de ida y regreso.
         • Digráfica Asimétrica Completa
           • También llamada "Torneo completo" y para cada par de nodos existe una linea dirigida
           • Tiene n(n-1)/2 líneas
         • Digráfica Regular
           • Es de grado (i, e) donde todos los nodos tienen el mismo grado interno y externo
         • Digráfica Balanceada
           • Cada nodo tiene grado interno = externo
     • Bosques
       • Conformada por varios árboles
         • Los árboles son gráficas simples conectadas sin circuitos
           • Árbol Binario
             • tiene un vértice de grado 2 y los restantes son de grado 1 o 3
           • Árbol Estrictamente Binario
             • Cada nodo tiene 0, 1 o 2 hijos
     • Subgráficas
       • Todos los vértices de g están contenidos en G y cada línea de g tiene los mismos vértices de terminales en G
     • Gráfica Bipartita
       • El conjunto de vértices puede dividirse en dos subconjuntos donde las vértices de un subconjunto no deben ser adyacentes a los elementos del otro subconjunto
     • Gráfica Bipartita Completa
       • Todos los nodos de un subconjunto son adyacentes los nodos del otro subconjunto
     • Multigrafo o Pseudografo
       • Tiene líneas paralelas y búcles
   • Tamaño de G: Es el número de aristas que tiene una gráfica
   • Orden de G: Es el número de nodos que tiene una gráfica
     • Trivial. Gráfica que consta de un sólo nodo
   • Incidencia y Adyacencia
     • Un nodo es terminal de un arco, el nodo incide en el arco o la línea incide en él
     • Dos arcos no paralelos son incidentes de un nodo en común o dos nodos comparten una línea, son adyacentes

2. Teoremas

   • Havel Hakimi
   • Lema del apretón de manos
     • Nodos de grado impar son par
     • Nodos aislados son de grado 0
     • Nodos de grado 1 son colgantes
   • Gráfica desconectada
   • Gráfica simple de n vertices y k subconjuntos
     • Tiene a lo más (n-k)(n-k+1)/2 líneas

Images and files in the map