Unidad 1

Unidad 1

1. GRAFO

   • conjunto de vértices y aristas G=(V,e)
   • MULTIGRAFO
     • Debe tener líneas paralelas pero sin bucles.
   • NULO
     • No contiene aristas y se denota como Nn.
   • SIMPLE
     • No contiene bucles ni líneas paralelas.
     • REGULAR
       • Grafo simple donde todos los vértices tienen el mismo grado. Número de lineas (n*r)/2.
     • COMPLETO
       • Grafo simple donde cada para de vértices son adyacentes, Kn. Tiene exactamente n*(n-1)/2 líneas.
     • BIPARTIDO
       • Grafo simple en donde el conjunto de vértices puede dividirse en dos subconjuntos Vk y Vr, G(Vk,Vr).(bipartita, bicoloreable).
     • BIPARTITO COMPLETO
       • Todos los vértices de V1 son adyacentes a los de V2, Kr,s. Existe una arista entre cada par de vértices V1 y V2.
   • GENERAL
     • También conocido como pseudografo. Contiene bucles y/o líneas paralelas.
   • CONECTADA
     • Se puede alcanzar un nodo cualquiera a partir de otro.Existe una trayectoria entre cada par de nodos.
   • FUERTEMENTE CONECTADO
     • Si de un vértice puede pasarse a cualquier otro incluyendo este mismo, FKn. Tiene exactamente n*(n+1)/2 líneas.
   • SUBGRAFO
     • Si todos los vértices de g están contenidos en G y además cada línea de g tiene los mismos nodos terminales de G.
     • LÍNEAS SEPARADAS
       • Si g1 y g2 no comparten líneas( pueden compartir nodos).
     • VÉRTICES DISJUNTOS
       • Si g1 y g2 no comparten nodos.
     • EXPANDIDO
       • Es un subgrafo que se obtiene al eliminar líneas de modo que los nodos permanezcan conectados con la menor cantidad de aristas y sin circuitos. Un subgrafo puede contener varios subgrafos expandidos.
   • ISOMORFO
     • Cuando G y G´ tienen una correspondencia uno a uno entre sus nodos, líneas y relación de incidencia se mantiene.
   • SEPARABLE
     • Contiene varios puntos de articulación.
   • TRIVIAL
     • Grafo de orden 1
   • INFINITO
     • Número infinito de nodos.
   • FINITO
     • Número finito de nodos.
   • COMPONENTES
     • Subconjuntos disjuntos de grafos no conectados. Un grafo simple con n vértices y k subconjuntos puede tener a lo más (n-k)*(n-k+1)/2 líneas.

2. TAMAÑO

   • Número de arcos en una gráfica.

3. ORDEN

   • Número de nodos en un grafo.

4. DIGRAFO

   • Grafo donde los arcos tienen dirección.
   • CONECTADO
     • Existe al menos un paseo dirigido entre cualquier par de nodos.
   • ISOMORFO
     • Sus grafos son isomorfos y se mantiene la dirección.
   • SIMPLE
     • No contiene bucles ni líneas paralelas, puede tener líneas recurrentes. Tiene a lo más (n-k)*(n-k+1) líneas.
   • SIMÉTRICO
     • Para cada arco que va del nodo Vi a Vj existe otro que va de Vj a Vi(recurrentes). No debe tener bucle.
   • ASIMÉTRICO
     • Tiene a lo más una línea dirigida entre un par de nodos y no puede tener bucles. Al menos un arco no tiene un arco recurrente.
   • SIMÉTRICO COMPLETO
     • Para cada par de vértices existe una línea de idea y de regreso, DKn. No contiene bucles.
   • ASIMÉTRICO COMPLETO
     • Hay exactamente una línea dirigida entre cada par de nodos. Tiene n*(n-1)/2.(Torneo completo).
   • REGULAR
     • Todos los vértices tienen el mismo grado interno y externo. Tiene un máximo de n-1 grados internos y externos.
     • BALANCEADO
       • Cada nodo en su grado externo y en su grado interno son iguales.
   • PSEUDODIGRAFO
     • Puede tener múltiples aristas y/o bucles.
   • MULTIDIGRAFO
     • Tiene múltiples arista paralelas y recurrentes, No tiene bucles.

