05/06/2018

1

Facultad de Informática Culiacán

Tema: GRAFOS

Instructor: MC. Gerardo Gálvez Gámez

Junio de 2018

UNIVERSIDAD AUTÓNOMA DE SINALOA

Grafos • FIUAS

Temas

• Grafos▫ Definición.▫ Aplicaciones.▫ Clasificación.▫ Conceptos básicos.▫ Representación.▫ Operaciones que se pueden

realizar.▫ Diseño de clases para su

implementación ▫ Prácticas y resolución de

problemas.

05/06/2018

2

Grafos • FIUAS

Definición de Grafo

• Son estructuras de datos no lineales, que permitemodelar relaciones arbitrarias entre objetos,donde cada componente puede tener uno o máspredecesores y sucesores.

Un grafo G = (V, E), está formadopor un conjunto de elementosllamados vértices “V” y unconjunto de aristas “E” queconectan a los distintos vértices.

Grafos • FIUAS

Definición de Grafo

• Las aristas.- Conectan a un vértice con otro, ypueden tener asociado un valor, el cual representa elpeso o dificultad para desplazarse de un vértice aotro.

• Los vértices.- Almacenan información.

05/06/2018

3

Grafos • FIUAS

Ejemplo gráfico de un Grafo:

Donde:

Vértices = {A, B, C, D, E}

Aristas = {(A, B), (A, D), (B, C), (B, D), (B, E), (C, E), (D, E), (E, D)}

Grafos • FIUAS

Aplicaciones de los grafos

• Para resolver diversos problemas como:▫ La síntesis de circuitos secuenciales, contadores o sistemas de

apertura, dibujo computacional, en toda las áreas de Ingeniería.

• Para modelar trayectos como:▫ El de una línea de autobús a través de las calles de una ciudad, en el

que podemos obtener caminos óptimos para el trayecto aplicandodiversos algoritmos como puede ser el algoritmo de Floyd.

• Para la administración de proyectos:▫ Donde se utilizan técnicas como técnica de revisión y evaluación de

programas (PERT).

• Se emplea en problemas de control de producción:▫ Para proyectar redes de computadoras,▫ Para diseñar módulos electrónicos modernos y proyectar sistemas

físicos con parámetros localizados (mecánicos, acústicos y eléctricos).• Para la solución de problemas de genética y problemas de

automatización de la proyección (SAPR).

• Entre muchos más (probabilidad, estadísticas, matemáticas, etc.)

05/06/2018

4

Grafos • FIUAS

Aplicaciones de los grafos

Grafos • FIUAS

Clasificación de grafos

• Grafo no dirigido.- Si los arcosestán formados por pares denodos no ordenados, noapuntados; se representa conun segmento uniendo los nodos,u — v.

• Grafo dirigido (dígrafo) .- Silos pares de nodos que formanlos arcos son ordenados; serepresentan con una flecha queindica la dirección de la relación,u → v.

05/06/2018

5

Grafos • FIUAS

Clasificación de grafos

No Dirigido Dirigido

Grafos • FIUAS

Clasificación de grafos

No Dirigido Dirigido

05/06/2018

6

Grafos • FIUAS

Clasificación de grafos

No Dirigido Dirigido

Grafos • FIUAS

Clasificación de grafos

No Dirigido Dirigido

05/06/2018

7

Grafos • FIUAS

Clasificación de grafos

No Dirigido Dirigido

Grafos • FIUAS

Conceptos básicos de grafo no dirigido

05/06/2018

8

Grafos • FIUAS

Conceptos básicos de grafo dirigido

Grafos • FIUAS

Conceptos básicos de grafo dirigido

• Ciclo es un caminosimple cerrado. Portanto, un cicloempieza y termina enel mismo nodo, v0 =vn, y además, debetener más de un arco.

• Un grafo dirigido sinciclos (acíclico) seacostumbra adenominar GDA(Grafo DirigidoAcíclico).

05/06/2018

9

Grafos • FIUAS

Camino de un grafo

• Un camino P de longitud n

desde el vértice v0 a vn enun grafo G, es la secuenciade n+1 vértices v0, v1,v2,..., vn tal que ( vi ,vi+1)∈ A(arcos) para 0 ≤ i ≤ n.

• Matemáticamente, el caminoP = (v0,v1,v2,...,vn).

• La longitud del camino esel número de arcos que loforma.

En el siguiente grafo, se puedenencontrar más de un camino:

• P1 = (4,6,9,7), es uncamino de longitud 3.

• P2 = (10, 11) es uncamino de longitud 1.

Grafos • FIUAS

