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

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

1. ¿Qué es una gráfica?

   • Conjunto de vértices, nodos o puntos unidos por aristas, líneas o arcos que pueden, o no, ser con dirección
     • Tipos de gráficas
       • Multigrafo o pseudografo
         • Es aquella que tiene múltiples aristas
       • Nula
         • No contiene aristas
       • Simple
         • No contiene bucles ni líneas paralelas
       • General
         • Contiene bucles y líneas paralelas
       • Finitas o infinitas (a criterio de sus nodos)
       • Regular
         • Debe ser una gráfica simple y los grados de sus nodos deben ser iguales
       • Subgráficas
         • Todos los vértices de g están contenidos en G
         • Cada línea de g tiene los mismos vértices terminales en G
         • G es subgráfica de g; subgráfica de g es subgráfica de G; un vértice es subgráfica de G; un arco con sus respectivos nodos es una subgráfica de G
       • Isomórfica
         • Dos gráficas que comparten la relación entre sus nodos y sus arcos aún siendo graficadas de diferente forma
       • Digráfica o gráfica dirigida
         • Multidigrafo: digrafo con múltiples aristas
         • Pseudografo: multidigrafo con bucles
         • Longitud y distancia
           • Número de líneas que contiene un paseo
           • Entre dos nodos, es la distancia del paseo mínimo que los une
       • Bloque
       • Separada
     • Paseos
       • Secuencia de pasos finita y alterna de nodos y arcos comenzando y terminando en un nodo de cada línea tal que sean incidentes con nodos anteriores y posteriores
       • Abiertos
         • Trayectoria simple: no se repiten nodos ni arcos
       • Cerrados
         • Circuito: no se repiten nodos ni arcos salvo el nodo inicial y el nodo final
     • Árboles
       • Árbol
       • Árbol binario
       • Árbol estrictamente binario
   • El tamaño es el número de arcos en G
     • Arcos
       • Dirigido
         • Crean una gráfica dirigida ó bigráfica
       • No Dirigido
       • Paralelos
       • Si dos arcos NO paralelos inciden en un nodo, se dice que son adyacentes
       • El número de líneas que inciden en un nodo es llamado grado ó valencia " d(Vi)"
   • El orden es el número de nodos en G
     • Nodos
       • Nodo terminal
         • Cuando un nodo es terminal de un arco, se dice que estos son incidentes
         • Cuando dos arcos comparten una línea en común, son adyacentes
       • Bucle
       • Grado
         • Externo
         • Interno
       • Articulación
         • Aquel nodo al que, si se elimina, desconecta a G

2. Teoremas

   • Si una gráfica sin bucles tiene e líneas y n vértices, la suma del grado de sus vértices es igual a dos veces al número de líneas.
   • El número de vértices de grado impar en una gráfica sin bucles es par
   • Un nodo aislado tiene valencia o grado 0
   • Un nodo de grado 1 se le llama nodo colgante, pendiente o final
   • La suma de los grados internos es igual a la suma de los grados externos y es igual al número de líneas que contiene un grafo

Imágenes y archivos del mapa