5. ÁRBOL

   • Un grafo simple  sin bucles,líneas paralelas y circuitos. Existe una y sólo una trayectoria entre todo par de nodos en un árbol T. Si en un grafo existe una y sólo una trayectoria entre todo par de nodos, entonces G es un árbol. Un árbol tiene n-1 aristas.
   • BINARIO
     • Cada vértice tiene uno o dos hijos, el grado de sus nodos son 1,2 o 3.
     • ESTRICTAMENTE BINARIO
       • Un solo nodo de grado 2 y el resto de grado 3 o 1. Número de nodos colgantes es (n+1)/2
   • BOSQUE
     • Conjunto de árboles. Un bosque B con n nodos y k árboles tiene n-k líneas.
   • ARBORESCENCIA
     • Es un árbol con dirección.Debe existir una raíz y una trayectoria dirigida a la raíz hacía los demás nodos.
   • DISTANCIA
     • Es la longitud del camino que une un par de vértices, d(Vi,Vk).
     • EXCENTRICIDAD
       • Es la máxima distancia de un nodo a cualquier otro nodo del grafo, E(V).
       • CENTRO
         • Es él o los vértices de excentricidad mínima, E(c).

6. INCIDENCIA

   • Concepto relacionado al "choque" entre nodos y arcos.

7. ADYACENCIA

   • Cuando dos arcos no paralelos son incidentes en un vértice común.

8. GRADO

   • También se le llama valencia.Es el número de líneas que inciden en un nodo (d(Vi)).

9. TEOREMAS

   • JSKSKDK
   • GRADO IMPAR
     • El número de vértices de grado impar en un grafo sin bucles es par.
   • HAVEL-HAKIMI
     • Identifica si una secuencia de números enteros positivos corresponde a los grados de un grafo simple.
   • APRETÓN DE MANOS
     • En un grafo sin bucles, la suma de sus valencias es igual a dos veces el número de líneas.

10. ARCOS Y NODOS

    • DIRIGIDAS
      • GRADO INTERNO
        • Número de líneas incidentes hacia adentro de Vi, d-(Vi). La suma de los grados internos de un digrafo es igual a la suma de los grados externos e igual al número de líneas que contiene el digrafo.
      • GRADO EXTERNO
        • Número de líneas incidentes hacia afuera de Vi, d+(Vi).
      • NODO AISLADO
        • Su grado interno y externo es 0.
      • NODO TERMINAL
        • Su grado externo es 0 y el interno es diferente de 0. Todos los arcos llegan a él.
      • NODO INICIAL
        • Su grado interno es 0 y el externo es diferente de 0. Todos los arcos salen de él.
      • NODO INTERMEDIO
        • Aquéllos que nos son nodos finales o iniciales.
      • NODO COLGANTE
        • Su grado es uno.
      • LINEA PARALELA
        • Comparten el mismo nodo inicial,terminal y sus arcos tienen el mismo sentido.
      • LÍNEA RECURRENTE
        • Comparten nodos iniciales y terminales pero con sentido contrario en sus arcos.
      • BUCLE
      • VÉRTICE INICIAL
        • Incidencia hacía afuera.
      • VÉRTICE FINAL
        • Incidencia hacia adentro.
    • NO DIRIGIDAS
      • BUCLE
        • Arco asociado a un solo nodo.(loop,rizo,ciclo,lazo)
      • ARCO PARALELO
        • Arcos asociados al mismo par de nodos.
      • NODO AISLADO
        • Nodo de grado cero.
      • NODO COLGANTE
        • Nodo de grado uno.(pendiente,final).
      • ARCO EN SERIE
        • Arcos adyacentes con vértice en común de grado 2.

11. PASEOS

    • Secuencia finita y alterna de nodos y arcos. Se pueden repetir nodos,arcos e incluir bucles.(camino).
    • ABIERTO
      • Termina en un vértice distinto del cual comienza.
    • CERRADO
      • Termina en el mismo vértice del cual comienza.
    • DIRIGIDO
      • Secuencia alterna de nodos y líneas donde se respeta la dirección de los arcos.
      • SEMIPASEO
        • Si el paseo en el grado no dirigido existe.

12. TRAYECTORIA

    • Paseo abierto donde no se repiten vértices. Si un grafo tiene exactamente 2 nodos de grado impar, deberá existir una trayectoria que los una.
    • DIRIGIDA
      • Paseo dirigido abierto sin bucles.

13. CIRCUITO

    • Paseo cerrado donde no se repiten vértices.
    • DIRIGIDO
      • Es un paseo dirigido cerrado sin bucles.

14. LONGITUD

    • Número de líneas que contiene el paseo.

15. DISTANCIA

    • Longitud del paseo mínimo.

16. LÍNEA DE CORTE

    • Si al eliminarse una sola línea de un grafo este se desconecta.
    • CORTE
      • Conjunto de aristas que desconectan un grafo. Este puede tener varios cortes.
      • LONGITUD DE CORTE
        • Número de aristas que conforman el corte.
      • DISTANCIA DE CORTE
        • La mínima longitud de corte.

17. PUNTO DE ARTICULACIÓN

    • Vértice que al eliminarse desconecta el grafo. Al eliminar el vértice se eliminan los arcos incidentes a este.
    • BLOQUE
      • Grafo sin punto de articulación.

Imágenes y archivos del mapa