REPRESENTACIÓN DE LOS GRAFOS

• Hay que pensar cómo representarlo enmemoria interna, qué tipos o estructurasde datos se deben utilizar para considerarlos nodos y los arcos.

• Una primera simplificación es considerar losvértices o nodos como números consecutivos,empezando por el vértice 0.

• Es preciso tener en cuenta que se ha derepresentar un número (finito) de vértices yde arcos que unen dos vértices.

05/06/2018

10

Grafos • FIUAS

REPRESENTACIÓN DE LOS GRAFOS

• Representación secuencial:▫ mediante un arreglo

bidimensional, conocida como matriz de adyacencia;

• Representación dinámica:▫ mediante una estructura

multienlazada, denominada listas de adyacencia.

Grafos • FIUAS

Representación con matriz de adyacencia

• La matriz de adyacencia de un grafo X y el número desus vértices Y, al margen de que sea dirigido o no, seráuna matriz de Y x Y.

• Ejemplo:

▫ Para un grafo con los vértices {A,B,C,D}, dibujaremosuna tabla de 4×4 opcionalmente podemos señalizar las

columnas y las filas con el nombre del vértice.

A B C D

A

B

C

D

05/06/2018

11

Grafos • FIUAS

Representación con matriz de adyacencia

Obtenemos una matriz simétrica

Grafo no dirigido Grafo dirigido

• Si sumamos las columnas:• obtenemos el grado de entrada

• Si sumamos las filas:• Obtenemos el grado de salida

Matriz= Matriz=

Grafos • FIUAS

Matriz de accesibilidad

• Representa los vértices que son alcanzables por otrosvértices, hablamos también de una matriz cuadrada, cuyoselementos pueden ser (Qij):

▫ 1 si Vi es alcanzable desde Vj, 0 en otro caso

1 2 3 4 5

1

2

3

4

5

D F K L R

D

F

K

L

R

05/06/2018

12

Grafos • FIUAS

Matriz con factor de peso

En un grafo valorado, cada elemento representa el peso de la arista, y por ello se la denomina matriz de pesos.

A B C M R

A 0 0 5 5 0

B 0 0 3 6 3

C 3 0 0 0 0

M 0 2 0 0 0

R 0 1 0 0 0

Grafos • FIUAS

Representación con Lista de adyacencia

5

05/06/2018

13

Grafos • FIUAS

Elección de una representación

• Depende del tipo de grafo y de lasoperaciones que se vayan a realizar sobre losvértices y aristas (arcos).

• Para un grafo denso (aquel que tiene lamayoría de las aristas posibles):

▫ Lo mejor es utilizar una matiz de adyacencia.

• Para un grafo disperso (aquel que tiene,relativamente, pocas aristas):

▫ Se suelen utilizar listas de adyacencia que se ajustanal número de aristas.

Grafos • FIUAS

Tipo Abstracto de Datos Grafo

• Su realización depende de la representación elegida (matrizde adyacencia, o listas de adyacencia).

• Operaciones a considerar:

▫ Añadir Arista (u, v), al grafo.

▫ Añadir Arista(u, v) y Costo (w), un grafo valorado.

▫ Elimina Arista(u, v), del grafo .

▫ Vértices Adyacente (u, v). Operación que devuelve cierto silos vértices u, v forman una arista.

▫ Añadir Vértice(u)n al grafo G.

▫ Elimina el Vértice (u) del grafo G.

05/06/2018

14

Grafos • FIUAS

Actividades para el Alumno:

Elaboré un proyecto gráfico, utilizando unlenguaje de programación (C# o Java), para elmanejo de captura de datos correspondientesa un grafo dirigido de n nodos representadopor su matriz de accesibilidad y/o con factorde peso.

Grafos • FIUAS

Jerarquía de Clases a considerar para la

estructura del objeto grafo

Vertice

-nombre:string-numero:int

+Vertice()+Vertice(pNombre:string,pNumero:int)+Nombre:string{set,get}+Numero:int{get,set}+Igualdad(pVertice :Vertice):bool

Grafo

-numerovertice:int-tamañomaximo:int-vetices[tamañomaximo]:Vertice(class)-matrizadyacente[tamañomaximo][tamañomaximo]:int

+Grafo()+Grafo(pTamañoMaximo:int)+AñadirVertice(pNombre:string)+AñadirArista(pVerticeX:string, pVerticeY:string)+AñadirArista(pVerticeX:string, pVerticeY:string, pPeso:int)+EliminarArista(pVerticeX:string, pVerticeY:string)+EliminarVertice(pNombre:string)+VerticesAdyacentes(pVerticeX:string, pVerticeY:string):bool+RecorridoProfundidad():string+RecorridoAnchura():string

05/06/2018

15

Grafos • FIUAS

Descripción funcional de operaciones

1. El constructor sin argumentos deberá crearla matriz de adyacencia para un máximo de 20vértices preestablecido; el otro constructortiene un argumento con el máximo número devértices indicados por el usuario.

2. La operación Añadir un vértice, recibe elnombre(String) de un vértice del grafo, ycomprueba si ya está en la lista de vértices, encaso negativo incrementa el número de vérticesy lo asigna a la lista.

Grafos • FIUAS

Descripción funcional de operaciones

3. El método Añadir una Arista, recibe elnombre de cada vértice de la arista, busca, enel arreglo el número de vértice y asigna a cadauno de ellos la marca en la matriz deadyacencia.

4. La operación Vértices Adyacentes, Determinasi dos vértices, v1 y v2, forman una arista; esdecir, si el elemento de la matriz de adyacenciaes 1.

05/06/2018

16

Grafos • FIUAS

Diseño de Interfaz de usuario

Recorridos

Resolución de problemas

05/06/2018

17

Grafos • FIUAS

Recorrido en anchura

• Se utiliza una cola como estructura en la quese mantienen los vértices marcados que sevan a procesar posteriormente.

• El proceso de los elementos en una cola(primero en entrar primero en salir) haceque, a partir del vértice de partida v seprocesen primero todos los vérticesadyacentes a v, después los adyacentes deéstos que no estuvieran ya marcados ovisitados, y así sucesivamente con losadyacentes de los adyacentes.

Grafos • FIUAS

El orden en que se visitan los nodos en el

recorrido en anchura

Algoritmo:

1.Marcar el vértice de partida v.

2.Meter en la cola el vértice de partida v.

3.Repetir los pasos 4 y 5 hasta que se cumpla la condición cola vacía.

3.1.Quitar el nodo frente de la cola, w, visitar w.

3.2.Meter en la cola todos los vértices adyacentes a w que no estén marcados y, a continuación marcar esos vértices.

6.Fin del recorrido.

05/06/2018

18

Grafos • FIUAS

Ejemplo:

Grafos • FIUAS

Recorrido en profundidad

• La búsqueda de los vértices y aristas de ungrafo en profundidad persigue el mismoobjetivo que el recorrido en anchura: visitartodos los vértices del grafo alcanzables desdeun vértice dado.

• Difiere este recorrido con el recorrido enanchura, sólo en el orden en que se procesanlos vértices adyacentes.

• El orden en el recorrido en profundidad es elque determina la estructura pila.

05/06/2018

19

Grafos • FIUAS

Recorrido en profundidad

• El recorrido empieza por un vértice v del grafo,se marca como visitado y se mete en la pila.

• Después se recorre en profundidad cadavértice adyacente a v no visitado; hasta queno haya más vértices adyacentes no visitados.

• Esta estrategia de examinar los vértices sedenomina en profundidad porque la dirección devisitar es hacia adelante mientras resulta posible;al contrario que la búsqueda en anchura queprimero visita todos los vértices posibles enamplitud.

Grafos • FIUAS

Ejemplo:

05/06/2018

20

Grafos • FIUAS

Bibliografía

ESTRUCTURAS DE DATOSDe: OSVALDO CAIRO

Editorial: MCGRAW-HILL INTERAMERICANAISBN: 9701059085Edición: 3ªAño: 2006No. de páginas: 467Idioma: ESPAÑOLPaís: MEXICO

http://blogs.ua.es/jabibics/2011/01/06/capitulo-11-matriz-de-incidencia/

Grafos • FIUAS

Ejercicios

• 1.-.Dado el siguiente grafo no dirigido, obtenga lamatriz de accesibilidad y el recorrido en anchura,partiendo del vértice 2.

05/06/2018

21

Grafos • FIUAS

• Recorrido:______________________

• Demostración

Grafos • FIUAS

DataGridView C#

05/06/2018

22

Grafos • FIUAS

DataGridView

• Proporciona una tabla personalizable para mostrar datos.

• Espacio de nombres: System.Windows.Forms

// Modify the value in the first cell of the second row. this.dataGridView1.Rows[1].Cells[0].Value = "new value";

// The previous line is equivalent to the following line. this.dataGridView1[0, 1].Value = "new value";

http://msdn.microsoft.com/es-es/library/system.windows.forms.datagridview.rows(v=vs.110).aspx

Grafos • FIUAS

Obtener un arreglo bidimensional de un

DataGriedView

private int[,] ObtenerArreglo(DataGridView dgvDatos){

int [,] Numeros=new int[dgvDatos.RowCount,dgvDatos.ColumnCount];for (int Renglon = 0; Renglon < dgvDatos.RowCount; Renglon++){

for (int Columna = 0; Columna < dgvDatos.ColumnCount; Columna++){

object Valor = dgvDatos.Rows[Renglon].Cells[Columna].Value;if (Valor != null){

Numeros[Renglon, Columna] = Convert.ToInt32(Valor.ToString());}

}}return Numeros;

}

05/06/2018

23

Grafos • FIUAS

Mostrar una Matriz en un DataGridView

private void MostrarResultado(DataGridView dgvResultado,int[,] pMatriz){

for (int Renglon = 0; Renglon < dgvResultado.RowCount; Renglon++){

for (int Columna = 0; Columna < dgvResultado.ColumnCount; Columna++){

dgvResultado.Rows[Renglon].Cells[Columna].Value = pMatriz[Renglon, Columna].ToString();

}}

}

Grafos • FIUAS

Invocar los Métodos

private void btnMostarResultado_Click(object sender, EventArgs e){

int[,] MatrizA = ObtenerArreglo(this.dgvMatrizA);

MostrarResultado(this.dgvResultados,MatrizA);

}

05/06/2018

24

Grafos • FIUAS

Validar entrada de datos en DataGridView

• Programar el evento KeyPress del DataGridView

private void dgvMatriaA_KeyPress(object sender, KeyPressEventArgs e){

if(!(Char.IsDigit(e.KeyChar) || Char.IsControl(e.KeyChar))){

e.Handled = true;}

}

• Programar el evento EditingControlShowing del DataGridView

private void dgvMatriaA_EditingControlShowing(object sender, DataGridViewEditingControlShowingEventArgs e)

{ TextBox txtCelda =e.Control as TextBox; if (txtCelda != null ){

txtCelda.KeyPress += new KeyPressEventHandler(dgvMatriaA_KeyPress);}

}

Grafos • FIUAS

Método para la clase TDAGrafopublic DataTable ObtenerMatriz()

{DataTable datos = new DataTable();//agregar las columnas titulosfor (int x = 0; x < this.tamañomaximo;x++ ){

datos.Columns.Add(this.vertices[x].Nombre,typeof(string));}//agregar los datos de la matriz al datatableDataRow Renglon;for (int x = 0; x < this.tamañomaximo; x++){

Renglon = datos.NewRow();for (int y = 0; y < this.tamañomaximo; y++){

Renglon[y] = this.matriz[x, y].ToString();}datos.Rows.Add(Renglon);

}return datos;

}

