En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Tipos de grafos:
Existen dos tipos de grafos, los dirigidos y los no dirigidos:
- Dirigidos: Son aquellos en los cuales los lados están orientados(flechas). Cada lado se representa entre ángulos separando sus vértices por comas y teniendo en cuenta <vi,vj> = <vj,vi>. En grafos dirigidos, para cada lado <a,b>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como la cabeza del lado.Figura 3.
- No dirigidos: Son aquellos en los cuales los lados no están orientados(no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (vi,vj) = (vj,vi). Figuras 1 y 2.
Ejemplos:
1) Dado el siguiente grafo obtener su matriz de adyacencia (No dirigida, grafo)
Al momento de crear la matriz debemos poner con uno los vértices que estén conectados y con 0 los vértices que no estén conectados.
2) Dada la siguiente matriz de adyacencia, dibuje el grafo que la represente (No dirigida, matriz)
Una vez que se tiene la matriz, de dibujan los 4 vértices(A,B,C,D) y se conectan los vértices de acuerdo a la matriz.
3) Dado el siguiente grafo, obtener su matriz de adyacencia (Dirigida, grafo)
En este caso como el grafo es dirigido, relacionamos los vértices desde la fila, es por eso que A con B da 1, pero B con A da 0.
No hay comentarios:
Publicar un comentario