Grafos - Tipos de Grafos (Parte 1)


  • administrators

    Definicion

    Un grafo es la representación por medio de conjuntos de relaciones arbitrarias entre objetos. Existen dos tipos de grafos según la relación entre los objetos. Los primeros forman los grafos dirigidos o digrafos y los segundos los grafos no dirigidos o simplemente grafos.

    Grafo Dirigido

    Un grafo dirigido o dígrafo consiste de un conjunto de vértices $v \in V$ y un conjunto de arcos $E$. Los vértices se denominan como nodos, los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices(nodos) existe una relación unívoca $(a-R-b)$ pero no $(b-R-a)$. De modo que los arcos se representan comúnmente por medio de pares ordenados $(a,b)$, donde se dice que $a$ es la cabeza y $b$ la cola del arco y a menudo se representa también por medio de una flecha, tal como se muestra en la siguiente figura.

    0_1537845415237_440px-Kaari_suunnattu_graafiteoria.png

    Grafo no dirigido

    Un grafo no dirigido o grafo propiamente dicho es un grafo $G=(V,E)$ donde $V \ne 0$. Al igual que un dígrafo consiste de un conjunto de vértices $V$ y un conjunto de arcos $E$. La diferencia consiste en que la existencia de $(a-R-b)$ presupone que $(b-R-a)$ también existe y además que son iguales. De este modo es indistinto hablar del arco $(a,b)$ o $(b,a)$, tampoco tiene sentido hablar de la cabeza o la cola del arco. Los grafos representan como lo indica la siguiente figura, donde los círculos representan los vértices y las líneas representan los arcos.

    0_1537845443014_440px-Kaari_suuntaamaton_graafiteoria.png

    Grafos Ponderados

    Grafos en donde los arcos tienen asociado algún valor en cuyo caso hablamos de grafos ponderados y ahora se representan los arcos como tripletas. Sigue existiendo la información de los vértices unidos por dicho arco además de la información del peso de dicho arco. Así pues el arco se representa como $a=(v_i,v_j,w)$ donde $(v_i, v_j)$ son el origen y destino y ($w$) es el peso respectivamente.

    Por lo general en computadora existen dos representaciones principales de grados de las cuales hablaremos en las siguientes lecciones (partes), siendo la más utilizada la representación mediante Arrays de Arrays (Matriz de Adyacencia $G[v_i,v_j] =w$).

    G[ v[i] ][ v[j] ] = w;

    Algunos Grafos Particulares

    Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo.
    Grafo vacío: aquel que no tiene aristas.
    Grafo trivial: aquel que tiene un vértice y ninguna arista.
    Grafo simple: aquel que no posee bucles ni aristas paralelas.
    Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
    Grafo bipartito: sea $(W,X)$ una partición del conjunto de vértices $V$, es aquel donde cada arista tiene un vértice en $W$ y otro en $X$, este tipo de grafos es muy común en competencias de algoritmos, donde un conjunto de nodos esta en un grupo y el otro conjunto está en otro donde ningún nodo se conecta.
    Grafo bipartito completo: sea $(W,X)$ una partición del conjunto de vértices $V$, es aquel donde cada vértice en $W$ es adyacente sólo a cada vértice en $X$, y viceversa.
    Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
    Árbol: grafo conexo sin ciclos.
    Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

    Grafos - Metodos de representación en computadora (Parte 2)