Llamado del métodothis.dataGridView1.DataSource = this.Grafo.ObtenerMatriz();

05/06/2018

25

Grafos • FIUAS

Inicializaciones clase TDAGrafo

private void InicializarMatriz(){

for (int x = 0; x < this.tamañomaximo; x++){

for (int y = 0; y < this.tamañomaximo; y++){

this.matriz[x, y]=0;}

}}private void InicializarVertices(){

for (int x = 0; x < this.tamañomaximo; x++){

this.vertices[x] = new TDAVertice();this.vertices[x].Nombre = "Libre " + x.ToString();

}}

Grafos • FIUAS

Jtable Java

05/06/2018

26

Grafos • FIUAS

Jtable Java

String [][]Datos=new String[5][5];

Datos[0][0]="10";

Datos[1][1]="10";

Datos[2][2]="10";

String cabecera[]={"uno","dos","tres"};

DefaultTableModel Modelo;

Modelo=new DefaultTableModel(Datos,cabecera);

this.jTable1.setModel(Modelo);

Grafos • FIUAS

Método para la clase TDAGrafopublic DefaultTableModel ObtenerMatriz()

{ String [][] datos=new String[this.tamañomaximo][this.tamañomaximo];String[]encabezado=new String[this.tamañomaximo];//convertir la matriz a cadenafor(int x=0;x<this.tamañomaximo;x++){

for(int y=0;y<this.tamañomaximo;y++){

datos[x][y]= String.valueOf(matriz[x][y]);}

}//definir el encabezadofor(int x=0;x<this.tamañomaximo;x++){

encabezado[x]=this.vertices[x].nombre;}//crear el modeloDefaultTableModel modeloMatriz=new DefaultTableModel(datos,this.vertices);return modeloMatriz;

}

Invocarlo desde la interfaz :this.jTable1.setModel(ObjetoTDAGrafo.ObtenerModelo());

05/06/2018

27

Grafos • FIUAS

Preguntas?

FIN de Unidad