Introducción a la teoría de grafos.(Unidad 1)

Introducción a la teoría de grafos.(Unidad 1)

1. Tipos de grafos

   • Simple
     • Tiene arcos y nodos, no tiene bucles
   • Bipartida
     • Contiene dos subgráficas
   • Arbol
     • Tiene circuitos, debe de ser simple y no tiene bucles
   • Bosque
     • Conjuntos de arboles
   • Regular
     • Tiene que ser simple. Nodos con mismo grado
   • Desconectada
     • No puede haber un grafo que comience en un subconjunto y termine en otro
   • Conectada
     • Solo si su subconjunto de nodos se divide en dos subconjuntos
   • Completa
     • Debe de existir un arco entre cada par de nodos

2. Tipos de Líneas

   • Sin dirección
     • No tiene flecha
   • Paralelas
     • Comparten mismo nodo inicial y final
   • En serie
     • Nodos tienen valencia de 2
   • Adyacentes
     • Comparten dos aristas un nodo
   • Con dirección
     • Tienen flecha

3. Teoremas

   • Apretón de manos
     • Gráfica no contiene bucles y la suma de la valencia de los nodos es el número de líneas
   • Algoritmo Havel-Hakimi
     • Valor máximo menor que la longitud

4. Tipos de nodos

   • Colgantes
     • Nodos de grado 1
   • Terminales
     • Nodo de grado interno uno y grado externo cero
   • Adyacentes
     • Nodos que comparten arista
   • Aislados
     • Nodo de grado cero